排序算法(Java版)

1、直接插入排序

算法原理： 每次將無序序列中的第一個插入到有序序列當中，使有序序列仍為有序，第一趟排序默認第一個元素是有序的，類比于生活中的摸牌，每次將新的排插入已有的牌當中。直接插入排序的算法原理很簡單，我們只需要找到每個元素該插入到哪個位置即可。
在這里插入圖片描述

代碼實現：

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

代碼圖解：
在這里插入圖片描述

2、希爾排序

算法原理： 希爾排序又稱縮小增量排序，原理是先選定一個數作為分組的組數，將數組進行分組，接著分別對每個組進行排序，每組排序好之后，縮小分組的組數，重復上述步驟，直到組數為1。對每個組進行排序，我們使用插入排序的方法進行排序。
在這里插入圖片描述

代碼實現：

    public void ShellSort(int[] array) {int gap = array.length;//分成gap組,對每一組進行插入排序while (gap > 1) {gap /= 2;shell(array, gap);}}//對每組進行插入排序public void shell(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 {array[j + gap] = tmp;break;}}array[j + gap] = tmp;}}

3、直接選擇排序

算法原理： 每次待排序序列中選擇最小的元素和待排序的第一個元素交換
代碼實現：

    public void SelectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}//交換minIndex下標和i下標的值int tmp = array[minIndex];array[minIndex] = array[i];array[i] = tmp;}}

4、堆排序

算法原理： 堆排序是借用堆這種數據結構來實現的一種排序算法，如果升排序，建立大根堆；如果排降序，建立小根堆。建堆之后：
1、交換0下標元素和最后一個元素的值
2、然后重新將數組進行向下調整為大根堆
重復這兩個步驟，直到全部有序
在這里插入圖片描述

代碼實現：

    public void HeapSort(int[] array) {//先創建大堆createBigHeap(array);int end = array.length - 1;while (end >= 0) {//交換int tmp = array[0];array[0] = array[end];array[end] = tmp;ShiftDown(array, 0, end);end--;}}public void createBigHeap(int[] array) {for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {ShiftDown(array, parent, array.length);}}public void ShiftDown(int[] array, int parent, int end) {int child = parent * 2 + 1;while (child < end) {if (child + 1 < end && array[child] < array[child + 1]) {child++;}if (array[child] > array[parent]) {//交換int tmp = array[parent];array[parent] = array[child];array[child] = tmp;parent = child;child = parent * 2 + 1;} else {break;}}}

5、冒泡排序

算法原理： 遍歷數組，每次比較相鄰兩個元素的大小，如果大的數字在前則交換兩個元素的位置，這樣就完成了一趟冒泡排序，此時最大的數到了最后，然后對前n-1個數進行相同的操作，直到有序。
代碼實現：

    public void BubbleSort(int[] array) {for (int i = 0; i < array.length-1; i++) {for (int j = i; j < array.length - i - 1; j++) {if (array[j] > array[j + 1]) {//交換int tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;}}}}

問題：如果遍歷一遍數組已經有序了，就不用再繼續比較下去了，因此對上面代碼進行優化
優化后:

    public void BubbleSort(int[] array) {boolean flg = false;for (int i = 0; i < array.length - 1; i++) {for (int j = i; j < array.length - i - 1; j++) {if (array[j] > array[j + 1]) {//交換int tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;flg = true;}}if (!flg) {break;}}}

6、快速排序

算法原理： 快速排序的基本思想就是：選定一個基準，通過一趟快速排序之后，能把數據分割為兩部分，左邊部分比基準的值小，右邊的部分比基準的值大，接著再按照這個方法分別對基準左邊部分和右邊部分進行遞歸，重復這個步驟直到整個序列都有序。快速排序的最重要部分就是如何將序列分割成兩部分，常見的分割方法有hoare法和挖坑法
Hoare法分割： 先選定一個基準（默認是第一個元素），定義left、right下標，left從序列最右邊開始找比基準小的值（升序排序），找到之后停下來，接著讓left從最左邊開始找比基準大的值，找到之后停下來，將找到的這兩個值交換，當left和right相遇時(left=right)，交換基準的值和left/right下標的值，這樣left/right下標左邊的元素全都比left/right下標的值小,右邊的元素都比它大，這樣就分割好了。
圖解：
在這里插入圖片描述

挖坑法：
和Hoare法的區別是：挖坑法是邊找邊交換，如圖
在這里插入圖片描述

6.1 遞歸實現

代碼實現：

    public void QuickSort(int[] arr) {quick(arr, 0, arr.length - 1);}public void quick(int[] arr, int left, int right) {//遞歸結束的條件if (left >= right) {return;}//進行分割int pio = partition(arr, left, right);quick(arr, 0, pio - 1);quick(arr, pio + 1, right);}

hoare法分割

    public int partition(int[] arr, int left, int right) {int tmp = arr[left];int i = left;while (left < right) {while (left < right && arr[right] >= tmp) {right--;}while (left < right && arr[left] <= tmp) {left++;}//交換int tmp = array[right];array[right] = array[left];array[left] = tmp;}//交換int tmp = array[i];array[i] = array[left];array[left] = tmp;return left;}

挖坑法分割

    public int partition(int[] arr, int left, int right) {int tmp = arr[left];while (left < right) {while (left < right && arr[right] >= tmp) {right--;}arr[left] = arr[right];while (left < right && arr[left] <= tmp) {left++;}array[right] = array[left];}arr[left] = tmp;return left;}

優化： 如果待排序序列是：1、2、3、4、5這種有序的序列，假如還是取第一個元素為基準，就會出現左邊沒有小于基準的值，如何讓每次分割都是均勻分割？方法很簡單，取序列最左邊、最右邊和中間位置的三個元素的中位數作為基準，再進行Hoare法或者挖坑法分割，此時每次都能均勻分割，如圖
在這里插入圖片描述

優化后：

    public void QuickSort(int[] arr) {quick(arr, 0, arr.length - 1);}public void quick(int[] arr, int left, int right) {//遞歸if (left >= right) {return;}//中位數的值作為基準int midIndex = midThreeIndex(arr, left, right);//交換int tmp = arr[left];arr[left] = arr[midIndex];arr[midIndex] = tmp;    int pio = partition(arr, left, right);quick(arr, 0, pio - 1);quick(arr, pio + 1, right);}public int partition(int[] arr, int left, int right) {int tmp = arr[left];int i = left;while (left < right) {while (left < right && arr[right] >= tmp) {right--;}while (left < right && arr[left] <= tmp) {left++;}swap(arr, right, left);}swap(arr, i, left);return left;}

6.2 非遞歸實現

原理： 利用棧這個數據結構來實現。首先先對序列進行一次分割（Hoare法或者挖坑法都可以），將基準左邊部分的left、right下標入棧，再將右邊部分的left、right下標入棧，然后出棧兩個元素作為新的left、right來進行分割，重復上述步驟，直到棧為空
在這里插入圖片描述

代碼實現：

    public void QuickSortNoRecursion(int[] arr) {Stack<Integer> stack = new Stack<>();int left = 0;int right = arr.length - 1;int pio = partition(arr, left, right);if (pio > left + 1) {stack.push(left);stack.push(pio - 1);}if (pio < right - 1) {stack.push(pio + 1);stack.push(right);}while (!stack.isEmpty()) {right = stack.pop();left = stack.pop();pio = partition(arr, left, right);if (pio > left + 1) {stack.push(left);stack.push(pio - 1);}if (pio < right - 1) {stack.push(pio + 1);stack.push(right);}}}

7、歸并排序

原理： 歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；歸并排序的思想是：先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
在這里插入圖片描述

7.1 遞歸實現

遞歸思路： 先將序列進行分解，直到分解為單個元素為一組，然后再進行合并。合并：開辟新的數組，新的數組存儲的是合并之后且有序的子序列，再開辟的新數組的元素拷貝回原數組

    public void mergeSort(int[] arr) {merge(arr, 0, arr.length - 1);}public void merge(int[] arr, int left, int right) {if (left >= right) {return;}int mid = (left + right) / 2;//分解merge(arr, left, mid);merge(arr, mid + 1, right);//合并mergeFun(arr, left, mid, right);}//合并public void mergeFun(int[] arr, int left,int mid, int right) {int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;int k = 0;int[] tmp = new int[right - left + 1];//開辟新的數組while (s1 <= e1 && s2 <= e2) {if (arr[s1] < arr[s2]) {tmp[k++] = arr[s1++];} else {tmp[k++] = arr[s2++];}}while (s1 <= e1) {tmp[k++] = arr[s1++];}while (s2 <= e2) {tmp[k++] = arr[s2++];}//此時tmp有序了,拷回到原數組for (int i = 0; i < k; i++) {arr[left + i] = tmp[i];}}

7.2 非遞歸實現

非遞歸省去了分解的步驟，直接對數組進行合并

    //非遞歸public void mergeSortN(int[] arr) {mergeN(arr);}//沒有分解的過程private void mergeN(int[] arr) {int gap = 1;while (gap <= arr.length) {for (int i = 0; i < arr.length; i = i + 2 * gap) {int mid = i + gap - 1;if (mid >= arr.length) {mid = arr.length - 1;}int right = mid + gap;if (right >= arr.length) {right = arr.length - 1;}mergeFun(arr, i, mid, right);}gap *= 2;}}public void mergeFun(int[] arr, int left,int mid, int right) {int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;int k = 0;int[] tmp = new int[right - left + 1];while (s1 <= e1 && s2 <= e2) {if (arr[s1] < arr[s2]) {tmp[k++] = arr[s1++];} else {tmp[k++] = arr[s2++];}}while (s1 <= e1) {tmp[k++] = arr[s1++];}while (s2 <= e2) {tmp[k++] = arr[s2++];}//此時tmp有序了,拷回到原數組for (int i = 0; i < k; i++) {arr[left + i] = tmp[i];}}

8、性能分析

性能包括：時間復雜度、空間復雜度、穩定性

排序算法	平均時間復雜度	空間復雜度	穩定性
插入排序	O(n^2)	O(1)	穩定
希爾排序	O(和增量有關)	O(1)	不穩定
選擇排序	O(n^2)	O(1)	不穩定
堆排序	O(n*logn)	O(1)	不穩定
冒泡排序	O(n^2)	O(1)	穩定
快速排序	O(n*logn)	O(logn)	不穩定
歸并排序	O(n*logn)	O(n)	穩定