排序

简单排序（前三种就是简单排序）
void X_sort(ElementType A[ ], int N)
1.大多数情况下，为简单期间，讨论从小到大的整数排序
2.N是正整数
3.只讨论基于比较的排序（> = <有定义）
4.只讨论内部排序
5.稳定性：任意两个相等的数据，排序前后的相对位置不发生改变
6.没有一种排序是任何情况下都是变现最好的

1.冒泡排序

 1 void Bubble_sort(ElementType A[], int N)
 2 {
 3     int flag, i, j;
 4     for (i = N - 1; i >= 0; i--)        //N- 1趟冒泡
 5     {
 6         flag = 0;
 7         for (j = 0; j < i; j++)
 8         {
 9             if (A[j] > A[j + 1])
10             {
11                 swap(&A[j], &A[j + 1]);
12                 flag = 1;                //标识发生了交换
13             }
14         }
15         if (flag == 0) break;        //全称无交换
16     }
17 }

或者是

 1 void Bubble_sort(ElementType A[], int N)
 2 {
 3     int flag, i, j;
 4     for (i = 0; i < N - 1; i++)
 5     for (j = 0; j < N - i - 1; j++)
 6     {
 7         if (A[j] > A[j + 1])
 8             swap(&A[j], &A[j + 1]);
 9     }
10 
11 }

算法复杂度：
最好情况：顺序 T = O(N)
最坏情况：逆序 T = O(N^2)

2.插入排序

 1 void Insertion_Sort(ElementType A[], int N)
 2 {
 3     int i, j;
 4     ElementType tmp;
 5     for (i = 1; i < N; i++)
 6     {
 7         tmp = A[i];
 8         for (j = i; j > 0 && A[j - 1] > tmp; j--)
 9             A[j] = A[j - 1];
10         A[j] = tmp;
11     }
12 }

3.选择排序

 1 void _Sort(ElementType A[], int N)
 2 {
 3     int i, k, j;
 4     for (i = 0; i < N - 1; i++)
 5     {
 6         k = i;
 7         for (j = i; j < N; j++)
 8         {
 9             if (A[k]> A[j])
10                 k = j;
11         }
12         swap(&A[k], &A[i]);
13     }
14 }

4.希尔排序：如果增量元素不互质，则小增量可能根本不起作用，则增量的选取可以采用Hibbard或Sedgewick增量序列

 1 void Shell_sort(ElementType A[], int N)
 2 {
 3     int i, j, increament;
 4     ElementType temp;
 5     for (increament = N / 2; increament > 0; increament /= 2)
 6     {
 7         for (i = increament; i < N; i++)
 8         {
 9             temp = A[i];
10             for (j = i; j >= increament; j -= increament)
11             {
12                 if (A[j - increament] > temp)
13                     A[j] = A[j - increament];
14                 else
15                     break;
16             }
17 
18             A[j] = temp;
19         }
20     }
21 }

或：

 1 void Shell_sort(ElementType A[], int N)
 2 {
 3     int i, j, increament;
 4     ElementType temp;
 5     for (increament = N / 2; increament > 0; increament /= 2)
 6     {
 7         for (i = increament; i < N; i++)
 8         {
 9             temp = A[i];
10             for (j = i; j >= increament && A[j - increament] > temp; j -= increament)
11                 A[j] = A[j - increament];
12             A[j] = temp;
13         }
14     }
15 }

5.堆排序：
//将树调整成最大堆

 1 void PercDown(ElementType A[], int i, int N)
 2 {
 3     int child;
 4     ElementType temp;
 5     for (temp = A[i]; (2 * i + 1) < N; i = child)
 6     {
 7         child = 2 * i + 1;
 8         if (child != N - 1 && A[child] < A[child + 1])
 9             child++;
10         if (temp > A[child])
11             break;
12         else
13             A[i] = A[child];
14     }
15     A[i] = temp;
16 }
17 
18 void Heap_sort(ElementType A[], int N)
19 {
20     int i;
21     for (i = N / 2; i >= 0; i--)        //BuildHeap
22         PercDown(A, i, N);
23     for (i = 0; i < N - 1; i++)            //DeleteMax
24     {
25         swap(&A[0], &A[N - 1 - i]);
26         PercDown(A, 0, N - i - 1);
27     }
28 }
29 
30 DeleteMax还可以写成这样
31 for (i = N - 1; i > 0; i--)            //DeleteMax
32     {
33         swap(&A[0], &A[i]);
34         PercDown(A, 0, i);
35     }

6.1归并排序(递归实现）

 1 //Left = strart of left half, Right = start of right half, RightEnd = end of right half
 2 void Merge(ElementType A[], ElementType TmpArray[],
 3     int Left, int Right, int RightEnd)
 4 {
 5     int LeftEnd, SumNum, temp, i;
 6     temp = Left;
 7     LeftEnd = Right - 1;
 8     SumNum = RightEnd - Left + 1;
 9 
10     //main loop
11     while (Left <= LeftEnd && Right <= RightEnd)        
12     {
13         if (A[Left] < A[Right])
14             TmpArray[temp++] = A[Left++];
15         else
16             TmpArray[temp++] = A[Right++];
17     }
18     while (Left <= LeftEnd)                //copy rest of first half
19         TmpArray[temp++] = A[Left++];
20     while (Right <= RightEnd)            //copy rest of second half
21         TmpArray[temp++] = A[Right++];    
22 
23     for (i = 0; i < SumNum; i++, RightEnd--)        //copy TempArray back
24         A[RightEnd] = TmpArray[RightEnd];
25 }
26 
27 void MSort(ElementType A[], ElementType TmpArray[],
28     int Left, int Right)
29 {
30     int Center;
31     if (Left < Right)
32     {
33         Center = (Left + Right) / 2;
34         MSort(A, TmpArray, Left, Center);
35         MSort(A, TmpArray, Center + 1, Right);
36         Merge(A, TmpArray, Left, Center + 1, Right);
37     }
38 }
39 
40 void Merge_sort(ElementType A[], int N)
41 {
42     ElementType *TmpArray;
43     TmpArray = (ElementType*)malloc(N * sizeof(ElementType));
44     if (TmpArray != NULL)
45     {
46         MSort(A, TmpArray, 0, N - 1);
47         free(TmpArray);
48     }
49     else
50         printf("No space for tmpArray[ ]!!!
"); 
51 }

T = T(N/2) + T(N/2) + O(N) ----> T= O(NlogN);

6.2 归并排序（非递归实现）

 1 //Left = strart of left half, Right = start of right half, RightEnd = end of right half
 2 void Merge1(ElementType A[], ElementType TmpArray[],
 3     int Left, int Right, int RightEnd)
 4 {
 5     int LeftEnd, SumNum, temp;
 6     temp = Left;
 7     LeftEnd = Right - 1;
 8     SumNum = RightEnd - Left + 1;
 9 
10     //main loop
11     while (Left <= LeftEnd && Right <= RightEnd)        
12     {
13         if (A[Left] < A[Right])
14             TmpArray[temp++] = A[Left++];
15         else
16             TmpArray[temp++] = A[Right++];
17     }
18     while (Left <= LeftEnd)                //copy rest of first half
19         TmpArray[temp++] = A[Left++];
20     while (Right <= RightEnd)            //copy rest of second half
21         TmpArray[temp++] = A[Right++];    
22 }
23 
24 //非递归算法 length = 当前子序列长度， Merge1将A中的元素归并到TmpA
25 void Merge_pass(ElementType A[], ElementType TmpA[], int N, int length)
26 {
27     int i, j;
28     for (i = 0; i <= N - 2 * length; i += 2 *length)
29         Merge1(A, TmpA, i, i + length, i + 2 * length - 1);
30     if (i + length < N)        //归并最后两个子列
31         Merge1(A, TmpA, i, i + length, N - 1);
32     else
33     for (j = i; j < N; j++)        //最后只剩一个元素
34         TmpA[j] = A[j];
35 }
36 
37 void Merge_sort(ElementType A[], int N)
38 {
39     int length = 1;
40     ElementType *TmpA;
41     TmpA = (ElementType*)malloc(sizeof(ElementType) * N);
42     if (TmpA != NULL)
43     {
44         while (length < N)
45         {
46             Merge_pass(A, TmpA, N, length);
47             length *= 2;
48             Merge_pass(TmpA, A, N, length);
49             length *= 2;
50         }
51         free(TmpA);
52     }
53     else
54         printf("Run out of memory!!!
");
55 }

7.快速排序（也是分而治之）
最好情况：每次正好中分 T = O(NlogN)
选主元：
1.随机rand()函数不便宜
2.取头、中、尾的中位数
在程序中定义一个cutoff的阈值。当递归的数据规模充分小，则停止递归，直接调用简单排序（录入插入排序）
//选取主元

 1 ElementType Median3(ElementType A[], int Left, int Right)
 2 {
 3     int Center = (Left + Right) / 2;
 4     if (A[Left] > A[Center])
 5         swap(&A[Left], &A[Center]);
 6     if (A[Left] > A[Right])
 7         swap(&A[Left], &A[Right]);
 8     if (A[Center] > A[Right])
 9         swap(&A[Center], &A[Right]);
10 
11     swap(&A[Center], &A[Right] - 1);    //将pivot藏到右边
12     
13     //只需要考虑A[Left + 1]……A[Right - 2]
14     return A[Right - 1];    //返回pivot
15 }
16 
17 void Quicksort(ElementType A[], int Left, int Right)
18 {
19     int i, j;
20     ElementType pivot;
21     if (Cutoff <= Right - Left)
22     {
23         pivot = Median3(A, Left, Right);
24         i = Left, j = Right - 1;
25         for (;;)
26         {
27             while (A[++i] < pivot) {}
28             while (A[--j] > pivot) {}
29             if (i < j)
30                 swap(&A[i], &A[j]);
31             else
32                 break;
33         }
34         swap(&A[i], &A[Right - 1]);
35         Quicksort(A, Left, i - 1);
36         Quicksort(A, i + 1, Right);
37     }
38     else
39         Insertion_sort(A + Left, Right - Left + 1);
40 }
41 
42 
43 void Quick_sort(ElementType A[], int N)
44 {
45     Quicksort(A, 0, N - 1);
46 }

8.表排序
需要排序的每个元素很庞大（例如：结构体）
间接排序：
定义一个指针数组作为“表”（table)

例如在表排序中用插入排序：

 1 void table_sort(ElementType A[], int N)
 2 {
 3     int i, j;
 4     int table[N];
 5     ElementType temp;
 6     for(i = 0; i < N; i++)
 7         table[i] = i;
 8     for (i = 1; i < N; i++)
 9     {
10         temp = table[i];
11         for (j = i; j > 0 && A[table[j - 1]] > temp; j--)
12             table[j] = table[j - 1];
13         table[j] = temp;
14     }
15 }

9.物理排序
N个数字的排列由若干个独立的环组成

10.桶排序
T(N, M) = O(M + N)

11.基数排序
次位优先

排序算法的比较