排序与二叉树

时间:2021-04-06 17:32:01
插入排序
冒泡排序
选择排序
快速排序
堆排序
归并排序
希尔排序
 
  假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中,ri仍在rj之前,则称这种排序算法是稳定的;否则称为不稳定的。

  快速排序

  两种方法,1.指针两边往中间走。2.指针都在开头 往后走。

排序与二叉树排序与二叉树
 1 public static void quickSort(int[] arr, int start, int end) {
 2         if (start>=end) 
 3             return;
 4         int key = partionByBoth(arr, start,end);
 5         quickSort(arr, start,key-1);
 6         quickSort(arr, key+1,end);
 7     }
 8     
 9     public static int partionByEither(int[] arr, int start, int end) {
10         int mid = start+((end-start)>>2);
11         int key = arr[mid];
12         swap(arr,mid,end);
13         int p = start;
14         int q = end-1;
15         while (p<=q) {
16             if(arr[p] > key){
17                 swap(arr,p,q);
18                 q--;
19             }
20             else
21                 p++;
22         }
23         swap(arr,p,end);
24         return p;
25     }
26     public static int partionByBoth(int[] arr, int start, int end) {
27         int mid = start+((end-start)>>2);
28         int key = arr[mid];
29         swap(arr,mid,end);
30         int p = start;
31         for (int q = start; q < end; q++) {
32             if (arr[q] <= key) {
33                 swap(arr, q, p);
34                 p++;
35             }
36         }
37         swap(arr,p,end);
38         return p;
39     }
40     
41     private static void swap(int[] arr, int a, int b) {
42         int temp = arr[a];
43         arr[a] = arr[b];
44         arr[b] = temp;
45     }
View Code

   快速排序非递归方案

 1     public static void quickSort(int[] arr) {
 2         if (arr == null) 
 3             return;
 4         int[] stack = new int[32];  //默认递归深度最深为32/2,因为快速排序是二叉树的递归
 5         int top=-1;  //栈顶指针
 6         stack[++top]=0; //初始栈的两个值
 7         stack[++top]=arr.length-1;
 8         while (top>0) {
 9             int end = stack[top--];
10             int start = stack[top--]; //从栈顶取出值
11             int key = arr[end];
12             int p = start;
13             for (int q = start; q < end; q++) { //快速排序的划分
14                 if (arr[q] < key) {
15                     int temp = arr[p];
16                     arr[p] = arr[q];
17                     arr[q] = temp;
18                     p++;
19                 }
20             }
21             int temp = arr[p];
22             arr[p] = arr[end];
23             arr[end] = temp;
24             
25             if (p+1 < end) { //压栈  下一半数组的排序
26                 stack[++top] = p+1;
27                 stack[++top] = end;
28             }
29             if (p-1>start) { //压栈  上一半数组的排序
30                 stack[++top] = start;
31                 stack[++top] = p-1;
32             }
33             //注意,执行上述的排序 是 反过来执行的,先执行上一半,再执行下一半,这就是栈
34         }

  三种线性排序算法 :计数排序桶排序与基数排序 

  计数排序

/*  
算法的步骤如下:  
    1.找出待排序的数组中最大和最小的元素  
    2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项  
    3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)  
    4.反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1  
*/  
  
void counting_sort(int *ini_arr, int *sorted_arr, int n)  
{  
       int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE);  
       int i, j, k;  
  
       //统计数组中,每个元素出现的次数  
       for(k=0; k<NUM_RANGE; k++){  
               count_arr[k] = 0;  
       }  
         
       for(i=0; i<n; i++){  
               count_arr[ini_arr[i]]++;  
       }  
  
      //使count_arr数组中的值表示此下标的位置
     //就是使之 下标-值 -》 值-下标
     //eg: 1,3,4 ->01011->01123
     //所以1的值下标在1上,3的值下标在2上,4的值下标在3上
       for(k=1; k<NUM_RANGE; k++){  
               count_arr[k] += count_arr[k-1];  
       }  
       for(j=n-1 ; j>=0; j--){  
           int elem = ini_arr[j];  
           int index = count_arr[elem]-1;  
           sorted_arr[index] = elem;  
           count_arr[elem]--;  
       }  
       free(count_arr);  
}  

   桶排序 

  假设有一组长度为N的待排关键字序列K[1....n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ,将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ,那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。

  假如待排序列K= {49、 38 、 35、 97 、 76、 73 、 27、 49 }。这些数据全部在1—100之间。因此我们定制10个桶,然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中,并在每个非空的桶中进行快速排序。

  桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。 当然桶排序的空间复杂度 为O(N+M)

  基数排序

  整数 425、321、235、432也可以每个位上的数字为一个关键字。

  基数排序的思想就是将待排数据中的每组关键字依次进行桶分配

  278、109、063、930、589、184、505、269、008、083

  我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8 ,k2(十位)=7 ,k3=(百位)=2。

  然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列。

  930、063、083、184、505、278、008、109、589、269

  再对上面的序列接着进行针对k2的桶分配,输出序列为:

  505、008、109、930、063、269、278、083、184、589

  最后针对k3的桶分配,输出序列为:

  008、063、083、109、184、269、278、505、589、930

  基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度,而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2N) ,当然d要远远小于N,因此基本上还是线性级别的。基数排序的空间复杂度为O(N+M),其中M为桶的数量。一般来说N>>M,因此额外空间需要大概N个左右。

   基数排序的应用:线性时间的原地置换(空间O1)排序

排序与二叉树排序与二叉树
 1 /**
 2  * 题目:一个大小为N的数组,里面是N个整数,怎样去除重复,要求时间复杂度为O(n),空间复杂度为O(1). 
 3  *      实际需求就是排序,线性时间的原地置换排序
 4  *      下列算法时间复杂度为 O(n) -> 上界32*n
 5  * @author hawksoft
 6  *
 7  */
 8 public class DeleteRepeatedInt {
 9 //===================================================
10 //排序算法修正部分
11 /// <summary>
12     /// 需要除掉重复的整数的数组,注意这里我没有处理负数情况,
13     /// 其实负数情况只要先用0快排分一下组,然后各自用以下算法进行处理即可。
14     /// 另外因为是整数,这里没考虑32位符号位,只考虑31位。
15     /// 题目分析:从要求来看,如果一个数组是排好序的,除掉重复就很简单,因此就转换成了
16     /// 排序算法寻找,这种算法需要满足:线性时间,常量内存,原地置换。但纵观这么多算法,比较排序肯定不行,
17     /// 那么就只有基数排序,桶排序和计数排序,但基数排序依赖于位排序,而且要求位排序是稳定的,
18     /// 且不能过多使用辅助空间,计数排序排除,因为计数排序无法原地置换,桶排序也需要辅助空间,所以最后考虑用
19     /// 基数排序。但问题是如何选择位排序,因为位上只有0和1,因此有其特殊性,使用快排的分组就可以达到线性,
20     /// 但问题是这种算法虽然是线性,原地置换,但不稳定。所以要利用一种机制来确保快排是稳定的。经过一段时间思考,
21     /// 发现,如果从高位开始排序,假设前K位是排好的,对K+1进行排序时,只针对前K位的相同的进行,前K位不相同,也不可
22     /// 能相等,第K+1位也不影响结果,而前K位相同的排序,就不怕快排的不稳定了,因为这个不稳定不会影响到最终结果。
23     /// 下面就是算法:
24     /// </summary>
25     /// <param name="A"></param>
26     private static void BitSortAndDelRepeatorsB(int[] A)
27     {
28         //获取数组长度
29         int theN = A.length;
30         //从高位到低位开始排序,这里从31位开始,32位是符号位不考虑,或者单独考虑。
31         for (int i = 31; i >= 1; i--)
32         {
33             //当前排序之前的值,只有该值相同才进行快排分组,如果不相同,则重新开始另外一次快排
34             //这很关键,否则快排的不稳定就会影响最后结果.
35             int thePrvCB = A[0] >> (i)  ;
36             //快排开始位置,会变化
37             int theS = 0;
38             //快排插入点
39             int theI = theS-1;
40             //2进制基数,用于测试某一位是否为0
41             int theBase = 1 << (i-1);
42             //位基元始终为0,
43             int theAxBit = 0;
44            
45             //分段快排,但总体上时间复杂度与快排分组一样.
46             for (int j = 0; j < theN; j++)
47             {
48                 //获取当前数组值的前面已拍过序的位数值。
49                 int theTmpPrvCB = A[j] >> (i);
50                 //如果前面已排过的位不相同,则重新开始一次快排.
51                 if (theTmpPrvCB != thePrvCB)
52                 {
53                     theS = j;
54                     theI = theS - 1;
55                     theAxBit = 0;
56                     thePrvCB = theTmpPrvCB;
57                     j--;//重新开始排,回朔一位.
58                     continue;
59                 }
60                 //如果前面的数相同,则寻找第1个1,thI指向其
61                 //如果相同,则按快排处理
62                 int theAJ = (A[j] & (theBase)) > 0 ? 1 : 0; ;//(A[j] & (theBase)) > 0 ? 1 : 0;(A[j] >> (i - 1)) & 1
63                 //如果是重新开始排,则寻找第1个1,并人theI指向其.这可以减少交换,加快速度.
64                 if (theI < theS)
65                 {
66                     if (theAJ == 0)
67                     {
68                         continue;
69                     }
70                     theI = j;//Continue保证J从theI+1开始.
71                     continue;
72                 }
73                 //交换.
74                 if (theAJ <= theAxBit)
75                 {
76                     int theTmp = A[j];
77                     A[j] = A[theI];
78                     A[theI] = theTmp;
79                     theI++;
80                 }
81             }
82         }
83     }
84    public static void main(String[] args) {
85        int[] A = {1,2,3,4,6,8,4,3,1};
86        BitSortAndDelRepeatorsB(A);
87        for (int i : A) {
88         System.out.println(i);
89        }
90    }
91 }
View Code

  需要满足:线性时间,常量内存,原地置换。但纵观这么多算法,比较排序肯定不行(下限nlog(n)),
  那么就只有基数排序,桶排序和计数排序,但基数排序依赖于位排序,而且要求位排序是稳定的,
  且不能过多使用辅助空间,计数排序排除,因为计数排序无法原地置换,桶排序也需要辅助空间,所以最后考虑用基数排序。

  但问题是如何选择位排序,因为位上只有0和1,因此有其特殊性,使用快排的分组就可以达到线性.

  但问题是这种算法虽然是线性,原地置换,但不稳定。所以要利用一种机制来确保快排是稳定的。经过一段时间思考,发现,如果从高位开始排序,假设前K位是排好的,对K+1进行排序时,只针对前K位的相同的进行,前K位不相同,也不可能相等,第K+1位也不影响结果,而前K位相同的排序,就不怕快排的不稳定了,因为这个不稳定不会影响到最终结果。

  上述原话的意思是,假设前K位排好序了,对前k位快排分组,当排到第k+1时,重新设置插入点,起始点,重新快排分组

  eg:初始数据: 6 0 7 0 也就是 110 000 111 000

    排序进行到                       000 000 111 110

    后一步  排完第一个第二个时,轮到第三个,发现111前面的两个和第一个不一致,重新初始化。针对 111 和 110 快排分组。

    结果                                000 000 110 111

 

 

 

 

 

 

 

 

AVL树和红黑树