【原创】经典排序回顾

1 void bubble_sort(int a[], int n){
2     for(int i=0;i){
3         for(int j=0;j1;j++){
4             if(a[j]>a[j+1]){
5                 swap(a[j],a[j+1]);
6             }
7         }
8     }
9 }

 1 void quick_sort(int a[], int left, int right){
 2     if(left<right){
 3         int i=left;
 4         int j=right;
 5         int tmp=a[i];
 6         while(i<j){
 7             while(itmp) j--;
 8             
 9             if(a[j]<tmp){
10                 a[i]=a[j];
11                 i++;
12 
13             }
14             while(i;
15             if(a[i]>tmp){
16                 a[j]=a[i];
17                 j--;
18             }
19         }
20         a[i]=tmp;
21         quick_sort(a, left, j--);
22         quick_sort(a,i++,right);
23     }
24 }

 1 void insert_sort(int a[], int n){
 2     int tmp;
 3     int i,j,k;
 4     for(i=1; i){
 5         for(j=i-1;j>=0;j--){
 6             if(a[j]<=a[i]){//在已经排序的数列里往回找，直到找到一个不大于（所以插入排序是稳定的）当前数的下标位置
 7                 break；
 8             }
 9             if(j!=i-1){//后移元素
10                 tmp=a[i];
11                 for(k=i;k>j+1;k--){
12                     a[k]=a[k-1];
13 
14                 }
15                 a[j+1]=tmp;
16             }
17         }
18     }
19 }

 1 void select_sort(int a[], int n){
 2     int i,j,min;
 3     fot(i=0; i){
 4         min=i;
 5         for(j=i+1; j//从未排序的i+1及后面的数中选取最小值
 6             if(a[j]j;
 7         }
 8         if(min ！=i){
 9             swap(a[i],a[min]);//将最小值交换到i位
10         }
11     }
12 }

 1 void maxheap_down(int a[], int start, int end)
 2 {
 3     int c = start;            // 当前(current)节点的位置
 4     int l = 2*c + 1;        // 左(left)孩子的位置
 5     int tmp = a[c];            // 当前(current)节点的大小
 6     for (; l <= end; c=l,l=2*l+1)
 7     {
 8         // "l"是左孩子，"l+1"是右孩子
 9         if ( l 1])
10             l++;        // 左右两孩子中选择较大者，即m_heap[l+1]
11         if (tmp >= a[l])
12             break;        // 调整结束
13         else            // 交换值
14         {
15             a[c] = a[l];
16             a[l]= tmp;
17         }
18     }
19 }
20 
21 void heap_sort_asc(int a[], int n)
22 {
23     int i;
24 
25     // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
26     for (i = n / 2 - 1; i >= 0; i--)
27         maxheap_down(a, i, n-1);
28 
29     // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
30     for (i = n - 1; i > 0; i--)
31     {
32         // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
33         swap(a[0], a[i]);
34         // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
35         // 即，保证a[i-1]是a[0...i-1]中的最大值。
36         maxheap_down(a, 0, i-1);
37     }
38 }

 1 /*
 2  * 将一个数组中的两个相邻有序区间合并成一个
 3  *
 4  * 参数说明：
 5  *     a -- 包含两个有序区间的数组
 6  *     start -- 第1个有序区间的起始地址。
 7  *     mid   -- 第1个有序区间的结束地址。也是第2个有序区间的起始地址。
 8  *     end   -- 第2个有序区间的结束地址。
 9  */
10 void merge(int a[], int start, int mid, int end)
11 {
12     int *tmp = (int *)malloc((end-start+1)*sizeof(int));    // tmp是汇总2个有序区的临时区域
13     int i = start;            // 第1个有序区的索引
14     int j = mid + 1;        // 第2个有序区的索引
15     int k = 0;                // 临时区域的索引
16 
17     while(i <= mid && j <= end)
18     {
19         if (a[i] <= a[j])
20             tmp[k++] = a[i++];
21         else
22             tmp[k++] = a[j++];
23     }
24 
25     while(i <= mid)
26         tmp[k++] = a[i++];
27 
28     while(j <= end)
29         tmp[k++] = a[j++];
30 
31     // 将排序后的元素，全部都整合到数组a中。
32     for (i = 0; i )
33         a[start + i] = tmp[i];
34 
35     free(tmp);
36 }
37 
38 /*
39  * 归并排序(从上往下)
40  *
41  * 参数说明：
42  *     a -- 待排序的数组
43  *     start -- 数组的起始地址
44  *     endi -- 数组的结束地址
45  */
46 void merge_sort_up2down(int a[], int start, int end)
47 {
48     if(a==NULL || start >= end)
49         return ;
50 
51     int mid = (end + start)/2;
52     merge_sort_up2down(a, start, mid); // 递归排序a[start...mid]
53     merge_sort_up2down(a, mid+1, end); // 递归排序a[mid+1...end]
54 
55     // a[start...mid] 和 a[mid...end]是两个有序空间，
56     // 将它们排序成一个有序空间a[start...end]
57     merge(a, start, mid, end);
58 }