所谓排序就是将一个原始的无序序列重新排列成有序序列。稳定性涉及排序方法。所谓稳定性，就是待排序的序列中有两个或两个以上相同的项。查看这些相同物品在排序前后的相对位置是否发生了变化。如果没有变化，则排序方式稳定；如果改变，则排序方法不稳定。如果记录中的关键词不能重复，则排序结果是唯一的，所以选择的排序方式是否稳定无关紧要；如果关键字可以重复，在选择排序方式时，需要根据具体需要考虑选择稳定或不稳定的排序方式。那么，哪些排序算法是不稳定的呢？“快速选择堆”：其中“快速”是指快速排序，“一些”是指希尔排序，“选择”是指选择性排序，“堆”是指堆排序，即这四种排序方式是不稳定的，而其他人自然是稳定的。排序算法分类1、插入排序就是在一个已经排好序的序列中插入一条新记录，就像军训排队一样。一列已经排好了。这时，来了一个新人，于是新“插手”在这支队伍中得到了合适的位置。这类排序有：直接插入排序、二分插入排序、希尔排序。2、交换排序这类方法的核心是“交换”，即每次排序都是通过一系列“交换”动作完成的。比如军训排队的时候，教官说：你比旁边一个高，你们两个交换，如果比旁边一个高，就继续交换。这样的排序是：冒泡排序，快速排序。3、选择排序该方法的核心是“选择”，即每次排序选择一个最小的（或***）记录，将其与序列中的第一条（或最后一条）记录进行交换，使最小的（或***)记录到位。比如军训排队的时候，教官选出个子最小的学生，让他和排在第一位的学生交换，剩下的继续选。这样的排序有：选择排序、堆排序。4.归并排序所谓归并就是将两个或多个有序序列组合成一个新的有序序列。比如军训排队的时候，教官说：大家先和旁边的人组成二人组，在组里排队，二人组和旁边的二人组形成一个四人一组，然后在里面排队，等等。直到***所有的同学都归为一组，并进行排序。这样的排序是：（双向）归并排序。5.基数排序这种方法比较特殊。它基于多关键词排序的思想。它将逻辑关键字拆分为多个关键字。例如，一副扑克牌可以按照基数排序思路按花色排序，然后分成4堆，每堆按A-K的顺序排序，这样整副扑克牌最终就有序了。排序算法分析本文主要分析的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序。交换算法由于大多数排序算法都使用交换两条记录的动作，因此将交换动作单独封装，以方便各个排序算法的使用。//交换函数Array.prototype.swap=function(i,j){vartemp=this[i];this[i]=this[j];this[j]=temp;}插入排序算法思想：每行将将一个待排序的键，根据其键值的大小，插入到已排序的部分序列的合适位置，直到插入完成。//插入排序Array.prototype.insertionSort=function(){for(vari=1;i0&&this[j-1]>value){this[j]=this[j-1];--j;}this[j]=value;}}算法性能：this[j]=this[j-1intheinnerloop]，这句话作为一个基本操作。考虑到最坏情况，即整个序列倒序，其基本操作的总执行次数为n*(n-1)/2，其时间复杂度为O(n*n)。考虑***情况，即整个序列已经有序，那么循环中的操作都是常量级的，其时间复杂度为O(n)。因此，该算法的平均时间复杂度为O(n*n)。该算法额外需要的空间只有一个值，所以空间复杂度为O(1)。希尔排序算法的思想：希尔排序也叫收缩增量排序。它把待排序的序列按照一定的规则分成若干个子序列，分别对这些子序列进行插入排序。规则是增量。例如可以用5、3、1的增量来划分网格序列，每次希尔排序的增量逐渐减小。每进行一次希尔排序，都会使整个序列更加有序，以此类推。顺序基本是有序的，换个插入排序效率会更高。这就是希尔排序的思想。//希尔排序Array.prototype.shellSort=function(){for(varstep=this.length>>1;step>0;step>>=1){for(vari=0;i=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(vari=this.length-1;i>0;--i){for(varj=0;jthis[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)。该算法的附加辅助空间只有一个临时交换空间，所以空间复杂度为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);varindex=s-1;for(vari=s;i<=e;++i)if(this[i]<=this[e])this.swap(i,++index);this.quickSort(s,index-1);this.quickSort(index+1,e);}算法性能：快速排序时的时间复杂度***为O(nlogn)，待排序序列越接近无序，算法效率越高，最坏情况下时间复杂度为O(n*n)，越接近待排序序列，则该算法效率较低，算法的平均时间复杂度为O(nlogn)。就平均时间而言，快速排序是所有排序算法中最快的。该算法的空间复杂度为O(logn)。快速排序是递归进行的，需要栈的辅助，因此比以前的排序方式需要更多的辅助空间。快速排序的效率与选择的“枢轴”有关。所选主元越接近中值，算法效率越高。所以，为了提高算法效率，可以在第一次选择“pivot”的时候做文章，比如在数据堆中随机选择3个值，取3个值的平均值作为“枢轴”，就像抽样一样。关于如何提高快速排序算法的效率，本文不做详细介绍，就此打住。（有兴趣的读者可以自己研究）选择排序算法的思想：该算法的主要动作是“选择”，它使用一种简单的选择方法从头到尾扫描序列以找到最小的记录，并且首先交换记录，然后从剩余的记录中继续进行这种选择和交换，最终使序列有序。//选择排序Array.prototype.selectionSort=function(){for(vari=0;i>1;k>=0;j=k,k=(k-1)>>1){if(this[k]>=this[j])break;this.swap(j,k);}}for(vari=this.length-1;i>0;--i){this.swap(0,i);for(varj=0,k=(j+1)<<1;k<=i;j=k,k=(k+1)<<1){if(k==i||this[k]=e)return;varm=(s+e)>>1;this.mergeSort(s,m,b);this.mergeSort(m+1,e,b);for(vari=s,j=s,k=m+1;i<=e;++i)b[i]=this[(k>e||j<=m&&this[j]
