目錄

插入排序

希爾排序

歸并排序

快速排序

---

插入排序

排序原理：

1.把所有元素分為兩組，第一組是有序已經排好的，第二組是亂序未排序。

2.將未排序一組的第一個元素作為插入元素，倒序與有序組比較。

3.在有序組中找到比插入元素小或者大的元素，將插入元素放入該位置，后面元素向后移動一位。

?時間復雜度：O(n^2)

穩定性：當A與B相等，排序前A若在B前，排序后A仍然在B前，就說明該排序是穩定的。

插入排序：穩定

//比較兩元素大小方法private static boolean greater(Comparable v,Comparable w){return v.compareTo(w)>0;}

 //數組中 交換元素位置private static void exch(Comparable[] a,int i,int j){Comparable temp;temp = a[i];a[i] = a[j];a[j] = temp;}

插入排序

    public static void insertSort(Comparable[] a){for (int i = 1; i < a.length-1; i++) {for (int j = i+1; j >0; j--) {if (greater(a[j-1],a[j])){exch(a,j-1,j);}else break;}}}

希爾排序

排序原理：

1.選擇一個增長量h，按照h將數據分組。

2.每組進行插入排序。

3.減少增長量h直到h=1，重復步驟2

穩定性：不穩定

     public static void shellSort(Comparable[] a){int h = 1;//確定hwhile (h<a.length/2){h = 2*h+1;}// 希爾排序while (h>=1){for (int i = h; i < a.length; i=i+h) {for (int j = i; j >= h; j=j-h) {if (greater(a[j-h],a[j])){exch(a,j-h,j);}else break;}}h=h/2;}}

歸并排序

排序原理：

1.盡可能的一組數據拆分成兩個元素相等的子組，并對每一個子組繼續拆分，直到拆分后的每個子

組的元素個數是1為止。

2.將相鄰的兩個子組進行合并成一個有序的大組；

3.不斷的重復步驟2，直到最終只有一個組為止。

時間復雜度：O(nlogn)

穩定性： 穩定

import java.util.Arrays;public class Merge {//歸并需要的輔助數組private static Comparable[] assist;//判斷v是否比w小private static boolean less(Comparable v,Comparable w){return v.compareTo(w)<0;}//交換元素private static void exch(Comparable[] a,int i,int j){Comparable t = a[i];a[i] = a[j];a[j] = t;}//對數組a排序public static void sort(Comparable[] a){//    1.初始化輔助數組assistassist= new Comparable[a.length];//    定義lo變量和hi變量。分別記錄數組中最小的索引和最大的索引int lo = 0;int hi = a.length-1;sort(a,lo,hi);}//對數組a中從lo到hi元素進行排序private static void sort(Comparable[] a,int lo,int hi){//安全檢驗if (hi<=lo){return;}//  對lo和hi之間的數據進行分為兩組int mid = lo+(hi-lo)/2;//    分別排序sort(a,lo,mid);sort(a,mid+1,hi);//兩組歸并merge(a,lo,mid,hi);}//歸并private static void merge(Comparable[] a,int lo,int mid,int hi){//    定義三個指針int i = lo;int p1 = lo;int p2 = mid+1;//    遍歷移動p1指針和p2指針，比較對應 索引處的值，找出小的，放到輔助數組對應分索引處while (p1<=mid&&p2<=hi){if (less(a[p1],a[p2])){assist[i++] = a[p1++];}else {assist[i++] = a[p2++];}}//遍歷，如果p1的指針沒有走完，將p1剩余遍歷到輔助數組中while (p1<=mid){assist[i++] = a[p1++];}//遍歷，如果p2的指針沒有走完，將p2剩余遍歷到輔助數組中while (p2<=hi){assist[i++] = a[p2++];}//    把輔助數組中的元素復制到原數組中for (int index = lo;index<=hi;index++){a[index] = assist[index];}}public static void main(String[] args) {Integer[] a={7,8,4,5,6,1,3,9,2};Merge.sort(a);System.out.println(Arrays.toString(a));//    [1, 2, 3, 4, 5, 6, 7, 8, 9]}}

快速排序

排序原理：
1.首先設定一個分界值，通過該分界值將數組分成左右兩部分；

2.將大于或等于分界值的數據放到到數組右邊，小于分界值的數據放到數組的左邊。此時左邊部分

中各元素都小于或等于分界值，而右邊部分中各元素都大于或等于分界值；

3.然后，左邊和右邊的數據可以獨立排序。對于左側的數組數據，又可以取一個分界值，將該部分

數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處

理。
4.重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序后，再遞歸排好右側

部分的順序。當左側和右側兩個部分的數據排完序后，整個數組的排序也就完成了。?

時間復雜度：

平均情況：O(nlogn)，最壞情況：O(n^2)?

穩定性：不穩定?

import java.util.Arrays;public class Quick {private static void exch(Comparable[] a,int i,int j){Comparable t = a[i];a[i] = a[j];a[j] = t;}private static boolean less(Comparable v,Comparable w){return v.compareTo(w)<0;}//對數組內的元素進行排序public static void sort(Comparable[] a){int lo = 0;int hi = a.length-1;sort(a,lo,hi);}//對數組a中從索引hi之間的元素進行排序public static void sort(Comparable[] a,int lo,int hi){if (lo>=hi)return;int partition = partition(a,lo,hi);sort(a,lo,partition-1);sort(a,partition+1,hi);}private static int partition(Comparable[] a,int lo,int hi){//確定分界值Comparable key = a[lo];//定義兩個指針，分別指向待切分元素的最小索引處和最大索引處的下一個位置int left = lo;int right = hi+1;//切分 掃描while (true){//先從右邊向左掃描，移動right指針，找到比分界值小的，停止while (less(key,a[--right])){if (right==lo){break;}}//從左邊向右掃描，移動light指針，找到比分界值大的，停止while (less(a[++left],key)){if (left==hi){break;}}//right<right時交換if (left>=right){break;}else {exch(a,left,right);}}//交換分界值exch(a,lo,right);return right;}public static void main(String[] args) {Integer a[] = {3,6,9,2,5,8,4,7,1};Quick.sort(a);System.out.println(Arrays.toString(a));//    [1, 2, 3, 4, 5, 6, 7, 8, 9]}}