冒泡排序、插入排序、快速排序、堆排序、希爾排序、歸并排序

冒泡排序核心邏輯就是對數組從第一個位置開始進行遍歷，如果發現該元素比下一個元素大，則交換位置，如果不大，就拿著下一個比該元素大的元素向下繼續比較，以此類推一直比較到最后，每一輪下來就會把當前最大的元素放到最后所以每一輪會確定一個最大元素。

    public void bubbleSort(int[] array) {for (int i = 0; i < array.length; i++) {int flag = 0;for (int j = 1; j < array.length-i; j++) {if (array[j - 1] > array[j]) {swap(array,j-1,j);flag = 1;}}if (flag == 0) {break;}}}

這里做了一個優化，當某一輪發現一個元素都沒有移動的時候，就表示這個數組已經是有序的了，不理解的可以舉一個已經有序的例子推敲一下，所以定義一個flag如果為0就表示一整倫下來都沒有發生過移動直接跳出循環，排序完成。

時間復雜度：O(N^2)

穩定性：穩定

空間復雜度：O(1)

插入排序

    public void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int j = i - 1;int tmp = array[i];for (; j >= 0; j--) {if (array[j] >= tmp) {array[j+1] = array[j];} else {break;}}array[j+1] = tmp;}}

時間復雜度：O(N^2)

穩定性：穩定

空間復雜度：O(1)

快速排序(未優化版本)

	public void quickSort (int[] array) {quick(array,0,array.length-1);}private void quick(int[] array, int start, int end) {if (start >= end) {return;}// 一個是霍爾法一個是挖坑法，兩個都可int part = partition1(array,start,end); // 霍爾法//int part = partition2(array,start,end); // 挖坑法quick(array,start,part-1);quick(array,part+1,end);}private int partition1(int[] array, int left, int right) {int tmp = array[left];int tmpIndex = left;while (left < right) {while (left < right && array[right] >= tmp) {right--;}while (left < right && array[left] <= tmp) {left++;}swap(array,left,right);}swap(array,tmpIndex,left);return left;}private int partition2(int[] array, int left ,int right) {int tmp = array[left];while (left < right) {while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}

最好時間復雜度：O(N*logN)

最壞時間復雜度：O(N^2)

空間復雜度：O(logN)

穩定性：不穩定

快速排序(優化版本)

	public void quickSort (int[] array) {quick(array,0,array.length-1);}private void quick(int[] array, int start, int end) {if (start >= end) {return;}// 優化1（如果是少量的數據，直接插入排序速度是很快的，所以我們用直接插入排序處理數量小于等于15個的情況，不要小看這個優化，因為quickSort是樹形的遞歸模式，在最后一層會有大量的數據存在，這個時候我們直接不進行遞歸直接進行插入排序可以節省大量的開銷）if (end - start + 1 <= 15) {insertWithQuick(array,start,end);return;}// 優化2（三數取中優化，如果當一個數組比較趨于有序的情況下，那么構造出來的二叉樹就是變成了一個鏈表，所以才會有時間復雜度區域O(N^2)，我們只要打破這個順序就好，我們直接去一個較為中間的值作為基準值就能均分了）int midIndex = findMidIndex(array,start,end);swap(array,start,midIndex);// 一個是霍爾法一個是挖坑法，兩個都可int part = partition1(array,start,end); // 霍爾法//int part = partition2(array,start,end); // 挖坑法quick(array,start,part-1);quick(array,part+1,end);}private int partition1(int[] array, int left, int right) {int tmp = array[left];int tmpIndex = left;while (left < right) {while (left < right && array[right] >= tmp) {right--;}while (left < right && array[left] <= tmp) {left++;}swap(array,left,right);}swap(array,tmpIndex,left);return left;}private int partition2(int[] array, int left ,int right) {int tmp = array[left];while (left < right) {while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}// 使用插入排序進行優化private void insertWithQuick(int[] array, int start, int end) {for (int i = start; i <= end; i++) {int j = i - 1;int tmp = array[i];for (; j >= start; j--) {if (array[j] >= tmp) {array[j+1] = array[j];} else {break;}}array[j+1] = tmp;}}// 使用三數取中找到中值下標private int findMidIndex(int[] array, int start, int end) {int midIndex = start + (end - start) / 2;if (array[start] > array[end]) {// end  startif (array[midIndex] < array[end]) {return end;} else if (array[midIndex] > array[start]) {return start;} else {return midIndex;}} else {// start  endif (array[midIndex] < array[start]) {return start;} else if (array[midIndex] > array[end]) {return end;} else {return midIndex;}}}

優化后的時間復雜度將會無限趨近于O(N*logN)，空間復雜度不變

堆排序

    public void heapSort (int[] array) {createBigHeap(array);int end = array.length-1;while (end >= 0) {swap(array,0,end);end--;siftDown(array,0,end);}}private void createBigHeap(int[] array) {for (int parent = (array.length-2); parent >= 0; parent--) {siftDown(array,parent,array.length-1);}}private void siftDown(int[] array, int parent, int end) {int child = parent * 2 + 1;while (child <= end) {if (child + 1 <= end && array[child+1] > array[child]) {child++;}if (array[child] > array[parent]) {swap(array,child,parent);parent = child;child = child * 2 + 1;} else {break;}}}

時間復雜度：O(N*logN)

空間復雜度：O(logN)

穩定性：不穩定

希爾排序

    public void shallSort (int[] array) {int gap = array.length / 2;while (gap > 0) {shall(array,gap);gap /= 2;}}private void shall(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;for (; j >= 0; j -= gap) {if (array[j] >= tmp) {array[j + gap] = array[j];} else {break;}}array[j+gap] = tmp;}}

希爾排序就是直接插入排序的升級版本

時間復雜度：不好計算業界公認的大概是O(N^1.3)

空間復雜度：O(1)

穩定性：不穩定

歸并排序

    public void mergeSort(int[] array) {mergeFun(array,0,array.length-1);}private void mergeFun(int[] array, int start, int end) {if (start >= end) {return;}int midIndex = start + (end - start) / 2;mergeFun(array,start,midIndex);mergeFun(array,midIndex+1,end);// mergemerge(array, start, end, midIndex);}private void merge(int[] array, int start, int end, int midIndex) {int rs = midIndex + 1 , k = 0, tmpIndex = start;int[] tmpArray = new int[end - start +1];while (start <= midIndex && rs <= end) {if (array[start] < array[rs]) {tmpArray[k++] = array[start++];} else {tmpArray[k++] = array[rs++];}}while (start <= midIndex) {tmpArray[k++] = array[start++];}while (rs <= end) {tmpArray[k++] = array[rs++];}for (int j = tmpIndex; j <= end; j++) {array[j] = tmpArray[j - tmpIndex];}}

時間復雜度：O(N*logN)

空間復雜度：O(N)

穩定性：穩定

各排序時間消耗對比

為了更直觀的觀察每個排序有時間效率，我將這幾個排序進行了一個對比，先隨機生成要給數組大小為100000的隨機數，隨機數范圍是0-10000，之后分別計算各個排序所消耗的時間單位是毫秒

public static void main(String[] args) {Sort sort = new Sort();// 原數組int[] array = createRandomNumber(100_000,10_000);// copy數組int[] array1 = Arrays.copyOf(array, array.length);long start1 = System.currentTimeMillis();sort.quickSort(array1);System.out.println("quickSort : " + (System.currentTimeMillis()-start1) );int[] array2 = Arrays.copyOf(array, array.length);long start2 = System.currentTimeMillis();sort.shallSort(array2);System.out.println("shallSort : " + (System.currentTimeMillis()-start2) );int[] array3 = Arrays.copyOf(array, array.length);long start3 = System.currentTimeMillis();sort.heapSort(array3);System.out.println("heapSort : " + (System.currentTimeMillis()-start3) );int[] array4 = Arrays.copyOf(array, array.length);long start4 = System.currentTimeMillis();sort.mergeSort(array4);System.out.println("mergeSort : " + (System.currentTimeMillis()-start4) );int[] array5 = Arrays.copyOf(array, array.length);long start5 = System.currentTimeMillis();sort.insertSort(array5);System.out.println("insertSort : " + (System.currentTimeMillis()-start5) );int[] array6 = Arrays.copyOf(array, array.length);long start6 = System.currentTimeMillis();sort.bubbleSort(array6);System.out.println("bubbleSort : " + (System.currentTimeMillis()-start6) );}private static int[] createRandomNumber (int size, int range) {int[] array = new int[size];for (int i = 0; i < size; i++) {array[i] = new Random().nextInt(range);}return array;}