假设\(K_i=K_j (1 \leq i \leq n,1 \leq j
\leq n,i \neq j)\) ,且在排序前的序列中\(R_i\) 领先于\(R_j\) (即i<j)。若在排序后的序列中\(R_i\) 仍领先于\(R_j\) ,则称所用的排序方法是稳定的;反之,若可能使排序后的序列中Rj领先于Ri,则称所用的排序方法是不稳定的
1 2 3 4 5 6 7 8 9 10 11 #define MAXSIZE 20 typedef int KeyTypetypedef struct { } InfoTypetypedef struct { KeyType key; InfoType otherinfo; }RedType; typedef struct { RedType r[MAXSIZE+1 ]; int length; }SqList;
插入排序
每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止
直接插入排序
将一条记录插入到已排好序的有序表中,从而得到一个新的、记录数量增1的有序表
时间复杂度: \(O(n^2)\)
空间复杂度: \(O(1)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void InsertSort (SqList *L) { for (int i = 2 ; i <= L.length; i++) { if (L.r[i].key < L.r[i-1 ].key) { L.r[0 ] = L.r[i]; L.r[i] = L.r[i-1 ]; for (int j = i - 2 ; L.r[0 ].key < L.r[j].key; j++) { L.r[j+1 ] = L.r[j]; } L.r[j+1 ] = L.r[0 ]; } } }
折半插入排序
时间复杂度: \(O(n^2)\)
空间复杂度: \(O(1)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 void BInsertSort (SqList *L) { for (int i=2 ;i<=L.length;i++) { L.r[0 ] = L.r[i]; int low=1 ; high=i-1 ; while (low <= high) { int m = (low + high) / 2 ; if (L.r[0 ].key < L.r[m].key) { high = m -1 ; } else { low = m + 1 ; } } for (int j=i-1 ;j>=high+1 ;j--) { L.r[j+1 ] = L.r[j]; } L.r[high+1 ] = L.r[0 ]; } }
希尔排序(缩小增量排序)
时间复杂度: 当增量序列为\(dt[k]=2^{t−k+1}−1\) 时,希尔排序的时间复杂度为\(O(n^{3/2})\) ,其中t为排序趟数, \(1 \leq k \leq t \leq \lfloor log_2{(n+1)}
\rfloor\) 。还有人在大量的实验基础上推出:当n在某个特定范围内,希尔排序所需的比较和移动次数约为\(n^{1.3}\) ,当n→∞时,可减少到\(n(log_2n)^2\) 。
空间复杂度: \(O(1)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 void ShellInsert (SqList *L, int dk) { for (int i=dk+1 ; i <=L.length; i++) { if (L.r[i].key < L.r[i-dk].key) { int j=0 ; L.r[0 ] = L.r[i]; for (j=i-dk; j>0 &&L.r[0 ].key<L.r[j].key; j-=dk) { L.r[j+dk] = L.r[j]; } L.r[j+dk] = L.r[0 ]; } } } void ShellSort (SqList *L, int dt[], int t) { for (int k=0 ; k<t; k++) { ShellInsert(L, dt[k]); } }
交换排序
冒泡排序
时间复杂度: \(O(n^2)\)
空间复杂度: \(O(1)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 void BubbleSort (SqList *L) { int m = L.length-1 ; int flag = 1 ; while (m>0 &&flag==1 ) { flag = 0 ; for (int j=1 ; j<=m; j++) { if (L.r[j].key > L.r[j+1 ].key) { flag = 1 ; RedType t = L.r[j]; L.r[j] = L.r[j+1 ]; L.r[j+1 ] = t; } m--; } } }
快速排序
快速排序是由冒泡排序改进而得到的。在冒泡排序过程中,只有相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序,如果通过两个(不相邻)记录的一次交换,消除多个逆序,则会大大加快排序的速度
时间复杂度\(O(nlog_2n)\)
空间复杂度\(O(log_2n) \to
O(n)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 int Partition (SqList *L, int low, int high) { L.r[0 ] = L.r[low]; KeyType pivotkey = L.r[low].key; while (low < high) { while (low<high && L.r[high].key >= pivotkey) --high; L.r[low] = L.r[high]; while (low<high && L.r[high].key <= pivotkey) ++low; L.r[high] = L.r[low]; } L.r[low] = L.r[0 ]; return low; } void QSort (SqList *L, int low, ing high) { if (low < high) { KeyType pivotkey = Partition(L, low, high); Qsort(L, low, pivotkey-1 ); Qsort(L, pivotkey, high); } } void QuickSort (SqList *L) { QSort(L, 1 , L.length); }
选择排序
每一趟从待排序的记录中选择关键字最小的记录,按顺序放在已排序的记录序列的最后,直到全部排完为止
简单选择排序
时间复杂度 \(O(n^2)\)
空间复杂度 \(O(1)\)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void SelectSort (SqList *L) { for (int i=1 ; i<L.length; i++) { int k = i; for (int j=i+1 ; j<=L.length; j++) { if (L.r[j].key < L.r[k].key) k = j; } if (k != i) { int t = L.r[i]; L.r[i] = L.r[k]; L.r[k] = L.r[t]; } } }
堆排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 void HeapAdjust (SqList *L, int s, int m) { RedType rc = L.r[s]; for (int j=2 *s; j<=m; j++) { if (j<m&&L.r[j].key < L.r[j+1 ].key) ++j; if (rc.key >= L.r[j].key) break ; L.r[s] = L.r[j]; s = j; } L.r[s] = rc; } void CreateHeap (SqList *L) { int n = L.length; for (int i=n/2 ; i>0 ; i--) { HeadAdjust(L, i, n); } } void HeapSort (SqList *L) { CreateHeap(L); for (int i=L.length; i>1 ; i--) { RedType x = L.r[1 ]; L.r[1 ] = L.r[i]; L.r[i] = x; } HeapAdjust(L, 1 , i-1 ); }