排序算法-冒泡、選擇、堆、插入、歸併、快速、希爾
- 2022 年 8 月 15 日
- 筆記
- 排序算法-冒泡、選擇、堆、插入、歸併、快速、希爾
- 排序算法，默認是升序，左邊的值是屬於「小」值
理解比較大小後的交換：當前元素cur 和 左邊的元素cur-1， 左邊的比較大，就交換或者挪動 array[cur] = array[cur-1];
- 編碼的區間設置：建議是左閉 右開，方便 [begin, end)
- 計算方面：使用右移 代替 除法
☺ 排序算法—重點放到比較的排序算法—冒泡、選擇、堆排序 插入、歸併、快速、希爾，
對於計數排序、基數排序不是面試的重點
排序算法-冒泡、選擇、堆排序
一、冒泡排序：
為什麼要叫冒泡排序？ 因為形象生動上，每一輪都是最大的那個數冒到結尾
定義：
① 從頭開始index=1 比較每一對相鄰元素，如果第1個比第2個大，就交換它們的位置；執行完一輪後，最末尾那個元素就是最大的元素。
② 忽略 ① 中曾經找到的最大元素，重複執行步驟 ①，直到全部元素有序。
【一輪的比較範圍是從1 到 end，然後根據理解得到end 從最後一個元素開始不斷減少】
- 第一輪的比較，下標從1開始，左邊比右邊大進行交換
int array[] = {1, 3, 5, -1, -8};
//比較 end 的結束範圍，從最後一個元素-第二個元素
for(int end = array.length - 1; end > 0; end--) {
//冒泡排序-一輪的交換
for(int begin = 1; begin <= end; begin++) {
if(array[begin] < array[begin-1]) {//當前元素的左邊元素比較大時要交換
int temp = array[begin];
array[begin] = array[begin-1];
array[begin-1]=temp;
}
}
}
優化1-冒泡排序
▪ 提前有序，終止比較（不一定有用：因為一般在隨機數據中要提前有序的概率是很低的，）
- 布爾變量：假設本輪已經有序
//比較 end 的結束範圍，從最後一個元素-第二個元素
for(int end = array.length - 1; end > 0; end--) {
boolean sorted = true;//假設提前有序
//冒泡排序-一輪的交換
for(int begin = 1; begin <= end; begin++) {
if(array[begin] < array[begin-1]) {//當前元素的左邊元素比較大時要交換
int temp = array[begin];
array[begin] = array[begin-1];
array[begin-1]=temp;
sorted = false;//本輪有交換，證明假設提前有序 不成立
}
}
if(sorted) break;//果然提前有序，不用再比較了
}
優化2-冒泡排序
- 如果序列尾部已經局部是有序的，可以記錄最後一次交換的位置，從而減少比較的次數。
int array[] = {1, 3, 5, -1, -8};
//比較 end 的結束範圍，從最後一個元素-第二個元素
for(int end = array.length - 1; end > 0; end--) {
int sortedIndex = 1;//記錄最後一次交換的位置，初始值為1，是為了考慮一開始數組就是完全有序的
//冒泡排序-一輪的交換
for(int begin = 1; begin <= end; begin++) {
if(array[begin] < array[begin-1]) {//當前元素的左邊元素比較大時要交換
int temp = array[begin];
array[begin] = array[begin-1];
array[begin-1]=temp;
sortedIndex = begin;//記錄最後一次交換的位置
}
}
end = sortedIndex;//更新比較範圍到最後一次交換的位置
}
二、選擇排序
為什麼要叫選擇排序？ 因為每一輪都是把最大的那個數的位置給選擇出來
定義：
① 從序列中找出最大的那個元素，然後與最末尾的元素交換位置；執行完一輪後，最末尾的那個元素就是最大的元素。
② 忽略 ① 中曾經找到的最大元素，重複執行步驟 ①
▪ 選擇排序本質上看是冒泡的優化：
因為冒泡是從頭到尾：相鄰兩個元素比較完就交換
選擇排序是從頭到尾：先找到最大元素位置，然後記錄位置，最後才交換
int array[] = {1, 3, 5, -1, -8};
//比較 end 的結束範圍，從最後一個元素-第二個元素
for(int end = array.length - 1; end > 0; end--) {
int maxIndex = 0;
//選擇排序-找出本輪的最大值
for(int begin = 1; begin <= end; begin++) {
if(array[maxIndex] <= array[begin]) {//取等號是為了變成穩定的排序算法 10 10() 8 --一輪比較--> 10 8 10()
maxIndex = begin;
}
}
//交換，把本輪找到的最大一個數放到結尾
int temp = array[maxIndex];
array[maxIndex] = array[end];
array[end] = temp;
}
三、堆排序
▪ 堆排序本質上看是冒泡的優化：
選擇排序是從頭到尾：每一輪都在 從頭到尾找到最大元素位置（內循環在找最大值）
—- 找最值，可以交給堆負責（優化）
▪ 堆排序：先原地建堆，然後尾部元素放到堆頂，然後下濾
int array[] = {1, 3, 5, -1, -8};
// 原地建堆
heapSize = arrayay.length;
for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
while (heapSize > 1) {
// 交換堆頂元素和尾部元素
int temp = array[0];
array[0] = array[heapSize];
array[heapSize] = temp;
heapSize--;
// 對0位置進行siftDown（恢復堆的性質）
siftDown(0);
}
/**
* 下濾
*/
private void siftDown(int index) {
int half = heapSize >> 1;
Integer element = array[index];
while(index < half) { //index 必須是非葉子節點！！！
// 默認拿是左邊跟父節點比大小
int childIndex = (index << 1) + 1;
Integer childElement = array[childIndex];
int rightIndex = childIndex + 1;
if(rightIndex < size
&& compare(array[rightIndex], childElement) > 0) {
childElement = array[childIndex = rightIndex];
}
if(compare(element, childElement) >= 0) break;
//子結點大的話
array[index] = childElement;
index = childIndex;
}
array[index] = element;
}
排序算法-插入排序
一、插入排序
插入排序非常類似於撲克牌的排序
定義：① 在執行過程中，插入排序會將序列分為2部分；頭部是已經排好序的，尾部是待排序的
② 從頭開始掃描每一個元素；每當掃描到一個元素，就將它插入到頭部合適的位置，使得頭部數據依然保持有序
private void sort(Integer[] array) {
------------------------------------------- 核心代碼開始 ------------------------------------------------------------
for(int begin = 1; begin < array.length; begin++) {//從無序區抓起的牌
int cur = begin;
while(cur > 0 && cmp(array[cur], array[cur - 1]) < 0) {//這張牌不斷往左邊走，和緊鄰[cur-1]的頭部有序區進行比較,小於左邊就交換
swap(array[cur], array[cur - 1]);
cur--;//交換完，這個牌的位置
}
}
------------------------------------------- 核心代碼結束 ------------------------------------------------------------
}
protected int cmp(int v1, int v2) {
return v1 - v2;
}
protected void swap(int v1, int v2) {
int tmp = v1;
v1 = v2;
v2 = tmp;
}
優化1-插入排序
- 優化：挪動替換交換
private void sort(Integer[] array) {
for(int begin = 1; begin < array.length; begin++) {//從無序區抓起的牌
int cur = begin;
Integer v = array[cur];
while(cur > 0 && cmp(v, array[cur - 1]) < 0) {//頭部有序數據中比待插入元素大的，都朝尾部方向挪動1個位置
array[cur] = array[cur-1];//左邊的值比較大就往右邊挪動
cur--;
}
//找到合適的位置，插入
array[cur] = v;
}
}
優化2-插入排序
-
找位置–使用二分搜索法(通過挪動左右指針，不斷縮小一半的可能範圍)
-
使用二分搜索優化了比較次數
細節：二分搜素的開始-結束區間[begin, end）
-
int begin = 0； int end = array.length;
-
為什麼結束要取 end，因為方便後續其他計算，比如算出該區間有多少元素
-
-
優化二分搜素[原：查找位置]為[查找待插入的位置]
▪ 原：查找到位置
查找目標位置的：查找過程分成三種判斷條件：小於，去左邊查找；大於，去右邊查找；等於直接返回目標
▪ 現：查找到待插入位置
查找待插入的目標位置的：查找過程分成兩種種判斷條件：小於，去左邊查找；大等於，去右邊查找；因為這個等於不是待插入的目標位置
- 待插入的目標位置是第一個大於 待插入原始的值v 的元素位置
/**
* 查找待插入位置的索引
*/
private int search(int index) {//index 是待插入索引
int begin = 0;
int end = index;
while(begin < end) {
int mid = (begin + end) >> 2;
if(cmp(array[index], array[mid]) < 0) {
end = mid;
}else {
begin = mid + 1;
}
}
return begin;
}
private void sort(Integer[] array) {
for(int begin = 1; begin < array.length; begin++) {//從無序區抓起的牌
Integer v = array[begin];//備份插入元素
int insertIndex = search(begin);//查找到合適的插入位置
for(int i = begin; i > insertIndex; i--) {//挪動騰出空間
array[i] = array[i - 1];
}
array[insertIndex] = v;
}
}
排序算法-歸併排序
一、歸併排序
定義：
① 不斷地將當前序列平均分割成2個子序列；直到不能再分割（序列中只剩1個元素）
② 不斷地將2個子序列合併成一個有序序列；直到最終只剩下1個有序序列
int[] leftArray;
int[] array;
private void sort(int begin, int end) {
if(end - begin < 2) return;//至少要有2個元素
int mid = (begin + end) >> 1;
sort(begin, mid);//左邊歸併
sort(mid, end);//右邊歸併
merge(begin, mid, end);//最後進行合併
}
/**
* 將 [begin, mid) 和 [mid, end) 範圍的序列數組合併成一個有序序列
*/
private void merge(int begin, int mid, int end) {
int li = 0, le = mid - begin;//左邊數組leftArray
int ri = mid, re = end;//右邊數組
int ai = begin;//arrayay 的索引
for(int i = li; i < le; i++) {//拷貝arrayay左邊數組到leftArray
leftArray[i] = array[begin + i];
}
while(li < le) {//左邊還有元素
if(ri < re && cmp(array[ri], leftArray[li]) < 0) {//右邊有元素，且右邊的值更加小
array[ai++] = array[ri++];
}else {
array[ai++] = leftArray[li++];//左邊有元素，且左邊的值更加小
}
}
排序算法-快速排序、希爾排序
一、快速排序
快速排序的本質：逐漸將每一個元素都轉換成軸點元素
定義：
① 從序列中選擇一個軸點元素（pivot）
▪ 假設每次選擇 0 位置的元素為軸點元素
② 利用 pivot 將序列分割成 2 個子序列
▪ 將小於 pivot 的元素放在pivot前面（左側）
▪ 將大於 pivot 的元素放在pivot後面（右側）
▪ 等於pivot的元素放哪邊都可以
③ 對子序列進行 ① ② 操作
▪ 直到不能再分割（子序列中只剩下1個元素）
是一個遞歸排序：從軸點切分成兩部分，不斷地對左部分進行快速排序，不斷地對右部分進行快速排序
判斷該元素是 “甩”到左邊 還是 右邊，不加等號，因為加上等號會使得軸點元素分割出來的子序列極度不均勻
- 比如 6 6 6 6 6，軸點是6，那麼取等號，全部給甩到一邊了
int[] array;
private void sort(int begin, int end) {
if(end - begin < 2) return;//至少要有兩個元素
int mid = pivotIndex(begin, end);//軸點，以軸點分割成了左右兩部分
sort(begin, mid);//對左部分進行快速排序
sort(mid + 1, end);//對右部分進行快速排序
}
/**
* 對 [begin, end) 範圍內的元素進行快速排序
*/
private int pivotIndex(int begin, int end) {
swap(begin, begin + (int)(Math.random() * (end - begin)));//隨機交換begin位置的元素
Integer pivot = array[begin];//備份軸點元素
end--;//讓右邊指針直到元素上
------------------------------------------- 核心代碼開始 ------------------------------------------------------------
while(begin < end) {
//內部使用了兩個while 搭配 break，實現在右邊找「小」、在左邊找「大」後，對數組指針指向"調頭"
while(begin < end) { //不加等號，因為加上等號會使得軸點元素分割出來的子序列極度不均勻
if(cmp(pivot, array[end]) < 0) {// 右邊元素>軸點元素,不是目標，要在右邊找「小」
end--;
}else {
array[begin++] = array[end];
break;
}
}
while(begin < end) {
if(cmp(pivot, array[begin]) > 0) {// 左邊元素<軸點元素,不是目標，要在左邊找「大」
begin++;
}else {
array[end--] = array[begin];
break;
}
}
}
------------------------------------------- 核心代碼結束 ------------------------------------------------------------
array[begin] = pivot;//數組軸點元素進行賦值
return begin;
}
protected int cmp(int v1, int v2) {
return v1 - v2;
}
protected void swap(int v1, int v2) {
int tmp = v1;
v1 = v2;
v2 = tmp;
}
二、希爾排序
切分成n 列然後進行排序–> 逆序對數量逐漸減少 –> 希爾排序，底層是使用插入排序，也可以把希爾看成是對插入排序的改進版
int[] array;
private void sort() {
List<Integer> stepSequence = shellStepSequence();
for(Integer step: stepSequence) {//按照每個步長進行切割，然後進行一一對應的比較 排序
sort(step);
}
}
/**
* 按照給定的步長進行切割，然後對 step 列進行排序
*/
private void sort(Integer step) {
------------------------------------------- 核心代碼開始 ------------------------------------------------------------
// col: 第幾列
for(int col = 0; col < step; col++) {//對col列進行排序
// 第col 列中的元素: col、col+2*step、col+3*step、col+4*step
// 結合了步長的插入排序
for(int begin = col + step; begin < array.length; begin++) {
int cur = begin;
while(cur > col && cmp(array[cur], array[cur - step]) < 0) {
swap(array[cur], array[cur - step]);
cur -= step;
}
}
}
------------------------------------------- 核心代碼結束 ------------------------------------------------------------
}
/**
* 步長序列：獲取 step 步長分割數組
*/
private List<Integer> shellStepSequence(){
List<Integer> stepSequence = new ArrayList<>();
int step = array.length;
while((step >>= 1) > 0) {
stepSequence.add(step);
}
return stepSequence;
}
protected int cmp(int v1, int v2) {
return v1 - v2;
}
protected void swap(int v1, int v2) {
int tmp = v1;
v1 = v2;
v2 = tmp;
}
▪ 冒泡、選擇、插入、歸併、快速、希爾、堆排序，都是基於比較的排序 [面試會考]
- 平均時間複雜度目前最低是 O(nlogn)
▪ 計數排序、桶排序、基數排序，都不是基於比較的排序 [面試不考，作為了解]
- 它們是典型的用空間換時間，在某些時候，平均時間複雜度可以比 O(nlogn) 更低
排序算法-計數排序、基數排序、桶排序
一、計數排序
細節：在java 整型數組，new出數組之後，內部元素默認都是 0
int counts = new int[10]; //new 完，默認所有元素都是0
int[] array;
private void sort() {
//找出最大值
int max = array[0];
for(int i = 1; i < array.length; i++) {
if(array[i] > max) {
max = array[i];
}
}
------------------------------------------- 核心代碼開始 ------------------------------------------------------------
// 開闢內存空間，存儲每一個整數出現的次數
int[] counts = new int[1 + max];//整型數組，new出數組之後，內部元素默認都是 0
//統計每個整數出現的次數
for(int i = 0; i < array.length; i++) {
counts[array[i]]++;
}
//根據整數出現次數，對整數進行排序
int index = 0;//整數數組上的指針
for(int i = 0; i < counts.length; i++) {
while(counts[i]-- > 0) {
array[index++] = i;
}
}
------------------------------------------- 核心代碼結束 ------------------------------------------------------------
}
■ 計數排序缺點：
-
無法對負整數進行排序
-
極其浪費內存空間
-
是個不穩定的排序
■ 計數排序的優化
int[] array;
private void sort() {
// 找出最大值、最小值
int max = array[0];//最大值
int min = array[0];//最小值
for(int i = 1; i < array.length; i++) {
if(array[i] > max) {
max = array[i];
}
if(array[i] < min) {
min = array[i];
}
}
------------------------------------------- 核心代碼開始 ------------------------------------------------------------
//開闢內存空間，存儲次數
int[] counts = new int[max - min + 1];
//統計每個整數出現的次數
for(int i = 0; i < array.length; i++) {
counts[array[i] - min]++;
}
//累加次數
for(int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
//從後往前遍曆元素，將它放到有序數組中的合適位置
int[] newArray = new int[array.length];
for(int i = array.length - 1; i >= 0; i--) {
newArray[--counts[array[i] - min]] = array[i];// 公式 count[k - min] -p 其中p是該元素k倒數着出現的次數
}
------------------------------------------- 核心代碼結束 ------------------------------------------------------------
//將有序數組賦值到array
for(int i = 0; i < newArray.length; i++) {
array[i] = newArray[i];
}
}
二、基數排序
定義：依次對個位數、十位數、百位數、千位數、萬位數…進行排序（從低位到高位）
int[] array;
private void sort() {
// 找出最大值
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
// max = 593
// 個位數 array[i] / 1 % 10 = 3
// 十位數 array[i] / 10 % 10 = 9
// 百位數 array[i] / 100 % 10 = 5
for (int divider = 1; divider <= array.length; divider *= 10) {
countingSort(divider);
}
}
private void countingSort(int divider) {
// 開闢內存空間，存儲次數
int[] counts = new int[10];//給個位數、十位數、百位數排序，它們的範圍都是 0-9
// 統計每個整數出現的次數
for (int i = 0; i < array.length; i++) {
// counts[array[i]的基數]++;
counts[array[i] / divider % 10]++;
}
// 累加次數
for (int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
// 從後往前遍曆元素，將它放到有序數組中的合適位置
int[] newArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
// newArray[--counts[array[i]的基數] = array[i];
newArray[--counts[array[i] / divider % 10]] = array[i];
}
// 將有序數組賦值到array
for (int i = 0; i < newArray.length; i++) {
array[i] = newArray[i];
}
}
■ 基數排序的另外一種思路：元素先存到桶里，然後再回收
三、桶排序
如果本文對你有幫助的話記得給一樂點個贊哦，感謝！
