文章目錄
- 排序
- 插入排序
- 分析
- 希爾排序
- 分析
- 選擇排序
- 分析
- 堆排序
- 分析
- 冒泡排序
- 分析
- 快速排序
- 霍爾法
- 分析
- 挖坑法找基準
- 前后指針法
- 題目
- 快排的優化
- 三數取中法
- 非遞歸實現快排
- 歸并排序
- 分析
- 非遞歸實現歸并排序
- 海量數據的排序
- 非比較的排序
- 計數排序
- 分析
- 基數排序
- 桶排序

排序
- 穩定的排序:排序之前和排序之后它們倆的相對順序沒有發生變化
- 內部排序:在內存上的排序
- 外部排序:需要借助磁盤等外部空間進行的排序
插入排序
- 思想:假設這組數據的第一個元素是有序的,從第二個元素和前面的元素進行比較,找到合適的位置進行插入
// 插入排序public static 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(N^2)
最好情況:有序的數組,O(N)
數據越有序,排序越快
適用于待排序數組基本上趨于有序了,時間復雜度趨于O(N) - 空間復雜度:O(1)
- 穩定性:是一個穩定的排序
例子:5 5 7
穩定的排序可以改成不穩定的排序,但是不穩定的排序不能改成穩定的排序
希爾排序
- 對直接插入排序進行了優化,如果是 5 4 3 2 1 會退化為O(N^2)
- 分組:分完組后,每組都采用直接插入排序
- 中間隔一些元素進行分組的好處:比較大的元素都往后走了,比較小的元素都往前走了
- 縮小增量到最后會把整體看成是一組,5 3 1 組,前面的5 3 都是預排序,真正的排序是最后的一組
- 縮小增量的目的:為了讓排序更接近O(N),為了讓排序更快
// 希爾排序public static void shellSort(int[] array){int gap = array.length;while(gap > 1){gap /= 2;shell(array,gap);}}// 對每組進行插入排序public static void shell(int[] array,int gap){for(int i = gap;i < array.length;i++){int j = i - gap;int tmp = array[i];for(;j >= 0;j -= gap){if(array[j] > tmp){array[j+gap] = array[j];}else{break;}}array[j + gap] = tmp;}}
分析
- 時間復雜度:O(N^1.3 - N ^ 1.5),時間復雜度不好計算
- 空間復雜度:O(1)
- 穩定性:不穩定的排序
檢測排序速度:
public static void testInsert(int[] array){long startTime = System.currentTimeMillis();int[] tmp = Arrays.copyOf(array,array.length);Sort.insertSort(tmp);long endTime = System.currentTimeMillis();System.out.println(" " + (endTime - startTime));}public static void testShell(int[] array){long startTime = System.currentTimeMillis();int[] tmp = Arrays.copyOf(array,array.length);Sort.shellSort(tmp);long endTime = System.currentTimeMillis();System.out.println(" " + (endTime - startTime));}// 逆序初始化public static void initOrder(int[] array){for(int i = 0;i < array.length;i++){array[i] = array.length - i;}}public static void main(String[] args) {int[] arr = new int[10000];initOrder(arr);testInsert(arr);testShell(arr);}
選擇排序
- 在當前i下標對應的值的后面,找到后面最小的值和i下標對應的值交換
// 交換public static void swap(int i, int j, int[] array){int tmp = array[i];array[i] = array[j];array[j] = tmp;}// 選擇排序public static void selectSort(int[] array){// 在i下標的后面找到比i下標對應的值的最小值,然后交換int n = array.length;for(int i = 0;i < n;i++){int minIndex = i;for(int j = i + 1;j < n;j++){if(array[j] < array[i]){if(array[j] < array[minIndex]){minIndex = j;}}}swap(i,minIndex,array);}}
- 雙向選擇排序
時間復雜度還是O(N^2)
左邊找最大的,右邊找最小的,和第一個數和最后一個數交換
存在缺陷,maxIndex下標可能是在0下標是最大的,0下標會和最小值小標的值交換,那么0下標就不是最大值下標,應該更新為maxIndex = minIndex
public static void selectSort2(int[] array){// 在i下標的后面找到比i下標對應的值的最小值,然后交換int left = 0;int right = array.length - 1;while(left < right){int minIndex = left;int maxIndex = left;for(int i = left + 1;i <= right;i++){if(array[i] < array[minIndex]){minIndex = i;}if(array[i] > array[maxIndex]){maxIndex = i;}}swap(left,minIndex,array);// 第一個數是最大的數,防止最小的下標和第一個數換了,最大值就在minIndex的位置了if(maxIndex == left){maxIndex = minIndex;}swap(right,maxIndex,array);left++;right--;}}
分析
- 時間復雜度:O(N^2)
- 空間復雜度:O(1)
- 穩定性:不穩定的排序
堆排序
// 堆排序private static void shifDown(int[] array,int parent,int len){int child = 2 * parent + 1;while(child < len){if(child + 1 < len && array[child] < array[child + 1]){child++;}if(array[child] > array[parent]){swap(child,parent,array);parent = child;child = 2 * parent + 1;}else{break;}}}private static void createHeap(int[] array){// 建立大根堆for(int parent = (array.length - 1 - 1) / 2;parent >= 0;parent--) {shifDown(array, parent, array.length);}}public static void heapSort(int[] array){createHeap(array);int end = array.length - 1;while(end > 0){swap(end,0,array);shifDown(array,0,end);end--;}}
分析
- 時間復雜度:O(N * logN)
- 空間復雜度:O(1)
- 穩定性:不穩定的排序
冒泡排序
// 冒泡排序public static void bubbleSort(int[] array){// i是趟數for(int i = 0;i < array.length;i++){// j是比較的大小的boolean flag = true;for(int j = 0;j < array.length - i - 1;j++){if(array[j] > array[j + 1]){swap(j,j + 1,array);flag = false;}}if(flag) {break;}}}
分析
- 時間復雜度:O(N ^ 2)
- 空間復雜度:O(1)
- 穩定性:穩定的排序
快速排序
霍爾法
- 根據二叉樹進行遞歸劃分
// 快速排序public static void quickSort(int[] array){quick(array,0,array.length - 1);}private static void quick(int[] array,int start,int end){if(start >= end){return;}int prvot = partitionHoare(array,start,end);quick(array,start,prvot - 1);quick(array,prvot + 1,end);}private static int partitionHoare(int[] array,int left,int right){// 基準元素int tmp = array[left];// 記錄第一個基準下標int i = left;while(left < right) {// 必須先找先右再左// 找小while (left < right && array[right] >= tmp) {right--;}// 找大while (left < right && array[left] <= tmp) {left++;}swap(left, right, array);}swap(i,left,array);return left;}
- 為什么有等于號?
沒有等于號,會死循環,比如兩端都是6
- 為什么先從右邊開始,不先從左邊開始?
先走左邊的話,先遇到大的停下來,如果相遇的話,那么相遇位置的值就是大于基準元素的,這時候交換的話,6的左邊有一個數比6大
分析
- 時間復雜度:
最好情況下:O(N * logN)
每層都有N個節點,高度為logN,需要每個節點都遍歷到,N * logN次遍歷
最壞情況下:O(N^2),有序/逆序,單分支的樹 - 空間復雜度:
最好情況下:O(logN)
最壞情況下:O(N),有序/逆序,單分支的樹
遞歸左邊再遞歸右邊,遞歸右邊左邊沒有釋放 - 穩定性:不穩定的排序
挖坑法找基準
- 先走右邊再走左邊,以第一個元素為基準,并且拿出基準元素,基準元素的位置就是坑,如果右邊找到比基準小的,把它放入坑中,左邊找到比基準元素大的放到坑中,最后兩者相遇,把基準元素放入其中
// 挖坑法private static int partitionHole(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;}
前后指針法
- 如果cur比基準元素小并且cur下標的值和prev下標的值不相等,
// 前后指針法public static int partition(int[] array,int left,int right){int prev = left;int cur = left + 1;while(cur <= right){while(array[cur] < array[left] && array[++prev] != array[cur]){swap(cur,prev,array);}cur++;}swap(prev,left,array);return prev;}
題目
- 優先試挖坑法,其次是Hoare,最后是前后指針法
A
快排的優化
- 均勻的分割數組
- 讓遞歸的次數變少
三數取中法
- 三數取中法:left,right,mid三個下標中的中間值和第一個數交換位置,然后右邊找比基準元素小的值,左邊找比基準元素大的值
- 規定array[mid] <= array[left] <= array[right]
// 三數取中法,求中位數的下標private static int middleNum(int[] array,int left,int right){int mid = (left + right) / 2;if(array[left] < array[right]){// 1. x < 3 < 9// 2. 3 < 9 < x// 3. 3 < x < 9if(array[mid] < array[left]){return left;}else if(array[mid] > array[right]){return right;}else{return mid;}}else{// 9 > 3 == left > right// 1. x > left > rightif(array[mid] > array[left]){return left;}else if(array[right] > array[mid]){// 2. left > right > xreturn right;}else{// 3. left > x > rightreturn mid;}}}private static void quick(int[] array,int start,int end){if(start >= end){return;}// 1 2 3 4 5 6 7// 中間值的下標和第一個數交換,作為新的基準元素int index = middleNum(array,start,end);swap(index,start,array);// 4 2 3 1 5 6 7// 為了讓左右分布更均勻,降低樹的高度,減少遞歸的次數int prvot = partition(array,start,end);quick(array,start,prvot - 1);quick(array,prvot + 1,end);}
只剩最后幾層時,使用插入排序進行優化,降低遞歸次數,可以使用插入排序是因為前面遞歸成有序的序列了
public static void insertSort(int[] array,int left,int right){for(int i = left + 1;i <= right;i++){int j = i - 1;int tmp = array[i];for(;j >= left;j--){if(array[j] > tmp){array[j+1] = array[j];}else{break;}}array[j + 1] = tmp;}}private static void quick(int[] array,int start,int end){if(start >= end){return;}if(end - start + 1 <= 15){// 減少遞歸的次數// 因為最后幾層節點數最多,遞歸次數也多insertSort(array,start,end);return;}// 1 2 3 4 5 6 7// 中間值的下標和第一個數交換,作為新的基準元素int index = middleNum(array,start,end);swap(index,start,array);// 4 2 3 1 5 6 7// 為了讓左右分布更均勻,降低樹的高度,減少遞歸的次數int prvot = partition(array,start,end);quick(array,start,prvot - 1);quick(array,prvot + 1,end);}
非遞歸實現快排
- 找基準里面會進行交換元素,進行排序,外面就進行找到左右下標位置
// 非遞歸實現快速排序public static void quickSortNor(int[] array){int start = 0;int end = array.length - 1;Stack<Integer> stack = new Stack<>();int pivot = partitionHoare(array,start,end);if(pivot - 1 > start){// 左邊有兩個元素stack.push(start);stack.push(pivot - 1);}else if(pivot + 1 < end){// 右邊至少有兩個元素stack.push(pivot + 1);stack.push(end);}// 找基準里面會互換元素進行排序while(!stack.empty()){end = stack.pop();start = stack.pop();pivot = partitionHoare(array,start,end);if(pivot - 1 > start){// 左邊有兩個元素stack.push(start);stack.push(pivot - 1);}else if(pivot + 1 < end){// 右邊至少有兩個元素stack.push(pivot + 1);stack.push(end);}}
歸并排序
-
分解:根據mid進行分解
-
合并:第一個有序段和第二個有序段,比較大小放入一個新的數組中
// 歸并排序public static void mergeSort(int[] array){merge(array,0,array.length - 1);}private static void merge(int[] array,int start,int end){if(start >= end){return;}int mid = (start + end) / 2;// 分解merge(array,start,mid);merge(array,mid + 1,end);// 合并mergeHeB(array,start,mid,end);}private static void mergeHeB(int[] array, int left, int mid, int right) {int s1 = left;int e1 = mid;int s2 = mid + 1;int e2 = right;// 新數組的下標int k = 0;int[] tmpArray = new int[right - left + 1];while(s1 <= e1 && s2 <= e2){if(array[s1] < array[s2]){tmpArray[k++] = array[s1++];}else{tmpArray[k++] = array[s2++];}}while(s1 <= e1){tmpArray[k++] = array[s1++];}while(s2 <= e2){tmpArray[k++] = array[s2++];}// left是因為有左邊還有右邊的數組// tmpArray是臨時數組,會銷毀的,需要拷貝回原來的數組for(int i = 0;i < tmpArray.length;i++){array[i + left] = tmpArray[i];}}
分析
- 時間復雜度:O(N * logN)
- 空間復雜度:O(N),因為每次合并數組的時候要開O(N)大小的額外空間
- 穩定性:穩定的排序
非遞歸實現歸并排序
- 先一個一個有序,兩個兩個有序,四個四個有序,八個八個有序…
- gap = 1
left = i
mid = left + gap - 1
right = mid + gap
gap *= 2 - 每組合并完,最終就有序了
// 非遞歸實現歸并排序public static void mergeSortNor(int[] array){// gap表示每組的數據個數int gap = 1;while(gap < array.length){for(int i = 0;i < array.length;i = i + 2 * gap){int left = i;// mid和right可能會越界// 比如只有5個元素// 分解右邊一半的時候// l = i mid = 5 r = 7int mid = left + gap - 1;int right = mid + gap;if(mid >= array.length){mid = array.length - 1;}if(right >= array.length){right = array.length - 1;}mergeHeB(array,left,mid,right);}gap *= 2;}}
海量數據的排序
- 使用歸并排序進行外部排序,如果內存中不夠空間的話
非比較的排序
計數排序
- 通過統計每次數字出現的次數,最后按照順序從小到大輸出這些數字
- 適用的場景:指定范圍內的數據
// 計數排序,指定范圍內的數據進行排序
// O(Max(N,范圍))public static void countSort(int[] array){int minVal = array[0];int maxVal = array[0];// O(N)for(int i = 0;i < array.length;i++){if(minVal > array[i]){minVal = array[i];}if(maxVal < array[i]){maxVal = array[i];}}int len = maxVal - minVal + 1;int[] count = new int[len];// O(N)for(int i = 0;i < array.length;i++){count[array[i] - minVal]++;}// 寫回array數組中// O(范圍)// 因為count數組集中于一個數字,那么也是O(范圍)// 如果count數組不集中于一個數子,也是N倍的范圍// 也是O(范圍)int k = 0;for(int i = 0;i < count.length;i++){while(count[i] > 0){array[k++] = i + minVal;count[i]--;}}}
分析
- 時間復雜度:O(Max(N,范圍))
- 空間復雜度:O(范圍)
- 穩定性:穩定的排序
基數排序
- 開10個大小的空間,分別依次比較個位大小,十位大小和百位大小,最終達到有序,每個空間都是一個隊列
桶排序
- 先把數字放入一個范圍的區間內進行排序,排好序依次拿出來,最終就有序了