【算法】排序算法性能比较
内农大计算机院戳上面的蓝字关注我们哦！所谓排序，即将原来无序的一个序列重新排列成有序的序列。排序方法中涉...
戳上面的蓝字关注我们哦！
排序方法中涉及到稳定性，所谓稳定性，是指待排序的序列中有两个或两个以上相同的项，在排序前和排序后看这些相同项的相对位置有没有发生变化，如果没有发生变化，即该排序方法是稳定的，如果发生变化，则说明该排序方法是不稳定的。
如果记录中关键字不能重复，则排序结果是唯一的，那么选择的排序方法稳定与否就无关紧要了；如果关键字可以重复，则在选择排序方法时，就要根据具体的需求来考虑选择稳定还是不稳定的排序方法。那么，哪些排序算法是不稳定的呢？
“快些选堆”：其中“快”指快速排序，“些”指希尔排序，“选”指选择排序，“堆”指堆排序，即这四种排序方法是不稳定的，其他自然都是稳定的。
排序算法分类
1、插入类排序
即在一个已经有序的序列中，插入一个新的记录，就好比军训排队，已经排好一个纵队，这时来了个新家伙，于是新来的“插入”这个队伍中的合适位置。这类排序有：直接插入排序、折半插入排序、希尔排序。
2、交换类排序
该类方法的核心是“交换”，即每趟排序，都是通过一系列的“交换”动作完成的，如军训排队时，教官说：你比旁边的高，你俩交换下，还比下一个高就继续交换。这类排序有：冒泡排序、快速排序。
3、选择类排序
该方法的核心是“选择”，即每趟排序都选出一个最小（或最大）的记录，把它和序列中的第一个（或最后一个）记录交换，这样最小（或最大）的记录到位。如军训排队时，教官选出个子最小的同学，让他和第一个位置的同学交换，剩下的继续选择。这类排序有：选择排序、堆排序。
4、归并类排序
所谓归并，就是将两个或两个以上的有序序列合并成一个新的有序序列。如军训排队时，教官说：每个人先和旁边的人组成二人组，组内排好队，二人组和旁边的二人组组成四人组，内部再排好队，以此类推，直到最后全部同学都归并到一个组中并排好序。这类排序有：（二路）归并排序。
5、基数类排序
此类方法较为特别，是基于多关键字排序的思想，把一个逻辑关键字拆分成多个关键字，如一副扑克牌，按照基数排序思想可以先按花色排序，则分成4堆，每堆再按A-K的顺序排序，使得整副扑克牌最终有序。
即在一个已经有序的序列中，插入一个新的记录，就好比军训排队，已经排好一个纵队，这时来了个新家伙，于是新来的“插入”这个队伍中的合适位置。这类排序有：直接插入排序、折半插入排序、希尔排序。
2、交换类排序
该类方法的核心是“交换”，即每趟排序，都是通过一系列的“交换”动作完成的，如军训排队时，教官说：你比旁边的高，你俩交换下，还比下一个高就继续交换。这类排序有：冒泡排序、快速排序。
3、选择类排序
该方法的核心是“选择”，即每趟排序都选出一个最小（或最大）的记录，把它和序列中的第一个（或最后一个）记录交换，这样最小（或最大）的记录到位。如军训排队时，教官选出个子最小的同学，让他和第一个位置的同学交换，剩下的继续选择。这类排序有：选择排序、堆排序。
4、归并类排序
所谓归并，就是将两个或两个以上的有序序列合并成一个新的有序序列。如军训排队时，教官说：每个人先和旁边的人组成二人组，组内排好队，二人组和旁边的二人组组成四人组，内部再排好队，以此类推，直到最后全部同学都归并到一个组中并排好序。这类排序有：（二路）归并排序。
5、基数类排序
此类方法较为特别，是基于多关键字排序的思想，把一个逻辑关键字拆分成多个关键字，如一副扑克牌，按照基数排序思想可以先按花色排序，则分成4堆，每堆再按A-K的顺序排序，使得整副扑克牌最终有序。
排序算法分析
本文主要分析的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序。
交换算法
由于大部分排序算法中使用到两个记录相互交换的动作，因此将交换动作单独封装出来，便于各排序算法使用。
//交换函数
Array.prototype.swap = function(i, j) {
var temp = this;
this = this[j];
this[j] = temp;
}
插入排序
算法思想：每趟将一个待排序的关键字，按照其关键字值的大小插入到已经排好的部分序列的适当位置上，直到插入完成。
//插入排序
Array.prototype.insertionSort = function() {
for (var i = 1; i < this.length; ++i)
{
var j = i,
value = this;
while (j > 0 && this[j - 1] > value)
{
this[j] = this[j - 1];
--j;
}
this[j] = value;
}
}
算法性能：在内层循环中this[j]=this[j-1]，这句是作为基本操作。考虑最坏情况，即整个序列是逆序的，则其基本操作总的执行次数为n*(n-1)/2，其时间复杂度为O(n*n)。考虑最好情况，即整个序列已经有序，则循环内的操作均为常量级，其时间复杂度为O(n)。因此本算法平均时间复杂度为O(n*n)。算法所需的额外空间只有一个value，因此空间复杂度为O(1)。
希尔排序
算法思想：希尔排序又叫做缩小增量排序，是将待排序的序列按某种规则分成几个子序列，分别对这几个子序列进行插入排序，其中这一规则就是增量。如可以使用增量5、3、1来分格序列，且每一趟希尔排序的增量都是逐渐缩小的，希尔排序的每趟排序都会使得整个序列变得更加有序，等整个序列基本有序了，再使用一趟插入排序，这样会更有效率，这就是希尔排序的思想。
//希尔排序Array.prototype.shellSort = function() {
for (var step = this.length >> 1; step > 0; step >>= 1)
{
for (var i = 0; i < step; ++i)
{
for (var j = i + step; j < this.length; j += step)
{
var k = j, value = this[j];
while (k >= step && this[k - step] > value)
{
this[k] = this[k - step];
k -= step;
}
this[k] = value;
}
}
}
}
算法性能：希尔排序的时间复杂度平均情况为O(nlogn)，空间复杂度为O(1)。希尔排序的增量取法要注意，首先增量序列的最后一个值一定是1，其次增量序列中的值没有除1之外的公因子，如8，4，2，1这样的序列就不要取（有公因子2）。
冒泡排序
算法思想：通过一系列的“交换”动作完成的，首先第一个记录与第二个记录比较，如果第一个大，则二者交换，否则不交换；然后第二个记录和第三个记录比较，如果第二个大，则二者交换，否则不交换，以此类推，最终最大的那个记录被交换到了最后，一趟冒泡排序完成。在这个过程中，大的记录就像一块石头一样沉底，小的记录逐渐向上浮动。冒泡排序算法结束的条件是一趟排序没有发生元素交换。
//冒泡排序Array.prototype.bubbleSort = function() {
for (var i = this.length - 1; i > 0; --i)
{
for (var j = 0; j < i; ++j)
if (this[j] > this[j + 1])
this.swap(j, j + 1);
}
}
算法性能：最内层循环的元素交换操作是算法的基本操作。最坏情况，待排序列逆序，则基本操作的总执行次数为(n-1+1)*(n-1)/2=n(n-1)/2，其时间复杂度为O(n*n)；最好情况，待排序列有序，则时间复杂度为O(n)，因此平均情况下的时间复杂度为O(n*n)。算法的额外辅助空间只有一个用于交换的temp，所以空间复杂度为O(1)。
快速排序
算法思想：以军训排队为例，教官说以第一个同学为中心，比他矮的站他左边，比他高的站他右边，这就是一趟快速排序。因此，一趟快速排序是以一个枢轴，将序列分成两部分，枢轴的一边比它小（或小于等于），另一边比它大（或大于等于）。
//递归快速排序Array.prototype.quickSort = function(s, e) {
if (s == null)
s = 0;
if (e == null)
e = this.length - 1;
if (s >= e)
return;
this.swap((s + e) >> 1, e);
var index = s - 1;
for (var i = s; i
1; k >= 0; j = k, k = (k - 1) >> 1)
{
if (this[k] >= this[j])
break;
this.swap(j, k);
}
}
for (var i = this.length - 1; i > 0; --i)
{
this.swap(0, i);
for (var j = 0, k = (j + 1)
关注 内农大计算机院
微信扫一扫关注公众号
