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

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);
  }
}