网站的建设与维护需要资质吗,个人全屏网站模板,ppt免费下载模板网站,网推公司怎么收费原文地址#xff1a;https://www.jianshu.com/p/916b15eae350 常见排序算法的总结 - 复杂度、实现和稳定性 2018.08.29 16:20* 最基础的算法问题#xff0c;温故知新。排序算法的几个主要指标是#xff0c;时间复杂度#xff08;最好#xff0c;最差和平均#xff09;https://www.jianshu.com/p/916b15eae350 常见排序算法的总结 - 复杂度、实现和稳定性 2018.08.29 16:20* 最基础的算法问题温故知新。排序算法的几个主要指标是时间复杂度最好最差和平均空间复杂度额外空间和稳定性。本文主要描述八种常见算法简单选择排序、冒泡排序、简单插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序关于它们的指标统计可以直接看最后。本文均为基本C实现不使用STL库。 值得一提的是排序算法的稳定性之前关注较少。稳定性的意思是对于序列中键值Key value相同的元素它们在排序前后的相对关系保持不变。对于int这样的基本数据类型稳定性基本上是没有意义的因为它的键值就是元素本身两个元素的键值相同他们就可以被认为是相同的。但对于复杂的数据类型数据的键值相同数据不一定相同比如一个Student类包括Name和Score两个属性以Score为键值排序这时候键值相同元素间的相对关系就有意义了。 简单选择排序 应该是最自然的思路。选择排序的思想是从全部序列中选取最小的与第0个元素交换然后从第1个元素往后找出最小的与第一个元素交换再从第2个元素往后选取最小的与第2个元素交换直到选取最后一个元素。 void selectionSort(int a[], int n) {for (int i 0; i n - 1; i) {int minIdx i;for (int j i 1; j n; j) {if (a[j] a[minIdx]) {minIdx j;}}int tmp a[i];a[i] a[minIdx];a[minIdx] tmp;}
}无论如何都要完整地执行内外两重循环故最好、最差和平均时间复杂度都是O(n2)不需要额外空间。选择排序是不稳定的。 冒泡排序 冒泡排序的思想是从第0个元素到第n-1个元素遍历若前面一个元素大于后面一个元素则交换两个元素这样可将整个序列中最大的元素冒泡到最后然后再从第0个到第n-2遍历如此往复直到只剩一个元素。 void bubbleSort(int a[], int n) {for (int i 0; i n - 1; i) {for (int j 0; j n - i - 1; j) {if (a[j] a[j 1]) {int tmp a[j];a[j] a[j 1];a[j 1] tmp;}}}
}冒泡排序与简单选择排序类似无论如何都要执行完两重循环故最好、最坏和平均时间复杂度均为O(n2)不需要额外空间。冒泡排序是稳定的。 冒泡排序的一个改进是在内层循环之前设置一个标记变量用于标记循环是否进行了交换在内层循环结束时若判断没有进行交换则说明剩下的序列中每个元素都小于等于后面一个元素即已经有序可终止循环。这样冒泡排序的最好时间复杂度可以提升到O(n)。 简单插入排序Insertion Sort 思路是类似扑克牌的排序每次从未排序序列的第一个元素插入到已排序序列中的合适位置。假设初始的有序序列为第0个元素本文描述的序号都从0开始只有一个元素的序列肯定是有序的然后从原先序列的第1个元素开始到第n-1个元素遍历每次将当前元素插入到它之前序列中的合适位置。 void insertionSortBSearch(int a[], n) {for (int i 1; i n; i) { int j, val a[i]; for (j i - 1; j 0 a[j] val; --j) {a[j 1] a[j];}a[j 1] val;}
}两重循环最差和平均时间复杂度为O(n2)最好情况是原序列已有序则忽略内层循环时间复杂度O(n)。插入排序是稳定的。 这里内层循环我们用的是从后向前遍历来找到合适的插入位置而内层循环所遍历的是已排序的数组所以我们可以使用二分查找来寻找插入位置从而使时间复杂度提高到O(n*log n)。代码如下。 // 二分查找改进的插入排序
void insertionSortBSearch(int a[], n) {for (int i 1; i n; i) { int j, val a[i]; int begin 0, end i - 1;while (begin end) {int mid begin (end - begin) / 2;if (a[mid] val) {end mid - 1;}else {begin mid;}}for (j i - 1; j begin; --j) {a[j 1] a[j];}a[begin] val;}
}希尔排序 希尔排序可以被认为是简单插入排序的一种改进。插入排序一个比较耗时的地方在于需要将元素反复后移因为它是以1为增量进行比较的元素的后移可能会进行多次。一个长度为n的序列以1为增量就是一个序列以2为增量就形成两个序列以i为增量就形成i个序列。希尔排序的思想是先以一个较大的增量将序列分成几个子序列将这几个子序列分别排序后合并在缩小增量进行同样的操作知道增量为1时序列已经基本有序这是进行简单插入排序的效率就会较高。希尔排序的维基词条上有一个比较好的解释例子如下 // 原始序列
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10
// 以5为增量划分5列每列即为一个子序列
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
// 对每一个子序列进行插入排序得到以下结果
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
// 恢复一行显示为
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45
// 再以3为增量划分3列每列即为一个子序列
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
// 对每一个子序列进行插入排序得到如下结果
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
// 恢复一行为
10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94
// 然后再以1为增量进行插入排序即简单插入排序
// 此时序列已经基本有序分布均匀需要反复后移的情况较少效率较高上面的例子中我们依次选取了5、3和1为增量实际中增量的选取并没有统一的规则唯一的要求就是最后一次迭代的增量需为1。最初的增量选取规则为从n/2折半递减直到1。还有一些关于希尔排序增量选取的研究针对不同数据有不同的表现在此不做展开。下面是增量从n/2折半递减到1的代码示例。 void shellSort(int a[], int n) {for (int step n / 2; step 0; step / 2) {for (int i step; i n; i) {int j, val a[i];for (j n - step; j 0 a[j] val; j - step) {a[j step] a[j];}a[j 1] val;}}
}希尔排序在简单插入排序的基础上做了些改进它的最好及最差时间复杂度和简单插入排序一样分别是是O(n)和O(n2)平均时间复杂度试增量选取规则而定一般认为介于O(n)和O(n2)之间。它不需要额外空间。它是不稳定的。 归并排序 归并排序的思想是利用二分的特性将序列分成两个子序列进行排序将排序后的两个子序列归并合并当序列的长度为2时它的两个子序列长度为1即视为有序可直接合并即达到归并排序的最小子状态。基于递归的实现如下 void mergeSortRecursive(int a[], int b[], int start, int end) {if (start end) {return;}int mid start (end - start) / 2,start1 start, end1 mid,start2 mid 1, end2 end;mergeSortRecursive(a, b, start1, end1);mergeSortRecursive(a, b, start2, end2);int i 0;while (start1 end1 start2 end2) {b[i] a[start1] a[start2] ? a[start1] : a[start2];}while (start1 end1) {b[i] a[start1];}while (start2 end2) {b[i] a[start2];}for (i start; i end; i) {a[i] b[i];}
}void mergeSort(int a[], int n) { int *b new int[n]; mergeSortRecursive(a, b, 0, n - 1); delete[] b; }
归并排序的最好最坏和平均时间复杂度都是O(n*logn)。但需要O(n)的辅助空间。归并排序是稳定的。
快速排序
快速排序可能是最常被提到的排序算法了快排的思想是选取第一个数为基准通过一次遍历将小于它的元素放到它的左侧将大于它的元素放到它的右侧然后对它的左右两个子序列分别递归地执行同样的操作。
void quickSortRecursive(int a[], int start, int end) {if (start end)return;int mid a[start];int left start 1, right end;while (left right) {while (a[left] mid left right)left;while (a[right] mid left right)--right;swap(a[left], a[right]);}if (a[left] a[start])swap(a[left], a[start]);else--left;if (left)quickSortRecursive(a, start, left - 1);quickSortRecursive(a, left 1, end);
}void quickSort(int a[], int n) { quickSortRecursive(a, 0, n - 1); }
快速排序利用分而治之的思想它的最好和平均实际复杂度为O(nlogn)但是如果选取基准的规则正好与实际数值分布相反例如我们选取第一个数为基准而原始序列是倒序的那么每一轮循环快排都只能把基准放到最右侧故快排的最差时间复杂度为O(n2)。快排算法本身没有用到额外的空间可以说需要的空间为O(1)对于递归实现也可以说需要的空间是O(n)因为在递归调用时有栈的开销当然最坏情况是O(n)平均情况是O(logn)。快速排序是不稳定的。
堆排序
堆排序利用的是二叉树的思想所谓堆就是一个完全二叉树完全二叉树的意思就是除了叶子节点其它所有节点都有两个子节点这样子的话完全二叉树就可以用一个一块连续的内存空间数组来存储而不需要指针操作了。堆排序分两个流程首先是构建大顶堆然后是从大顶堆中获取按逆序提取元素。 首先是大顶堆大顶堆即一个完全二叉树的每一个节点都大于它的所有子节点。大顶堆可以按照从上到下从左到右的顺序用数组来存储第i个节点的父节点序号为(i-1)/2左子节点序号为2i1右子节点序号为2(i1)。构建大顶堆的过程即从后向前遍历所有非叶子节点若它小于左右子节点则与左右子节点中最大的交换然后递归地对原最大节点做同样的操作。下面是一个较好的示意图来自bubkoo 构建大顶堆示意图 构建完大顶堆后我们需要按逆序提取元素从而获得一个递增的序列。首先将根节点和最后一个节点交换这样最大的元素就放到最后了然后我们更新大顶堆再次将新的大顶堆根节点和倒数第二个节点交换如此循环直到只剩一个节点此时整个序列有序。下面是一个较好的示意图来自
bubkoo从大顶堆逆序提取元素使其有序示意图 void updateHeap(int a[], int i, int n) {int iMax i,iLeft 2 * i 1,iRight 2 * (i 1);if (iLeft n a[iMax] a[iLeft]) {iMax iLeft;}if (iRight n a[iMax] a[iRight]) {iMax iRight;}if (iMax ! i) {int tmp a[iMax];a[iMax] a[i];a[i] tmp;updateHeap(a, iMax, n);}
}void heapSort(int a[], int n) { for (int i (n - 1) / 2; i 0; i–) { updateHeap(a, i, n); } for (int i n - 1; i 0; --i) { int tmp a[i]; a[i] a[0]; a[0] tmp; updateHeap(a, i, n); } }
堆排序的整个过程中充分利用的二分思想它的最好、最坏和平均时间复杂度都是O(nlogn)。堆排序不需要额外的空间。堆排序的交换过程不连续显然是不稳定的。
基数排序
基数排序是一种典型的空间换时间的排序方法。以正整数为例将所有待比较数值统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位个位排序一直到最高位排序完成以后数列就变成一个有序序列。 对正整数我们常以10为基数每一位可以为0到9对于其它数据类型如字符串我们可以进一步拓展基数基数越大越占空间但时间更快如果有一段足够长的内存空间也就是说基数为无穷大那就足够表示所有出现的数值我们就可以通过一次遍历就实现排序当然实现上这是不可能的对已知输入范围的数据是可能的而且非常有用的可以用这种思想来模拟一个简单的hash函数。
int maxBit(int a[], int n)
{int maxData a[0]; for (int i 1; i n; i){if (maxData a[i]) {maxData a[i];} }int d 1;int p 10;while (maxData p){maxData / 10;d;}return d;
}
void radixsort(int a[], int n)
{int d maxBit(a, n);int *tmp new int[n];int *count new int[10];int i, j, k;int radix 1;for (i 1; i d; i, radix * 10){for (j 0; j 10; j) {count[j] 0;} for (j 0; j n; j){k (a[j] / radix) % 10;count[k];}for (j 1; j 10; j) {count[j] count[j - 1] count[j];} for (j n - 1; j 0; j--){k (a[j] / radix) % 10;tmp[count[k] - 1] a[j];count[k]--;}for (j 0; j n; j) {a[j] tmp[j];}}delete[]tmp;delete[]count;
}基数排序的最好最好、最坏和平均时间复杂度都是O(n*k)其中n是数据大小k是所选基数。它需要O(nk)的额外空间。它是稳定的。
八种排序算法总结
上面介绍了最常提到的八种排序算法最基础的是选择和插入基于选择和插入分别改进出了冒泡和希尔。基于二分思想又提出了归并、快排和堆排序。最后基于数据的分布特征提出了基数排序。这些排序算法的主要指标总结如下。
算法最好时间最坏时间平均时间额外空间稳定性选择n2 n2 n2 1不稳定冒泡nn2 n2 1稳定插入nn2 n2 1稳定希尔nn2 n1.3(不确定) 1不稳定归并nlog2nnlog2nnlog2nn稳定快排nlog2nn2 nlog2nlog2n至n不稳定堆nlog2nnlog2nnlog2n1不稳定基数n*kn*kn*knk稳定
参考
排序算法时间复杂度https://www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/ 排序算法稳定性https://www.geeksforgeeks.org/stability-in-sorting-algorithms/ /div/div
/div
