📢博客主頁：🏀敲代碼的布萊恩特🏀
📢歡迎點贊 👍 收藏 ?留言 📝 歡迎討論！👏
📢本文由 【敲代碼的布萊恩特】 原創，首發于 CSDN🙉🙉🙉
📢由于博主是在學小白一枚，難免會有錯誤，有任何問題歡迎評論區留言指出，感激不盡！?
📖精品專欄（不定時更新）【JavaSE】 【Java資料結構】【LeetCode】
【Java資料結構】想進大廠必須牢記于心的——常見八大排序演算法
- 🛸基本概念
- ?排序
- ?穩定性
- 🛸七大基于比較的排序
- ?插入排序
- 🎄1. 直接插入排序
- 🎄2. 希爾排序（直接插入排序的優化）
- ?選擇排序
- 🎄3. 選擇排序
- 🎄4.堆排序（如果不了解堆的話可以看看我上一篇講 堆 的博客）
- ?交換排序
- 🎄5. 冒泡排序
- 🎄6. 快速排序
- ?🎄7. 歸并排序·
- 🛸非基于比較的排序
- 🎄8. 基排序
- 🗽總結
🛸基本概念
?排序
- 排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，
遞增或遞減的排列起來的操作， - 平時的背景關系中，如果提到排序，通常指的是排升序（非降序），
- 通常意義上的排序，都是指的原地排序(in place sort)，
?穩定性
兩個相等的資料，如果經過排序后，排序演算法能 保證其相對位置不發生變化 ，則我們稱該演算法是具備 穩定性 的排序演算法，
🛸七大基于比較的排序
?插入排序
🎄1. 直接插入排序
思路：
- 插入排序基本思想是將一個記錄插入到已經排好序的有序表中，從而變成一個新的、記錄數增1的有序表，
- 在其實作程序使用雙層回圈，外層回圈對
除了第一個元素之外的所有元素，內層回圈對當前元素前面有序表進行待插入位置查找，并進行移動
圖解：
代碼實作：
/**
* 時間復雜度：
* 最好：O(N) -> 資料是有序的
*
* 最壞：O(N^2) -> 無序的資料
*
* 空間復雜度：O(1)
* 穩定性：穩定排序
* @param array
*/
//插入排序
public static void insertSort (int[]array){
for (int i = 1; i<array.length; i++){//外回圈
//從1開始表示：假設array[0] 已經放好位置了
//后面的數字就是插入到它左邊還是右邊的問題，
int tmp = array[i];//設定一個快取tmp
int j = i-1;
for (; j >=0 ; j--){//內回圈
if (array[j]>tmp){//如果array[j]大于快取值，說明要換位置
array[j+1] = array[j];
}else{//否則直接退出當前這一次的回圈
break;
}
}
//最后記得要把快取值插入到表中
array[j+1] = tmp;//j此時有可能已經是-1了，所以要變成0下標就得+1
}
}
🎄2. 希爾排序（直接插入排序的優化）
思路：
- 希爾排序法又稱縮小增量法，
- 希爾排序法的基本思想是：
先選定一個整數（gap），把待排序檔案中所有記錄分成gap個組，所有距離為gap的記錄分在同一組內，并對每一組內的記錄進行排序，然后，取gap / 2，重復上述分組和排序的作業，當gap到達1時，所有記錄在同一組內排好序， - 注意gap的問題：
- 希爾排序是對直接插入排序的優化，
- 當gap > 1時都是預排序，目的是讓陣列更接近于有序，
當gap == 1時，陣列已經接近有序的了，這時相當于直接用插入排序，這樣就會很快，因為直接插入排序是越有序越快，這樣整體而言，可以達到優化的效果，我們實作后可以進行性能測驗的對比，
圖解：
代碼實作：
/**
* @param array 排序的陣列
* @param gap 每組的間隔 -》 組數
*/
public static void shell(int[] array,int gap) {
//如果將gap全部換成1，會發現其實就是直接插入排序
//所以當gap到1的時候，這就表示這是最后一次排序
//這最后一次排序其實就是一個直接插入排序
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;
}
}
/**
* 時間復雜度：不好算 n^1.3 - n^1.5 之間
* 空間復雜度：O(1)
* 穩定性：不穩定的排序
* 技巧：如果在比較的程序當中 沒有發生跳躍式的交換 那么就是穩定的
* @param array
*/
public static void shellSort(int[] array) {
//處理gap
int gap = array.length;
while (gap > 1) {
gap /= 2;//保證最后一個序列間隔是 1 除幾都行
shell(array,gap);
}
}
?選擇排序
🎄3. 選擇排序
思路：
將一組資料分為有序區（排過序的資料）和無序區（未排序資料），每一次從無序區間選出最大（或最小）的一個元素，存放在無序區間的最后（或最前），直到全部待排序的資料元素排完 ，
選擇排序的步驟：
1>首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
2>再從剩余未排序元素中繼續尋找最小（大）元素，然后放到未排序序列的起始位置，
3>重復第二步，直到所有元素均排序完畢，
圖解：
代碼實作：
/**
* 時間復雜度：
* 最好：O(N^2)
* 最壞：O(N^2)
* 空間復雜度：O(1)
* 穩定性：不穩定的
* @param array
*/
public static void selectSort(int[] array) {
for (int i = 0; i < array.length; i++) {//下標i前邊的為有序區間
for (int j = i+1; j < array.length; j++) {
if(array[j] < array[i]) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
}
}
🎄4.堆排序（如果不了解堆的話可以看看我上一篇講 堆 的博客）
思路：
準備知識：
堆的結構可以分為大根堆和小根堆，是一個 完全二叉樹，而堆排序是根據堆的這種資料結構設計的一種排序，下面先來看看什么是大根堆和小根堆
性質：
每個結點的值都大于其左孩子和右孩子結點的值，稱之為大根堆；
每個結點的值都小于其左孩子和右孩子結點的值，稱之為小根堆，
如下圖
基本步驟：
- 首先將待排序的陣列構造成一個大根堆（升序用大根堆，降序就用小根堆），此時，
整個陣列的最大值就是堆結構的頂端 - 將頂端的數與末尾的數交換，此時，末尾的數為最大值，將末尾這個最大值提取出去，剩余待排序陣列個數為n-1
- 將剩余的n-1個數再構造成大根堆，再將頂端數與n-1位置的數交換，如此反復執行，便能得到有序陣列
圖解：
代碼實作：
//堆的向下調整
public static void siftDown(int[] array,int root,int len) {//len表示末尾元素下標
int parent = root;
int child = 2*parent+1;//先找到左孩子節點
while (child <= len) {//當child>length的時候說明當前子樹已經調整好了
//先根據左孩子節點判斷右孩子節點是否存在，且是否大于左孩子節點
if(child+1 <= len && array[child] < array[child+1]) {//如果存在,且值大于左孩子節點
child++;
}
//child的下標就是左右孩子的最大值下標
if(array[child] > array[parent]) {//如果孩子節點最大值，大于父節點，則要交換位置，因為要建大根堆
int tmp = array[child];
array[child] = array[parent];
array[parent] = tmp;
//繼續向下看是否符合大根堆的條件
parent = child;//更新parent下標
child = 2*parent+1;//更新child下標
}else {//否則不用換位置
break;
}
}
}
//建堆
public static void createHeap(int[] array) {
//從小到大排序 -》 大根堆
for (int i = (array.length-1 - 1) / 2; i >= 0 ; i--) {
siftDown(array,i,array.length-1);
}
}
/**
* 時間復雜度：O(N*logN) 都是這個時間復雜度
* 復雜度：O(1)
* 穩定性：不穩定的排序
* @param array
*/
public static void heapSort(int[] array) {
createHeap(array);//O(n)
int end = array.length-1;//end表示當前末尾元素的下標
while (end > 0) {//O(N*logN)
int tmp = array[end];//因為要交換末尾與堆頂元素，所以先快取末尾元素
//已經建好堆了，這時堆頂（0下標元素）就是當前的最大值
array[end] = array[0];//將他提取出來，放到陣列的末尾，固定住
array[0] = tmp;//將末尾元素換到堆頂
end--;//固定了一個當前堆中的最大值之后，下一次參與排序的元素就得減少一個
siftDown(array,0,end);//將剩余元素繼續變成一個大根堆
}
}
?交換排序
🎄5. 冒泡排序
思路：
- 比較
相鄰的兩個元素，如果第一個比第二個大則交換他們的位置(升序排列，降序則反過來)， - 從串列的開始一直到結尾，
依次對每一對相鄰元素都進行比較，這樣，值最大的元素就通過交換“冒泡”到了串列的結尾，完成第一輪“冒泡”， - 重復上一步，繼續從串列開頭依次對相鄰元素進行比較，已經“冒泡”出來的元素不用比較(一直比較到結尾也可以，已經“冒泡”到后面的元素即使比較也不需要交換，不比較可以減少步驟)，
- 繼續從串列開始進行比較，
每輪比較會有一個元素“冒泡”成功，每輪需要比較的元素個數會遞減，一直到只剩一個元素沒有“冒泡”時(沒有任何一對元素需要比較)，則串列排序完成，
- 演算法優化
如若在一輪排序中沒有發生位置的交換，那么說明資料已經有序，不用繼續進行后邊的排序了
圖解：
代碼實作：
/**
* 時間復雜度：
* 最好最壞都是O(n^2) 但是：如果優化了 ，有序的時候就是O(n)
* 空間復雜度：O(1)
* 穩定性：穩定的排序
* 冒泡 直接插入
* @param array
*/
public static void bubbleSort(int[] array) {
for (int i = 0 ;i < array.length-1; i++){//外回圈只用length-1趟
boolean flg = false;//記錄當前這一趟是否有換位子
for (int j = 0 ; j <array.length-1-i ; j++){//內回圈array.length-1-i趟
if (array[j] > array[j+1]){
int tmp = array[j];
array[j] = array[j+1];
array[j+1] = tmp;
flg = true;
}
}
if (flg==false) {//如果當前趟沒換位置，說明已經有序，不需要再排序了
break;
}
}
}
🎄6. 快速排序
思路：
快速排序使用 分治策略 來把一個序列（list）分為兩個子序列（sub-lists），步驟為：
- 從數列中挑出一個元素，稱為"
基準"（pivot），
①選擇邊上（左或者右）默認用這種方式
②隨機選擇
③幾數取中（例如三數取中）：array[left], array[mid], array[right] 大小是中間的為基準值 - 重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（相同的數可以到任一邊），在這個磁區結束之后，該基準就處于數列的
中間位置，這個稱為磁區（partition）操作， - 遞回地（recursively）把小于基準值元素的子數列和大于基準值元素的子數列排序，
遞回到最底部時，數列的大小是零或一，也就是已經排序好了，這個演算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去，
圖解：
代碼實作：
/**
* 時間復雜度：
* 最好：O(n*logn) 均勻的分割下
* 最壞：o(n^2) 資料有序的時候
* 空間復雜度：
* 最好：logn
* 最壞：O(n)
* 穩定性：不穩定的排序
*
* k*n*logn
* 2
* 1.2
* @param array
*/
public static void quickSort(int[] array) {
sort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
private static void sort(int[] array, int low, int high) {
int i = low;
int j = high;
if (array.length <= 1) {
return;
}
if (i >= j) {
return;
}
int pivot = array[i];
while (i < j) {
while (i < j && array[j] >= pivot){
j--;
}
array[i++] = array[j];
while (i < j && array[i] <= pivot){
i++;
}
array[j--] = array[i];
}
array[i] = pivot;//i下標值就是pivot基準值，由此可以遞回左右兩邊的序列
sort(a, low, i - 1);
sort(a, i + 1, high);
}
非遞回實作快速排序（重點掌握遞回實作）
/**
* 非遞回實作快速排序
* @param array
*/
public static void quickSort_FDG(int[] array) {
Stack<Integer> stack = new Stack<>();
int start = 0;
int end = array.length-1;
int pivot = partition(array,start,end);
//左邊有2個元素及以上
if(pivot > start+1) {
stack.push(0);
stack.push(pivot-1);
}
if(pivot < end-1) {
stack.push(pivot+1);
stack.push(end);
}
while (!stack.empty()) {
end = stack.pop();
start = stack.pop();
pivot = partition(array,start,end);
//左邊有2個元素及以上
if(pivot > start+1) {
stack.push(0);
stack.push(pivot-1);
}
if(pivot < end-1) {
stack.push(pivot+1);
stack.push(end);
}
}
}
?🎄7. 歸并排序·
思路：
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序演算法,該演算法是采用分治法（Divide andConquer）的一個非常典型的應用，將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，若將兩個有序表合并成一個有序表，稱為二路歸并，
圖解：
-
分而治之
可以看到這種結構很像一棵完全二叉樹，本文的歸并排序我們采用遞回去實作（也可采用迭代的方式去實作），“分” 階段可以理解為就是遞回拆分子序列的程序，遞回深度為log2n， -
合并相鄰有序子序列
再來看看 “治” 階段，我們需要將兩個已經有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實作步驟，
代碼實作：
public static void merge(int[] array,int low,int mid,int high) {
int s1 = low;
int e1 = mid;
int s2 = mid+1;
int e2 = high;
int[] tmp = new int[high-low+1];
int k = 0;//代表tmp陣列的下標
while (s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
//k++;
//s1++;
}else {
tmp[k++] = array[s2++];
}
}
//有2種情況
while (s1 <= e1){
//說明第2個歸并段沒有了資料 把第1個歸并段剩下的資料 全部拷貝過來
tmp[k++] = array[s1++];
}
while (s2 <= e2) {
//說明第1個歸并段沒有了資料 把第2個歸并段剩下的資料 全部拷貝過來
tmp[k++] = array[s2++];
}
//tmp陣列當中 存盤的就是當前歸并好的資料,現在還需要拷貝到原陣列中
//這樣的代碼是錯誤的
/*for (int i = 0; i < array.length; i++) {
array[i] = tmp[i];
}*/
for (int i = 0; i < tmp.length; i++) {
array[i+low] = tmp[i];//加上對應的low，用來處理第二個歸并段，如果是第一個歸并段，low=0
}
}
public static void mergeSortInternal(int[] array,int low,int high) {
if(low >= high) {
return;
}
int mid = (low+high) / 2;
mergeSortInternal(array,low,mid);//分解前半段
mergeSortInternal(array,mid+1,high);//分解后半段
//合并的程序
merge(array,low,mid,high);
}
/**
* 時間復雜度： O(N*log n)
* 空間復雜度：O(N)
* 穩定性：穩定的
* @param array
*/
public static void mergeSort(int[] array) {
mergeSortInternal(array, 0,array.length-1);
}
非遞回實作歸并排序（了解即可，重點掌握遞回實作）：
/**
* 非遞回實作 歸并排序
* @param array
* @param gap
*/
public static void merge2(int[] array,int gap) {
int[] tmp = new int[array.length];
int k = 0;
int s1 = 0;
int e1 = s1+gap-1;
int s2 = e1+1;
//int e2 = s2+gap-1 >= array.length ? array.length-1 : s2+gap-1;
int e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1;
//保證有兩個歸并段
while (s2 < array.length) {
while (s1 <= e1 && s2 <= e2) {
if(array[s1] <= array[s2]) {
tmp[k++] = array[s1++];
}else {
tmp[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmp[k++] = array[s1++];
}
while (s2 <= e2) {
tmp[k++] = array[s2++];
}
//一組完了 確定新的區間的開始和結束
s1 = e2+1;
e1 = s1+gap-1;
s2 = e1+1;
e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1;
}
//e2 > array.length
while (s1 <= array.length-1) {
tmp[k++] = array[s1++];
}
for (int i = 0; i < tmp.length; i++) {
array[i] = tmp[i];
}
}
public static void mergeSort_FDG(int[] array) {
for (int i = 1; i < array.length; i*=2) {
merge2(array,i);
}
}
🛸非基于比較的排序
🎄8. 基排序
思路：
- 基數排序的思想就是先排好
個位，然后排好個位的基礎上排十位，以此類推，直到遍歷最高位 次，排序結束（仔細理解最后一句話） - 基數排序不是比較排序，而是通過分配和收集的程序來實作排序
初始化10個桶(固定的)，桶下標為0-9- 通過得到待排序數字的個十百等位的數字，
把這個數字對應的item放到對應的桶中 - 基數排序有兩種排序方式：LSD和MSD，最小位優先(從右邊開始)和最大位優先(從左邊開始)
圖解：
代碼實作：
public static void radixSort(int[] array) {
ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
for (int i = 0; i <10 ; i++) {
queue.add(new ArrayList<>());// 創建一個基數從0---9 每個數字上都是一個list
}
// 找到最大值，并判斷最大值是幾位數
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (max < array[i]) {
max = array[i];
}
}
int time = 0;
while (max > 0) {
max /= 10;
time++;
}
for (int i = 0; i < time; i++) {// 回圈每一個位數（個位、十位、百位）
for (int j = 0; j < array.length; j++) {// 回圈陣列，取每一個值
int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
ArrayList<Integer> queue3 = queue.get(x);
queue3.add(array[j]);
queue.set(x, queue3);
}
int count = 0;
for (int k = 0; k < 10; k++) {
while (queue.get(k).size() > 0) {
ArrayList<Integer> queue4 = queue.get(k);
array[count] = queue4.get(0);
queue4.remove(0);
count++;
}
}
}
}
🗽總結
一個穩定的排序，可以變成不穩定的排序
但是一個不穩定的排序，不可能變成穩定的排序
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
?原創不易，如有錯誤，歡迎評論區留言指出，感激不盡?
? 如果覺得內容不錯，給個三連不過分吧~ ?
? 看到會回訪~ ?
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/397353.html
標籤：其他