排序算法总结(通用4篇)

排序算法总结 第1篇

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

排序算法总结 第2篇

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(_n_2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法步骤如下：

排序算法总结 第3篇

另外，橘黄色封面那本外国人写的《算法》第四版中，第五章字符串，键索引计数法，就是计数排序的一种，思想跟这是类似的，实现上有细微差别。 

算法基本思想：

计数排序 的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

实现步骤：

以数组A = {101,109,107,103,108,102,103,110,107,103}为例。

第一步：找出数组中的最大值max、最小值min。

第二步：创建一个新数组count，其长度是max-min加1，其元素默认值都为0。

第三步：遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。

第四步：对count数组变形，新元素的值是前面元素累加之和的值，即count[i+1] = count[i+1] + count[i];。

第五步：创建结果数组result，长度和原始数组一样。

第六步：遍历原始数组中的元素，当前元素A[j]减去最小值min，作为索引，在计数数组中找到对应的元素值count[A[j]-min]，再将count[A[j]-min]的值减去1，就是A[j]在结果数组result中的位置，做完上述这些操作，count[A[j]-min]自减1。

是不是对第四步和第六步有疑问？为什么要这样操作？

第四步操作，是让计数数组count存储的元素值，等于原始数组中相应整数的最终排序位置，即计算原始数组中的每个数字在结果数组中处于的位置。

比如索引值为9的count[9]，它的元素值为10，而索引9对应的原始数组A中的元素为9+101=110（要补上最小值min，才能还原），即110在排序后的位置是第10位，即result[9] = 110，排完后count[9]的值需要减1，count[9]变为9。

再比如索引值为6的count[6]，他的元素值为7，而索引6对应的原始数组A中的元素为6+101=107，即107在排序后的位置是第7位，即result[6] = 107，排完后count[6]的值需要减1，count[6]变为6。

如果索引值继续为6，在经过上一次的排序后，count[6]的值变成了6，即107在排序后的位置是第6位，即result[5] = 107，排完后count[6]的值需要减1，count[6]变为5。

至于第六步操作，就是为了找到A中的当前元素在结果数组result中排第几位，也就达到了排序的目的。

实现代码：

算法分析：

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

排序算法总结 第4篇

基数排序是一种基于非比较的整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个不同数位分别比较。原始基数排序的算法思想是将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后从最低位开始依次进行一次排序。直到所有数据有序。基数排序时间复杂度为O(n×k)，其中n为数据个数，k为数据位数。主要分为两种实现方法MSD（最高位优先）和LSD（最低位优先）。

平均时间复杂度为O(n×k)，空间复杂度为O(n+k)，是一种稳定的排序算法。