[Algorithm] 常见排序算法

常见排序算法

插入排序

复杂度

思路

插排的思路是保证遍历到每个元素时，该元素前面的序列都是有序的。基于这个前提，我们将遍历到的新元素和它前面的序列相比对，然后将这个元素插入到适当的位置，使得这个包含新元素的序列也是有序的。虽然外层遍历只要O(N)时间，但是因为找到新元素的适当位置后要将之后的所有元素后移，所以最差时间是O(N^2）。

示意图

代码

public class InsertionSort<T extends Comparable> {  public T[] sort(T[] a){   T[] array=a;   T tmp;   for(int i = 1; i<a.length; i++){    tmp=array[i];    int j;    // 从后向前找到插入新元素的适当位置，比新元素大的都后移一位    for(j=i;j>0;j--){     if(array[j-1].compareTo(tmp)<0) break;     array[j]=array[j-1];    }    // 较大的元素都后移了一位，这里只要插入这个新元素，则新序列还是有序的    array[j]=tmp;   }   return array;  } }  

希尔排序

复杂度

思路

插排的一个优化是希尔排序，在原本的插入排序中，我们选择以一个一个往后看等待插入的元素。然而插入排序有这么一个性质，即如果序列有序程度越高，则时间复杂度越低。所以希尔排序利用了这个性质，先通过较大的步长进行一次插入排序（不再是一个一个往后找待插元素，而是隔一个或者隔n/2个元素来找），这样每次子插排都能将序列变得更有序一点，而且因为步长一开始很大，所以要遍历的数少，时间复杂度也很低。后来步长变小了，要遍历的数变多了，但数组也更有序了，时间复杂度也降低了。当然n/2^i这个步长序列不是最好的，最好的步长序列能使最差复杂度降低至O(N(logN)^2)

示意图

代码

public class Shellsort {  public static <T extends Comparable<? super T>> T[] sort(T[] a) {   int j = 0;   // 从n/2开始选择步长，每轮插排后减少步长，直到步长为1是最后一次   for (int gap = a.length / 2; gap > 0; gap /= 2) {    T tmp = null;    // 步长为gap的插入排序    for(int i = gap; i<a.length; i++){     tmp = a[i];     // 找到合适的插入点     for(j=i;j>=gap&&tmp.compareTo(a[j-gap])<0;j-=gap){      a[j]=a[j-gap];     }     a[j]=tmp;    }   }   return a;  } }  

选择排序

复杂度

思路

选排的思路和插排相反，插排是搜索有序序列找到合适的位置，选排则是搜索剩余的无序序列选择出其中最大（或最小）的，并将这个被选择的数放到无序序列的首部。需要注意的是。将这个数放到首部时，用的是交换的方法。因为无论如何都要遍历完子序列，所以时间复杂度至少是O(N^2)

示意图

代码

public class SelectionSort<T extends Comparable> {  public T[] sort(T[] array) {   T[] a = array;   T tmp;   int minIndex;   for (int i = 0; i < a.length; i++) {    minIndex = i;    // 在剩余无序序列中找到一个最小的    for (int j = i; j < a.length; j++) {     if (a[minIndex].compareTo(a[j]) > 0)      minIndex = j;    }    // 将这个最小的交换到无序序列的首部    if (minIndex != i) {     tmp = a[i];     a[i] = a[minIndex];     a[minIndex] = tmp;    }   }   return a;  } }  

归并排序

复杂度

思路

归并排序是典型的分治法。基本思路是将一个较长数组一分为二，我们将它的左右两半部分分别排好序，然后将这有序的两部分合并起来，这样较长数组也是有序的了。因为两半部分都是有序的，所以合并只需要同时遍历一下两半部分，看谁较小（大）就把谁先塞进数组就可以了。根据这个思路，我们不停的二分、二分，这样二分到尽头肯定只有一个数的数组，那它肯定是有序的，然后我们将两个只有一个数的数组合并，只要比较下这两个数就行了。这样就返回了一个有两个数的有序数组，然后再一直合并、合并、直到合并出整个数组。不过，在合并两个子数组时，要先用一个临时数组存放，否则会修改两个子数组的数据（因为两个子数组实际上是原数组的两个子部分）。

示意图

代码

public class Mergesort<T extends Comparable<? super T>> {  private static <T extends Comparable<? super T>> T[] sort(T[] array, T[] tmp, int left, int right){   if(left<right){    // 计算二分中点位置    int center = (left+right)/2;    // 将左半部分排序     sort(array,tmp,left,center);    // 将右半部分排序    sort(array,tmp,center+1,right);    // 将左右两半部分合并    merge(array,tmp,left,center+1,right);   }   return array;  }  public static <T extends Comparable<? super T>> T[] sort(T[] a){   T[] tmp = (T[]) new Comparable[a.length];   return sort(a,tmp,0,a.length-1);  }  private static <T extends Comparable<? super T>> void merge(T[] a, T[] tmpArray, int leftPos, int rightPos, int rightEnd){   int leftEnd=rightPos-1;   int tmpPos = leftPos;   int numElements = rightEnd - leftPos +1;   // 将两个有序数组的元素比较大小后合并成一个数组，存入一个临时数组中   while(leftPos<=leftEnd && rightPos<=rightEnd){    if(a[leftPos].compareTo(a[rightPos])<0)     tmpArray[tmpPos++]=a[leftPos++];    else     tmpArray[tmpPos++]=a[rightPos++];   }   // 如果左半部分没有合并完（说明右半部分的数较小），将其合并进去   while(leftPos<=leftEnd){    tmpArray[tmpPos++]=a[leftPos++];   }   // 如果右半部分没有合并完（说明左半部分的数较小），将其合并进去   while(rightPos<=rightEnd){    tmpArray[tmpPos++]=a[rightPos++];   }   // 将这个临时数组拷贝回原数组   for(int i = 0;i<numElements;i++,rightEnd--){    a[rightEnd]=tmpArray[rightEnd];   }  } }  

快速排序

复杂度

思路

快速排序也是分治的思想，它先选取一个枢纽值pivot，将整个数组按照枢纽值的大小重新排列，比枢纽值小的放在左边，比枢纽值大的放在右边。然后，我们再分别对这左半部分和右半部分进行同样的操作，这里半个部分不一定有半个数组的元素，要看具体有多少元素大于或小于枢纽值。一般情况下我们都选择子数组的第一个值作为枢纽，简化实现。最好还是能写个随机选择枢纽值的函数。最差的情况下，每次选到的枢纽值都是最小（最大）的，所以每次分割出来的子数组都只比当前整个数组小1的长度，就会导致O(N^2)的复杂度。

示意图

代码

public class Quicksort {  public <T extends Comparable<? super T>> T[] sort(T[] a){   return sort(a,0,a.length);  }  private <T extends Comparable<? super T>> T[] sort(T[] a, int left, int right){   if(left==right-1) return null;   //Partition into two part first   int k=partition(a,left,right);   //Recurse on front part   sort(a,left,k);   //Recurse on rear part   sort(a,k,right);   return a;  }  private <T extends Comparable<? super T>> int partition(T[] a, int left, int right){   T p = a[left];   int i = left, j =right;   // 先找到右边第一个小于枢纽值的数   do{    j--;    }while(a[j].compareTo(p)>0 && j>i);   //Swap a[i] and a[j] to partition   while(i<j){    // 将右边那个小于枢纽值的数和左边那个大于枢纽值的数交换（第一次交换的是枢纽值本身）    swap(a,i,j);    // 找到下一对可以交换的元素    do{     i++;    }while(a[i].compareTo(p)<0);    do{     j--;    }while(a[j].compareTo(p)>0);   }   //Elements before j+1 are partitioned, so we need to partition next part start from j+1   return j+1;  }  private <T extends Comparable<? super T>> void swap(T[] a, int i, int j){   T tmp = a[j];   a[j] = a[i];   a[i] = tmp;  } }  

外部排序

例题

思路

外部排序基于归并排序的理念，以该题为例，为了计算方便我们假设TB/GB/MB是以1000换算的，而且内存也有1.001G空间：

1. 将1TB数据分1000次读入内存中，每次对1GB的数据进行排序，每次排序完将其作为一个区块结果存入磁盘中。

2. 在内存中划分1000个通道，每个通道读入每个区块前1MB的数据，可知每个1MB都是有序的。

3. 对这1000个有序的1MB数据进行归并。将结果存入一个1MB的缓存当中，每当这1MB缓存满的时候，将这1MB缓存存入磁盘并清空。每当任何一个1MB通道空时，我们将对应区块的下1MB数据读入这个通道。

4. 持续执行步骤3直到所有区块的数据都被读完，这时候磁盘中就是1TB有序的数据了。