排序算法适用性和稳定性总结排序算法适用性和稳定性总结

文章图片

适合顺序结构的是：折半插入排序、希尔排序、快速排序、堆排序
适合链式结构的是：直接插入排序、归并排序
不稳定：快速排序、希尔排序、堆排序/选择排序。
稳定：冒泡排序、插入排序、归并排序、基数排序。

文章图片

一、冒泡（Bubble）排序稳定

void Sort() { bool flag = 1; for (int i = 1; i < n && flag; i++) { flag = 0; for (int j = 0; j < n - i; j++) { if (num[j] > num[j + 1]) { swap(num[j], num[j + 1]); flag = 1; } } } }

效率 O（n2）,适用于排序小列表。
在相邻数字相同时不交换，就会保证稳定性。
【排序算法适用性和稳定性总结】
二、插入排序适用基本有序稳定

void Sort() { for (int i = 1; i < n; i++) { int temp = num[i]; int j = i - 1; while (j >= 0 && num[j] > temp) { //优化为二分查找位置 num[j + 1] = num[j]; j--; } num[j + 1] = temp; } }

最佳效率O（n）；最糟效率O（n2）与冒泡、选择相同，适用于排序小列表，若列表基本有序，则插入排序比冒泡、选择更有效率。
插入到相等元素的后面，保证稳定性。

三、希尔排序增量插入不稳定

void Sort() { for (int incr = 5; incr; incr--) { //步长递减 for (int L = 0; L < incr; L++) { for (int i = L + incr; i < n; i += incr) { //对每个子列表应用插入排序 int temp = num[i]; int j = i - incr; while (j >= 0 && num[j] > temp) { num[j + incr] = num[j]; j -= incr; } num[j + incr] = temp; } } } }

适用于排序小列表。
效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。
Shell 排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。
虽然单次插入排序是稳定的，但是在不同的插入过程中，相同元素会被打乱，不能保证稳定性。

四、归并排序（外部排序）稳定
待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。
可用于nlogn求逆序数：当 num[i] > num[j] num[j]可以与前面一组mid - i 个都可以组成逆序对。

void Sort(int low, int high) { if (low >= high) return; int i, j, k; int mid = (low + high) / 2; Sort(low, mid); Sort(mid + 1, high); int temp[MAXN]; for (i = low, j = mid + 1, k = 0; i <= mid && j <= high; k++) { if (num[i] <= num[j]) { temp[k] = num[i]; i++; } else { temp[k] = num[j]; j++; } } for (; j <= high; j++) temp[k++] = num[j]; for (; i <= mid; i++) temp[k++] = num[i]; for (k = 0; k < high - low + 1; k++) num[low + k] = temp[k]; }

效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异，适用于排序大列表，基于分治法。
合并过程中保证如果两个数组比较元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。

五、快速排序不稳定
快排每次找到一个中间位置就是数组第n大的数，可以被用于对无序数组第K个元素的查找。

int Partition(int low, int high) { int stan = num[low]; while (low < high) { while (low < high && num[high] >= stan) high--; num[low] = num[high]; while (low < high && num[low] <= stan) low++; num[high] = num[low]; } num[low] = stan; return low; //返回中间元素所在的位置 } void Sort(int low, int high) { if (low < high) { int n = Partition(low, high); Sort(low, n); Sort(n + 1, high); } }

平均效率O（nlogn），适用于排序大列表。
此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n2）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。基于分治法。
在找到第n大位置的时候，会破坏稳定性。

六、堆排序（优化选择排序）不稳定
最大堆：后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字，此时位于堆顶的节点的关键字是整个序列中最大的。

示例代码为对从1到n的数组排序
复杂度与数组原来混乱程度无关。
建堆：从最后一个非叶子节点n/2自下而上的建堆。
堆排序：一个堆从中取出堆顶，再把堆大小-1再次调整成堆。

void HeapAdjust(int i, int size) { int lchild = 2 * i; int rchild = 2 * i + 1; int Max = i; if (i <= size / 2) { //如果i是叶节点就不用进行调整 if (lchild <= size && num[lchild] > num[Max]) { Max = lchild; } if (rchild <= size && num[rchild] > num[Max]) { Max = rchild; } if (Max != i) { swap(num[i], num[Max]); HeapAdjust(Max, size); //使Max为父节点的子树是堆 } } }void BuildHeap() { for (int i = n / 2; i >= 1; i--) {//非叶节点最大序号值为n/2 HeapAdjust(i, n); } } void Sort() { BuildHeap(); for (int i = n; i >= 1; i--) { swap(num[1], num[i]); //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面 HeapAdjust(1, i - 1); //重新调整堆顶节点成为大顶堆 } }

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1)。
选择排序就是不稳定的，堆优化也是不稳定的排序方法。

直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作，堆排序可通过树形结构保存部分比较结果，可减少比较次数。

七、基数排序稳定

前面所介绍的排序方法都是基于比较的排序；
而基数排序首先将待排序数据元素依次“分配”到不同的桶里，然后再把各桶中的数据元素“收集”到一起

实现方法：
1.最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列，适合递归。
2.最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列，适合循环。

int digital[] = { 1, 1, 10, 100, 1000, 10000 }; inline int get_d(int x, int d) { return ((x / digital[d]) % 10); //确定桶号 } int temp[MAXN]; int cnt[10]; void Sort(int begin, int end, int d) { memset(cnt, 0, sizeof(cnt)); //统计各桶需要装的元素的个数 for (int i = begin; i <= end; ++i) cnt[get_d(num[i], d)]++; for (int i = 1; i < 10; i++) cnt[i] = cnt[i] + cnt[i - 1]; //这里要从右向左扫描，保证排序稳定性 for (int i = end; i >= begin; i--) temp[--cnt[get_d(num[i], d)]] = num[i]; //cnt[j]-1是第j个桶的右边界索引 //此时cnt[i]为第i个桶左边界 for (int i = begin, j = 0; i <= end; i++) num[i] = temp[j++]; //对各桶中数据进行再排序 for (int i = 0; i < 10; i++) { int l = begin + cnt[i]; //左边界 int r = begin + cnt[i + 1] - 1; //右边界 if (r - l > 0 && d > 1) { Sort(l, r, d - 1); //对第i个桶基数排序，数位降 1 } } }int main() { freopen("data_tmp.txt", "r", stdin); scanf("%d", &n); int Max = -0x3fffffff, Max_d; for (int i = 0; i < n; i++) { scanf("%d", &num[i]); Max = max(Max, abs(num[i])); } if (Max < 10) Max_d = 1; else Max_d = (int) log10(Max) + 1; Sort(0, n - 1, Max_d); for (int i = 0; i < n; i++) { printf("%d ", num[i]); } return 0; }

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。

转载于:https://www.cnblogs.com/updateofsimon/p/3450556.html