排序算法总结
作者：桂志宏
在实际生活中，我们常常会看到各种基于排序的场景，譬如在网上买衣服，可以选择按照衣服价格递增的顺序来浏览商品，或者在某个app听音乐时，可以按照歌手姓氏递增的顺序来浏览歌曲信息等等，因此对排序算法的学习是非常重要的，尽管现在很多系统都已经实现了各种排序算法，不用我们自己去实现，只用调用相应的API或方法，但是我们仍然需要学习排序算法，这样当我们碰到不同的问题就知道应该选择什么排序算法比较合适，因此这里非常有必要对几种基本的排序算法进行讨论。很多其他的排序算法都可以基于这几种基本的排序算法改进得到，下面列出了几种常见的排序算法以及相应的时间复杂度。
(1)选择排序: O(N^2)
(2)插入排序 O(N^2)
(3)Shell排序 和递增序列有关
(4)归并排序 O(NlgN)
(5)快速排序 O(NlgN)
下面一一讨论
详解
问题描述:
将大小为N的int数组a按照从元素小到大的顺序进行排序
选择排序
思想:先找到序列中最小的元素，然后将其和第一个元素换位置，接着在剩下的元素中找最小的元素，然后将其和第二个元素换位置，如此重复，知道整个序列有序
时间复杂度:
由选择排序的思想是在数组第k个位置处放入数组后N-k个元素中最小的元素(前k-1个元素已经排好序)，因此所需要的比较次数为N-k，所以当我们从头扫描整个数组时，所需要的比较次数为 ： N+(N-1)+…+2+1, 即选择排序的时间复杂度为 ：O(N^2)
空间复杂度：
选择排序是将数组原地排序，只是需要某个临时变量来存储数组元素而不用使用额外的内存空间，因此其空间复杂度为：O(1)
代码实现:
public class Sort{
/**
*@param a, 待排序的数组
*/
public static void selectionSort(int[] a){
for(int sweep=0;sweep<a.length;sweep++){
for(int iloop=sweep+1;iloop<a.length;iloop++){
if(a[sweep]>a[iloop]) exch(a,sweep,iloop);
}
}
}
/**
*交换数组索引为iIndex和jIndex的元素
*@param aux
*@param iIndex
*@param jIndex
*/
private static void exch(int[] aux,int iIndex,int jIndex){
aux[jIndex]+=aux[iIndex];
aux[iIndex]=aux[jIndex]-aux[index];
aux[jIndex]-=aux[iIndex];
}
}
插入排序
思想:将位置k(k>0,k=1表示第一个元素)处的元素放到由位置1到位置k-1的元素的序列中恰当的位置。(有点像打扑克起牌，当起到第k张牌，然后将这张牌放到手中已有牌的适当的位置)
时间复杂度:
由插入排序的思想，对数组中第k个元素，需要将该元素放入前k-1个元素的适当位置，由于前k-1个元素已经排好序，在最好情况下，前k-1个元素都比第k个元素小，因此只用比较1次，不需要交换元素，因此总共需要N-1次比较，0次交换；在最坏情况下，前k-1个元素都比第k个元素大，这时就需要比较k-1次，同时需要k-1次元素交换，因此总共需要的比较次数和交换均为：1+2+3+…+(N-1) ~ N^2/2。 因此，平均情况下插入排序大约需要N^2/4次比较和N^2/4次交换。 故插入排序的时间复杂度为 O(N^2)
空间复杂度：
插入排序也是将数组原地排好序，所以其空间复杂度为O(1)
代码实现:
public class Sort{
/**
*@param a, 待排序的数组
*/
public static void insertionSort(int[] a){
for(int sweep=0;sweep<a.length;sweep++){
for(int iloop=sweep;iloop>0;iloop--){
if(a[iloop]<a[iloop-1]) exch(a,iloop,iloop-1);
}
}
}
/**
*交换数组索引为iIndex和jIndex的元素
*@param aux
*@param iIndex
*@param jIndex
*/
private static void exch(int[] aux,int iIndex,int jIndex){
aux[jIndex]+=aux[iIndex];
aux[iIndex]=aux[jIndex]-aux[index];
aux[jIndex]-=aux[iIndex];
}
}
Shell排序
思想:将序列中任意间隔为h的元素组成的子序列排好序。
时间复杂度：
和递增序列有关，具体分析不太清楚
代码实现：
/**
*希尔排序算法
*@param arrayIn 待排序的数组
*/
public static void ShellSort(int[] arrayIn){
int length=arrayIn.length;
int h=1;
while(h<length/3) h=3*h+1;
while(h>=1){
for(int iloop=h;iloop<length;iloop++){
for(int jloop=iloop;jloop>=h&&less(arrayIn[jloop],arrayIn[jloop-h]);jloop-=h){
exch(arrayIn,jloop,jloop-h);
}
}
h=h/3;
}
}
归并排序
思想:
归并排序采用的是分治的方法。简单来说，就是将数组分为两部分，然后分别将这两部分排好序后，最后将它们归并成一个数组。因此这是一个递归的过程
时间复杂度：
由归并排序的思想，不断将数组均分为两个子数组，然后将两个子数组排好序后并将其归并到一个大的数组中，可以用如下示意图来简单说明
在上图中，为便于分析，我们假设原始待排序的数组的长度为N=2^n。当递归地将数组切分k次时，产生的子数组的长度为2^(n-k)，产生子数组的对数为2^(k-1)对，因此将切分k次(或者递归深度为k)的子数组归并时，需要的比较次数约为2^(n-k)x2^(k-1)=2^(n-1)次，而递归深度不大于n(数组元素个数大于0),因此总共需要的比较次数为n2^(n-1)次，也就是约为NlgN次。因此归并排序的时间复杂度为： O(NlgN)
空间复杂度：
看具体实现方式
代码实现：
归并排序的基本实现方法有两种形式: 递归实现 和 非递归实现
public class Sort{
private static int[] helper;
/**
*递归实现归并排序
*@param a, 待排序的数组
*/
public static void mergeSort(int[] a){
helper=new int[a.length];
mergeSort(a,0,a.length-1);
}
/**
*@param a, 待排序的数组
*@param lo
*@param hi
*/
private static void mergeSort(int[] a,int lo,int hi){
if(lo>=hi) return;
mid=(lo+hi)/2;
mergeSort(a,lo,mid); //将左侧子数组排好序
mergeSort(a,mid+1,hi); //将右侧子数组排好序
merge(a,lo,mid,hi); //将左右两侧子数组归并
}
/**
*非递归实现归并排序
*@param a, 待排序的数组
*/
public static void mergeNonRecurSort(int[] a){
int size=a.length;
for(int sz=1;sz<size;sz=sz*2){
for(int iloop=0;iloop<size-sz;iloop+=sz*2){
merge(a,iloop,iloop+sz-1,Math.min(iloop+sz*2-1，size-1));
}
}
}
/**
*将数组aux索引lo到mid的子数组和索引mid+1到hi的子数组归并
*@param aux, 待归并的数组
*@param lo
*@param mid
*@param hi
*/
private static void merge(int[] aux,int lo,int mid,int hi){
int iIndex=lo;jIndex=mid+1;
for(int iloop=lo;iloop<=hi;iloop++){
helper[iloop]=aux[iloop];
}
for(int iloop=lo;iloop<=hi;iloop++){
if(iIndex>mid) aux[iloop]=helper[jIndex++];
else if(jIndex>hi) aux[iloop]=helper[iIndex++];
else if(helper[iIndex]<=helper[jIndex]) aux[iloop]=helper[iIndex++];
else aux[iloop]=helper[jIndex++];
}
}
}
改进:
在上述归并排序的递归实现中，每次归并时都需要将输入数组复制到辅助数组helper中，我们可以将此改进，在不同的递归层次改变输入数组和辅助数组的角色，从而不用每次归并时都要复制一次，示意图如下
实现代码如下
public class Sort{
private static int[] auxArray;
/**
*递归实现归并排序
*@param a, 待排序的数组
*/
public static void mergeSort(int[] a){
auxArray=new int[a.length];
for(int iloop=0;iloop<a.length;iloop++){
auxArray[iloop]=a[iloop];
}
mergeSort(a,auxArray,0,a.length-1);
}
/**
*@param a, 待排序的数组
*@param lo
*@param hi
*/
private static void mergeSort(int[] arrayInput,int[] aux,int lo,int hi){
if(lo>=hi) return;
mid=(lo+hi)/2;
mergeSort(aux,arrayInput,lo,mid); //改变输入数组和辅助数组的角色
mergeSort(aux,arrayInput,mid+1,hi);
merge(arrayInput,aux,lo,mid,hi);
}
/**
*将数组aux索引lo到mid的子数组和索引mid+1到hi的子数组归并
*@param aux, 待归并的数组
*@param lo
*@param mid
*@param hi
*/
private static void merge(int[] a,int[] helper,int lo,int mid,int hi){
int iIndex=lo;jIndex=mid+1;
for(int iloop=lo;iloop<=hi;iloop++){
if(iIndex>mid) a[iloop]=helper[jIndex++];
else if(jIndex>hi) a[iloop]=helper[iIndex++];
else if(helper[iIndex]<=helper[jIndex]) a[iloop]=helper[iIndex++];
else a[iloop]=helper[jIndex++];
}
}
}
快速排序
思想:从序列中选取切分元素(一般是序列的第一个元素)，然后将整个序列中中比切分元素小的元素放在切分元素的左边，比切分元素大的元素放在其右边。然后分别对左右两部分子序列采取同样的做法，当左右两部分子序列有序时，整个序列也就有序了。
时间复杂度：
由快速排序的思想，若每次选取的切分元素都是当前子数组中最小或最大的元素，每次将长度为k的数组切分为长度为k-1的子数组，所以总的比较次数为 (N-1)+(N-2)+…+3+2+1~O(N^2),可见快速排序在最坏情况下其性能较差； 在最好情况下，每次选取的切分元素都能将数组切分成两个相同长度的子数组，如果将长度为k的数组进行排序需要进行C(k)次比较，将该数组切分为两个长度为k/2的数组后再将这两个数组排好序所需要的比较的次数为2C(k/2)+k，因此满足式子: C(k)=2C(k/2)+k。将该式稍作变换可得: C(k)/k=C(k/2)/(k/2)+1. 也就是一个等差数列，如果原始输入数组长度为N=2^n， 容易得到：C(N)/N-C(1)/1=n.由于C(1)=0,n=lgN,因此将输入数组排好序需要的比较次数为NlgN。更为严格的分析较为复杂，这里不展开，平均而言，快速排序的事件复杂度约为O(NlgN)。
空间复杂度：
因为在切分的过程中需要利用临时变量存储切分元素，若输入数组的大小为N=2^n，因此需要切分的次数大约为n，因此空间复杂度大约为O(lgN)
代码实现：
public class Sort{
/**
*@param a, 待排序的数组
*/
public static void quickSort(int[] a){
}
private static void quickSort(int[] a,int lo,int hi){
if(lo>=hi) return;
int index=partition(a,lo,hi);
quickSort(a,lo,index-1);
quickSort(a,index+1,hi);
}
/**
*找出分解元素，将其放在数组恰当的位置，返回其索引
*@param a 待排序的数组
*@param lo 子数组的最低位索引
*@param hi 子数组的最高位索引
*/
private static int partition(int[] a,int lo,int hi){
int i=lo,j=hi+1;
int v=a[lo];
while(true){
while(less(a[++i],v)) if(i==hi) break;
while(less(v,a[--j])) if(j==lo) break;
if(i>=j) break;
exch(a,i,j);
}
exch(a,lo,j);
return j;
}
/**
*交换数组索引为iIndex和jIndex的元素
*@param aux
*@param iIndex
*@param jIndex
*/
private static void exch(int[] aux,int iIndex,int jIndex){
aux[jIndex]+=aux[iIndex];
aux[iIndex]=aux[jIndex]-aux[index];
aux[jIndex]-=aux[iIndex];
}
}
利用以上几种排序算法将一个数组大小为500000的随机整形数组排序所需要的运行时间如下
其中时间的单位为秒