简单排序（前三种就是简单排序）
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[ ]!!!\n"); 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!!!\n"); 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.基数排序
次位优先
排序算法的比较
