七種 基于比較 的排序：
- 1、插入排序：（元素少時插排最快）
- 2、希爾排序：
- 3、選擇排序：
- 4、堆排序：
- 5、冒泡排序：
- 6、快速排序：（重點）
- 7、歸并排序：（重點）
- 排序總結：
1、插入排序：（元素少時插排最快）
1、[ 有序區間（黃色區間），無序區間（藍色區間） ]
每次操作：
- 1、抓無序區間（右側藍區）的第一張牌（紅色牌）
- 2、依次和有序區間（左側黃區）的牌比較（綠色為正在比較的牌）
- 3、選擇適合的位置插入
動圖展示：
代碼實作：
public static void insertSort(long[] array) {
for (int i = 0; i < array.length - 1; i++) {
//1、抓無序區間第一張牌(紅色牌)
long key = array[i + 1];
//2、將取出的牌依次和有序區間的牌比較
int j;
for (j = i; j >= 0; j--) {
//如果取出 紅色的牌的值 < 綠色牌的值
if (key < array[j]) {
//將 綠牌 往后挪一個位置
array[j + 1] = array[i];
} else {
break;
}
}
//3、選擇合適的位置插入
array[j + 1] = key;
}
}
性能分析：
| 時間復雜度 | 空間復雜度 | ||
|---|---|---|---|
| 最好 | 平均 | 最壞 | |
| O(n) | O(n^2) | O(n^2) | O(1) |
| 資料有序 | 資料逆序 |
具備穩定性（相等的兩個數相對位置不會變），插入排序，初始資料越接近有序，時間效率越高
2、希爾排序：
希爾是發明者（ShellSort）
插排的優化版（分組插排排序）
排序步驟：（分為幾組，就意味著中間間隔是多少）（組數一般為 陣列長度 / 2）（下次的組數為上次組數的一半）
- 1、將陣列按不同顏色依次分成了 5 組：然后進行組內比較大小，調換順序
- 2、將第一次調整好的陣列分成 2 組：然后進行組內比較大小，調換順序
- 3、將第二次調整好的陣列進行整體比較
動圖展示：
代碼實作：
public static void shellSort(long[] array) {
//gap為間隔，也就是分為了幾組
int gap = array.length / 2;
while (true) {
insertSortGap(array,gap);
if (gap == 1) {
break;
}
//下次的組數為上次組數的一半
gap = gap / 2;
}
}
public static void insertSortGap(long[] array,int gap) {
for (int i = gap; i < array.length; i++) {
// key 為同一組中的第二個數
long key = array[i];
int j = 0;
//同一組中的第一個數
for (j = i - gap; j >= 0; j = j -gap) {
//第二個數 < 第一個數
if (key < array[j]) {
//第二個數的值 = 第一個數的值
array[j + gap] = array[j];
} else {
break;
}
}
//第一個數 = 之前保存的第二個數的值（此時的 j 是一個負數，加上 gap 剛好為第一個數）
array[j + gap] = key;
}
}
性能分析：
| 時間復雜度 | 空間復雜度 | ||
|---|---|---|---|
| 最好 | 平均 | 最壞 | |
| O(n) | O(n^1.3) | O(n^2) | O(1) |
| 資料有序 | 比較難構造 |
不穩定
3、選擇排序：
[ 有序區間（黃色區間），無序區間（藍色區間）]
每一次從無序區間選出最小（或最大）的一個元素，存放在無序區間的最前（或最后），直到全部待排序的資料元素排完
動圖展示：
代碼實作：
public static void selectSort(long[] array) {
for (int i = 0; i < array.length - 1; i++) {
//有序區間：[0,i)
//無序區間：[i,array.length]
int minIndex = i;//最小數下標
//先從無序區間中找到最小的數
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
//交換這個 最小數 和 無序區間的第一個數
long t = array[minIndex];
array[minIndex] = array[i];
array[i] = t;
}
}
性能分析：
| 時間復雜度 | 空間復雜度 |
|---|---|
| O(n^2) | O(1) |
| 資料不敏感 | 資料不敏感 |
不穩定：（相等的兩個數相對位置會變）
int[] a = { 9, 2, 5a, 7, 4, 3, 6, 5b };
// 交換中該情況無法識別，保證 5a 還在 5b 前邊
4、堆排序：
隨便給一組資料：[ 20,17,16,5,4,3 ]
（無序區間，我們用下劃線的方式表示）（有序區間：用小藍圈來表示）
排序流程：
- 1、建大堆：[ 20,17,4,16,5,3 ]
- 2、從大堆中找出最大值（堆頂元素），和無序區間的最后一個數字交換
- 3、此時陣列中左邊是無序區間，右邊是有序區間，用來存放最大值
- 4、交換完數字后，需要對交換的堆頂元素進行向下調整為大頂堆（不包括有序區間）
- 5、回圈遍歷該程序
不能通過小堆來實作，因為有序區間放在開頭的話，堆的邏輯結構就構不成二叉樹了
代碼實作：
public static void heapSort(long[] array) {
//1、建大堆
createHeap(array,array.length);
//2、進行選擇的程序，一共需要 array.length - 1組
for (int i = 0; i < array.length - 1; i++) {
//無序區間：[ 0,array.length - 1]
//交換0號下標（大堆中0號下標為堆中最大值）和無序陣列中最后一個元素
long t = array[0];
array[0] = array[array.length - 1 - i];
array[array.length - 1 - i] = t;
// 無序區間變為：[ 0,array - i - 1]
//向下調整
adjustDown(array,array.length-1-i,0);
}
}
//建大堆
private static void createHeap(long[] array, int size) {
for (int i = (size - 2) / 2; i >= 0; i--) {
adjustDown(array,size,i);
}
}
//向下調整
private static void adjustDown(long[] array, int size, int index) {
while (true) {
//1、判斷該結點是不是葉子結點
int leftIndex = 2 * index + 1;
if (leftIndex >= size) {
//左孩子不存在，該節點是葉子結點
return;
}
//2、找出最大的孩子
int maxIndex = leftIndex;
int rightIndex = 2 * index + 2;
if (rightIndex < size && array[rightIndex] > array[maxIndex]) {
maxIndex = rightIndex;
}
//3、比較最大孩子和該節點的大小
if (array[index] >= array[maxIndex]) {
//當前結點的值大于兩個孩子的值，則無須交換
return;
}
//4、交換
long t = array[index];
array[index] = array[maxIndex];
array[maxIndex] = t;
//5、將最大孩子視為 index，回圈回去
index = maxIndex;
}
性能分析：
| 時間復雜度 | 空間復雜度 |
|---|---|
| O(n*log(n)) | O(1) |
| 資料不敏感 | 資料不敏感 |
不穩定
5、冒泡排序：
[ 無序區間（藍色區間），有序區間（黃色區間）]
綠色為兩個正在比較的牌
在無序區間（藍色區間），通過相鄰兩個數的比較，將最大的數冒泡到無序區間的最后，持續這個程序
動圖展示：
代碼實作：
public static void bubbleSort(long[] array) {
for (int i = 0; i < array.length - 1; i++) {
//無序區間：[0,array.length - 1]
//有序區間：[array.length - i,array.length]
//每次進行冒泡之前，假設陣列已經有序
boolean isSorted = true;
//進行冒泡程序
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
long t = array[j];
array[j] = array[j + 1];
array[j + 1] = t;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
性能分析：
| 時間復雜度 | 空間復雜度 | ||
|---|---|---|---|
| 最好 | 平均 | 最壞 | |
| O(n) | O(n^2) | O(n^2) | O(1) |
| 資料有序 | 資料逆序 |
穩定（當兩個數字相同時，不交換兩個數字的位置）
6、快速排序：（重點）
步驟：
- 1、從陣列中選擇一個數（一般是最左邊的那個數），作為基準
- 2、實作 partition 方法（小于 基準的放 左邊，大于 基準的放 右邊）
- 3、分別對左右兩個區間按同樣的方法處理
- 4、直到（小區間有序： size = 0 / 1）
例如：給定陣列：[ 5,2,1,7,3,6,9 ]
（我們用紅框來表示基準）
解法類似一顆二叉樹
最終結果： [ 1,2,3,5,6,7,9 ]
動圖展示：
代碼實作：
public static void quickSort(long[] array) {
quickSortInternal(array,0,array.length - 1);
}
//給定位置之間采用快排
private static void quickSortInternal(long[] array, int lowIndex, int highIndex) {
//4、區間內的個數 = 0 / 1時，結束
int size = highIndex - lowIndex + 1;
if (size <= 1) {
return;
}
//1、選出一個數（選擇最左邊的）- array[lowIndex]
//2、執行 partition，小的放左，大的放右
//keyIndex 是經過 partition之后，選出來的數最終所在的下標（一次 partition之后，紅框的位置）
int keyIndex = partition(array,lowIndex,highIndex);
//3、分別對左右區間進行相同處理 - 遞回
quickSortInternal(array,lowIndex,keyIndex - 1);
quickSortInternal(array,keyIndex + 1,highIndex);
}
//以選出的 lowIndex 位置下的元素為基準，遍歷陣列，把比基準元素小的放到他左邊，比他大的放右邊
private static int partition(long[] array, int lowIndex, int highIndex) {
//選擇合適的方法:
//方法1：
//return hover(array,lowIndex,highIndex);
//方法2：
//return digAHole(array,lowIndex,highIndex);
//方法3：
return doublePointer(array,lowIndex,highIndex);
}
實作 partition 方法：
- 方法1：Hover 法
private static int hover(long[] array, int lowIndex, int highIndex) {
int leftIndex = lowIndex;
int rightIndex = highIndex;
// 選擇的數是最左邊的一個
long key = array[lowIndex];
//選擇了最左邊，從右邊先開始
//因為從右邊寫起來比較簡單，從左邊開始寫需要處理特殊情況，較復雜
while (leftIndex < rightIndex) {
while (leftIndex < rightIndex && array[rightIndex] >= key) {
rightIndex--;
}
while (leftIndex < rightIndex && array[leftIndex] <= key) {
leftIndex++;
}
//rightIndex下標遇到比基數小的數，leftIndex下標遇到比基數大的數，則，交換兩個數字
swap(array,leftIndex,rightIndex);
}
swap(array,lowIndex,leftIndex);
return leftIndex;
}
private static void swap(long[] array,int index1,int index2) {
long t = array[index1];
array[index1] = array[index2];
array[index2] = t;
}
- 方法2：挖坑法（效率最高）
private static int digAHole(long[] array, int lowIndex, int highIndex) {
//key 代表基數，將其挖出，則該位置為空
long key = array[lowIndex];
int leftIndex = lowIndex + 1;
int rightIndex = highIndex;
while (leftIndex < rightIndex) {
while (leftIndex < rightIndex && array[rightIndex] >= key) {
rightIndex--;
}
//把右邊小于基數的那個數填到之前左邊挖出的坑中
array[lowIndex] = array[rightIndex];
while (leftIndex < rightIndex && array[leftIndex] < key) {
leftIndex++;
}
//把左邊大于基數的那個數填到上邊空出的那個位置
array[rightIndex--] = array[leftIndex++];
}
//將 key 放回剩余的坑中
array[rightIndex] = key;
return rightIndex;
}
- 方法3：前后遍歷法：
設定兩個指標，依次往后遍歷，當遇到 > 基準值的時候，讓 separateIndex下標不動，i 繼續遍歷，遍歷到 < 基準值的時候，交換兩下標的值，最后交換 separateIndex 的前一個值和基準的值
private static int doublePointer(long[] array, int lowIndex, int highIndex) {
int separateIndex = lowIndex + 1;
for (int i = lowIndex + 1; i <= highIndex; i++) {
if (array[i] < array[lowIndex]) {
swap(array,i,separateIndex);
separateIndex++;
}
}
swap(array,lowIndex,separateIndex - 1);
return separateIndex - 1;
}
private static void swap(long[] array,int index1,int index2) {
long t = array[index1];
array[index1] = array[index2];
array[index2] = t;
}
性能分析：
每一次 partition 時間復雜度是 O(n)，一共多少層，看二叉樹的高度（二叉樹一般是 log(n)，最壞是 n）
| 時間復雜度 | 空間復雜度 | ||||
|---|---|---|---|---|---|
| 最好 | 平均 | 最壞 | 最好 | 平均 | 最壞 |
| O(n*log(n)) | O(n*log(n)) | O(n^2) | O(log(n)) | O(log(n)) | O(n) |
| 資料有序 |
不穩定
快排優化：
- 1、partition 挖坑（小細節優化）
- 2、數量比較少的時候，不是最快（當區間的個數低于某個閾值時（16），使用插排）
- 3、優化選擇特殊的數的方式
（1）亂數
（2）挑幾個數，選大小為中間值的（三數取中） - 4、把相等的值特殊處理
7、歸并排序：（重點）
分治法 思想：
- 1、把陣列平均分成兩份，分別對左右兩個區間，進行相同方式處理（歸并排序），直到區間內個數（size = 0 / 1）
- 2、合并左右兩個有序陣列
代碼實作：
public static void mergeSort(long[] array) {
mergeSortInternal(array,0,array.length);
}
//區間范圍時左閉右開的
// array[lowIndex,highIndex ]
private static void mergeSortInternal(long[] array, int lowIndex, int highIndex) {
int size = highIndex - lowIndex;
if (size <= 1) {
return;
}
int midIndex = (highIndex + lowIndex) / 2;
// 左區間：[lowIndex,midIndex)
// 右區間：[midIndex,highIndex)
mergeSortInternal(array,lowIndex,midIndex);
mergeSortInternal(array,midIndex,highIndex);
// 左右兩個區間有序，進行合并
mergeOrderedIntervals(array,lowIndex,midIndex,highIndex);
}
// 新建一個額外陣列，將需要合并的兩個陣列中依次取出元素進行比較，在放入額外陣列中
private static void mergeOrderedIntervals(long[] array, int lowIndex, int midIndex, int highIndex) {
int size = highIndex - lowIndex;//新陣列長度
long[] extra = new long[size];
int leftIndex = lowIndex;//左邊陣列的下標
int rightIndex = midIndex;//右邊陣列的下標
int i = 0;//新陣列下標
// 兩個陣列中都有元素
while (leftIndex < midIndex && rightIndex < highIndex) {
// <= 保證穩定性
if (array[leftIndex] <= array[rightIndex]) {
extra[i] = array[leftIndex];
leftIndex++;
} else {
extra[i] = array[rightIndex];
rightIndex++;
}
i++;
}
// 已經有陣列空了，則將另外一個陣列全部放入新陣列中
if (leftIndex < midIndex) {
//右邊陣列為空
while (leftIndex < midIndex) {
extra[i++] = array[leftIndex++];
}
} else {
//左邊陣列為空
while (rightIndex < highIndex) {
extra[i++] = array[rightIndex++];
}
}
//在將原陣列中的值換為新陣列的值
for (int j = 0; j < size; j++) {
array[lowIndex + j] = extra[j];
}
}
性能分析：
| 時間復雜度 | 空間復雜度 |
|---|---|
| O(n*log(n)) | O(n) |
| 資料不敏感 | 資料不敏感 |
穩定
擴展：
排序演算法都是在記憶體中進行的，當出現 海量資料 時，記憶體存不下，必須借助硬碟，采用歸并排序（多路歸并）
步驟：
- 1、先將資料平均分為 n 份（每份的大小較小）
- 2、分別對每份資料進行排序
- 3、至此，得到 n 個分別有序的資料檔案
- 4、借助記憶體，進行 n 個有序資料檔案的合并
（1）將每份檔案中最小的數放入記憶體中
（2）將最小的數選出來，尾插到最后的有序檔案中
n 多個資料以檔案的形式放到磁盤上，把每個資料的第一個數選出來作為代表放到記憶體中，比較，誰小就放到最終的結果檔案中，尾插進去
排序總結：
| 排序方法 | 最好 | 平均 | 最壞 | 空間復雜度 | 穩定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩定 |
| 希爾排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不穩定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩定 |
| 堆排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(1) | 不穩定 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩定 |
| 快速排序 | O(n*log(n)) | O(n*log(n)) | O(n^2) | O(log(n)) ~ O(n) | 不穩定 |
| 歸并排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(n) | 穩定 |
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/275545.html
標籤：其他