七种排序算法

方法	时间复杂度	空间复杂度	Stable
冒泡排序（Bubble Sort）	O(n) — O(n^2)	O(1)	yes
选择排序（Selection Sort）	O(n^2) — O(n^2)	O(1)	no
插入排序（Insertion Sort）	O(n) — O(n^2)	O(1)	yes
希尔排序（Shell Sort）	O(n) — O(n log^2 n)	O(1)	no
快速排序（Quick Sort）	O(n log n) — O(n log n) — O(n^2)	O(log n) — O(n)	no, but the stable exist
归并排序（Merge Sort）	O(n log n)	O(n)	yes
堆排序（Heap Sort）	O(n log n)	1	no

// 1. 冒泡排序

 1 public void bubbleSort(int[] A) {
 2      for(int i=A.length; i>0; i--) {
 3           boolean flag = true;
 4           for(int j=1; j<i; j++) {
 5                if(A[j]<A[j-1]) {
 6                     int tmp = A[j-1];
 7                     A[j-1] = A[j];
 8                     A[j] = tmp;
 9                     flag = false;
10                }
11           }
12           if(flag) {
13                break;
14           }
15      }
16 }

// 2. 选择排序

 1 public void selectionSort(int[] A) {
 2      for(int i=A.length; i>1; i--) {
 3           int maxIdx = 0;
 4           for(int j=1; j<i; j++) {
 5                if(A[j]>A[maxIdx]) {
 6                     maxIdx = j;
 7                }
 8           }
 9           if(maxIdx!=i-1) {
10                int tmp = A[maxIdx];
11                A[maxIdx] = A[i-1];
12                A[i-1] = tmp;
13           }
14      }
15 }

// 3. 插入排序

 1 public void insertionSort(int[] A) {
 2      for(int i=1; i<A.length; i++) {
 3           int tmp = A[i];
 4           int j = i-1;
 5           while(j>=0) {
 6                if(A[j]>=A[i])
 7                     j--;
 8                else break;
 9           }
10           int tmp = A[i];
11           j++;
12           for(int k=i; k>j; k--) {
13                A[k] = A[k-1];
14           }
15           A[j] = tmp;
16      }
17 }

// 4. 希尔排序 — 插入排序的一种更高效的改进版本

 1 public void shellSort(int[] A) {
 2      int step = A.length;
 3      while(step>1) {
 4           step = step>>1;
 5           for(int i=0; i<A.length; i++) {
 6                int pos = i+step;
 7                int tmp = A[pos];
 8                while((pos-step>=0) && tmp<A[pos-step]) {
 9                     A[pos] = A[pos-step];
10                     pos -= step;
11                }
12                A[pos] = tmp;
13           }
14      }    
15 }

// 5. 快速排序

 1 public void quickSort(int[] A, int start, int end) {
 2      if (start >= end) return;
 3      int i = start;
 4      int j = end;
 5      int tmp = A[i];
 6      while(i<j) {
 7           while(i<j && A[j]>=tmp)
 8                j--;
 9           A[i] = A[j];
10           while(i<j && A[i]<tmp)
11                i++;
12           A[j] = A[i];
13       }
14       A[i] = tmp;
15       quickSort(A, start, i-1);
16       quickSort(A, i+1, end);
17 }

// 6. 归并排序

 1 public void mergeSort(int A[], int start, int end) {
 2       if(start<end) {
 3            int dis=(end-start)/2;
 4             mergeSort(A,start,start+dis);
 5             mergeSort(A,start+dis+1,end);
 6            merge(A,start,start+dis,start+dis+1,end);
 7       }
 8 }
 9 public void merge(int[] A,int start1,int end1,int start2,int end2) {
10      int[] temp=new int[end1-start1+end2-start2+2];
11      int k=0;
12      int i1=start1;
13      int i2=start2;
14      while(i1<=end1&&i2<=end2) {
15           if(A[i1]<A[i2])
16                temp[k++]=A[i1++];
17           else
18                temp[k++]=A[i2++];
19      }
20      while(i1<=end1)
21           temp[k++]=A[i1++];
22      while(i2<=end2)
23           temp[k++]=A[i2++];
24      for(int i=start1,mark=0;mark<k;i++)
25           A[i]=temp[mark++];
26 }

// 7. 堆排序 — 选择排序的一种更高效的改进版本

 1 /* 父节点i的左子节点在位置 (2*i+1);
 2  * 父节点i的右子节点在位置 (2*i+2);
 3  * 子节点i的父节点在位置 floor((i-1)/2);
 4  */
 5 public void heapSort(int[] A) {
 6      for(int i=A.length/2;i>=0;i--) {
 7           heapAdjust(A,i,A.length);
 8      } // O(n)
 9  
10      for(int i=A.length-1;i>0;i--) {
11           swap(A[0],A[i]);
12           heapAdjust(A,0,i);
13      } // O(nlgn)
14 }
15  
16 public void heapAdjust(int[] A,int i,int length) { // siftDown
17      while(2*i+1<length) {
18           int left=2*i+1;
19           if((left+1)<length && A[left]<A[left+1])
20                left++;
21           if(A[i]<A[left]) {
22                swap(A[i],A[left]);
23                i=left;
24           } else
25                break;
26      }
27 }