数据结构与算法 ：提到的几种排序

1、插入排序：

对于第p趟（1<=p<=N-1），保证0~p的元素是以排序的。复杂度为O(N^2)。

public void insertionSort(int[] a){ int i=0,j=0; for(i=1;i<a.length;i++){ int t=a[i]; for(j=i;j>0&&t<a[j-1];j--) a[j]=a[j-1]; a[j]=t; } }

2、希尔排序：

每次对间隔gap的元素进行排序，gap不断减小，排序算法为插入排序。使用不同的增量序列的希尔排序复杂度不同。

public void shellSort(int[] a){ int j=0; for(int gap=a.length/2;gap>=1;gap=gap/2){//增量序列 gap=gap/2 for(int i=gap;i<a.length;i+=gap){ int t=a[i]; for( j=i;j>=gap&&t<a[j-gap];j-=gap) a[j]=a[j-gap]; a[j]=t; } } }

3、堆排序：

比较稳定，O(NlogN)。

public class Solution { public void heapSort(int[] a){ int t; for(int i=a.length/2;i>=0;i--) percDown(a,i,a.length); for(int i=a.length-1;i>=0;i--){ t=a[i]; //将最大的元素放到堆的后面 a[i]=a[0]; a[0]=t; percDown(a,0,i); } } public int leftchild(int i){ return 2*i+1; } public void percDown(int[] a,int i,int n){ //将a[i]放到合适的位置。 int child; int temp; for(temp=a[i];leftchild(i)<n-1;i=child){ child=leftchild(i); if(child!=n-1&&a[child]<a[child+1]) child++; if(temp<a[child]) a[i]=a[child]; else break; } a[i]=temp; } }

4、归并排序：

递归、O(NlogN)、java中泛型排序所使用的算法，所需要的比较次数最少。  需要额外的空间。

public class Solution { public void merge(int[] a,int[] tempArray,int leftPos,int rightPos,int rightEnd){ int leftEnd =rightPos-1; int tempPos=leftPos; int numElements=rightEnd-leftPos+1; while(leftPos<=leftEnd&&rightPos<=rightEnd){ if(a[leftPos]<=a[rightPos]){ tempArray[tempPos++]=a[leftPos++]; } else tempArray[tempPos++]=a[rightPos++]; } while(leftPos<=leftEnd){ tempArray[tempPos++]=a[leftPos++]; } while(rightPos<=rightEnd){ tempArray[tempPos++]=a[rightPos++]; } for(int i=0;i<numElements;i++,rightEnd--){ a[rightEnd]=tempArray[rightEnd]; } } public void mergeSort(int[] a,int[] tempArray,int left,int right){ if(left<right){ int center=(left+right)/2; mergeSort(a,tempArray,left,center); mergeSort(a,tempArray,center+1,right); merge(a,tempArray,left,center+1,right); } } public void mergeSort(int[] a){ int[] tempArray=new int[a.length]; mergeSort(a,tempArray,0,a.length-1); } }

5、快速排序：

在java里用作基本类型的排序算法。O(NlogN)。 对小的数组不使用递归。  随机化的快排比归并排序快。

public class Solution { int CUTOFF=2;//元素个数小于CUTOFF时，使用插入排序。 public void swapReferences(int[] a,int left,int right){ int t; t=a[left]; a[left]=a[right]; a[right]=t; } public int median3(int[] a,int left,int right){ int center=(left+right)/2; if(a[center]<a[left]) swapReferences(a,center,left); if(a[right]<a[left]) swapReferences(a,right,left); if(a[center]>a[right]) swapReferences(a,center,right); swapReferences(a,center,right-1); return a[right-1]; } public void quickSort(int[] a,int left,int right){ if(left<=right-CUTOFF){ int pivot=median3(a,left,right); int i=left,j=right-1; while(true){ while(a[++i]<pivot){}; while(a[--j]>pivot){}; if(i<j) swapReferences(a,i,j); else break; } swapReferences(a,i,right-1);//重置枢纽元 quickSort(a,left,i-1); quickSort(a,i+1,right); } else insertionSort(a,left,right); } public void insertionSort(int[] a,int left,int right){ int i=0,j=0; for(i=left;i<=right;i++){ int t=a[i]; for(j=i;j>0&&t<a[j-1];j--) a[j]=a[j-1]; a[j]=t; } } public void quickSort(int[] a){ quickSort(a,0,a.length-1); } }