Java數(shù)據(jù)結(jié)構(gòu)中七種排序算法實(shí)現(xiàn)詳解
實(shí)現(xiàn)冒泡排序
冒泡排序是一種簡(jiǎn)單的排序算法，它重復(fù)地遍歷要排序的列表，比較相鄰的元素，并交換它們直到列表排序完成。冒泡排序的時(shí)間復(fù)雜度為 O(n^2) ，在最壞的情況下需要進(jìn)行 n*(n-1)/2 次比較和交換操作。是一個(gè)穩(wěn)定排序。
具體步驟如下：
- 從列表的第一個(gè)元素開始，依次比較相鄰的兩個(gè)元素，如果它們的順序不正確，則交換它們的位置。
- 繼續(xù)比較相鄰的元素，直到達(dá)到列表的末尾。
- 重復(fù)以上步驟，直到列表排序完成。
冒泡排序的詳解過(guò)程：
冒泡排序的過(guò)程可以用一個(gè)簡(jiǎn)單的示意圖來(lái)說(shuō)明，假設(shè)我們要對(duì)一個(gè)包含5個(gè)元素的列表進(jìn)行冒泡排序：
初始狀態(tài)： [5, 3, 8, 2, 1]
第一輪冒泡：比較相鄰的元素并交換它們的位置，直到最大的元素被“冒泡”到列表的末尾。[3, 5, 2, 1, 8] ，[x, x, x, x, 8]所在的位置就是最終的位置，因此不需要再進(jìn)行交換了。
第二輪冒泡：同樣比較相鄰的元素并交換它們的位置，直到最大的元素被“冒泡”到列表的末尾。[3, 2, 1, 5, 8] ， [x, x, x, 5, 8]所在的位置就是最終的位置，因此不需要再進(jìn)行交換了。
第三輪冒泡：同理，[2, 1, 3, 5, 8] , [x, x, 3, 5, 8] 所在的位置就是最終的位置，因此不需要再進(jìn)行交換了。
第四輪冒泡：[1, 2, 3, 5, 8] 完成排序了，一共需要進(jìn)行（數(shù)組長(zhǎng)度 - 1 ）輪冒泡。
數(shù)組的順序?yàn)?[8，7，6，5，4，3，2，1] 來(lái)進(jìn)行冒泡排序的動(dòng)態(tài)演示過(guò)程：
代碼如下：
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1,10,7,4,8,3,2,6,9,5};
bubble(arr);
System.out.println(Arrays.toString(arr));
}
//冒泡排序
public static void bubble(int[] arr) {
for (int i = 0;i < arr.length-1; i++) {
for (int j = 0 ;j < arr.length-1-i;j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}實(shí)現(xiàn)選擇排序
選擇排序（Selection Sort）是一種簡(jiǎn)單直觀的排序算法。選擇排序的時(shí)間復(fù)雜度為 O(n^2) ，因?yàn)樵诿恳惠喼行枰M(jìn)行n次比較，找到最小元素。（默認(rèn)從小到大排序）
基本思想：每次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素，然后放到已排序序列的末尾。內(nèi)層循環(huán)代表的是：當(dāng)前這次循環(huán)中，需要找到剩余數(shù)組中最小的元素；外層循壞代表的是：需要進(jìn)行多少次內(nèi)層循環(huán)，才能將數(shù)組中的元素按從小到大排序完成。
舉例詳解選擇過(guò)程：
初識(shí)狀態(tài)：[3, 44, 5, 27, 2, 50, 48]
第一輪選擇過(guò)程：記錄未排好序的元素 3 ，然后從元素 3 的后一個(gè)元素 44 出發(fā)，尋找比 3 小的元素，如果找到了，則需要進(jìn)行交換；如果沒(méi)有找到，這說(shuō)明元素 3 就是當(dāng)前循環(huán)過(guò)程中最小的元素。當(dāng)前找到了比元素 3 小的元素 2 ，那么需要進(jìn)行交換。
第二輪選擇過(guò)程：因?yàn)樵?2 已經(jīng)排好序了，那么需要記錄從排好序元素的后一個(gè)元素 44 ，尋找的范圍是當(dāng)前記錄的元素的后一個(gè)元素開始出發(fā)直到數(shù)組最后一個(gè)元素。同樣，重復(fù)以上操作，如果找到了比 44 要小的元素，需要進(jìn)行記錄 minIndex = i ，內(nèi)層循環(huán)結(jié)束后，最小的元素下標(biāo)為 minIndex，交換 44 與下標(biāo)為 minIndex 的元素。
第三輪選擇過(guò)程也是一樣流程，這里就不多贅述了......
選擇過(guò)程的動(dòng)態(tài)圖演示過(guò)程：
代碼如下：
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr = {1,10,7,4,8,3,2,6,9,5};
select1(arr);
System.out.println(Arrays.toString(arr));
}
public static void select1(int[] arr) {
for (int i = 0;i < arr.length - 1;i++) {
int minIndex = i;
for (int j = i + 1;j < arr.length;j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (i != minIndex) {
swap(arr,i,minIndex);
}
}
}
public static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}選擇排序的改良升級(jí)
在選擇過(guò)程中，內(nèi)層循環(huán)每一次都是尋找最小的元素，這次改進(jìn)是在尋找最小元素的同時(shí)，又找最大的元素，定義兩個(gè) letf ,right 指針，一開始分別指向數(shù)組的左右兩邊。此時(shí)外層的循環(huán)條件：left < right 。一次內(nèi)層循環(huán)中找到了最小、最大元素，接著就分別于 left、right 下標(biāo)元素進(jìn)行交換，交換完之后，left++ ，right-- 。
一開始 minIndex、maxIndex 都是從 left 開始，從左到右進(jìn)行查找元素的。重點(diǎn)需要需要注意的是：假如最大的元素就是當(dāng)前的 left 下標(biāo)時(shí)，且minIndex 與 left 進(jìn)行交換后，會(huì)導(dǎo)致 maxIndex 找的元素下標(biāo)就會(huì)發(fā)生變化，所以在下標(biāo) minIndex 與 left 交換完之后，需要判斷 maxInde == left 是否發(fā)生，如果發(fā)生了，那么 maxIndex 需要重新賦值為 maxIndex = minIndex 。
代碼如下：
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr = {1,10,7,4,8,3,2,6,9,5};
select2(arr);
System.out.println(Arrays.toString(arr));
}
public static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void select2(int[] arr) {
int left = 0;
int right = arr.length-1;
while (left < right) {
int minIndex = left;
int maxIndex = left;
for (int i = left+1;i <= right; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
swap(arr,minIndex,left);
if (maxIndex == left) {
maxIndex = minIndex;
}
swap(arr,maxIndex,right);
left++;
right--;
}
}
}實(shí)現(xiàn)堆排序
堆排序（Heap Sort）是一種高效的排序算法，它利用了堆這種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)排序。堆是一種特殊的完全二叉樹，分為最大堆和最小堆兩種類型。在堆排序中，通常使用最大堆。堆排序的時(shí)間復(fù)雜度為 O(nlogn) ，并且是原地排序算法，不需要額外的存儲(chǔ)空間。
堆排序的基本思想：首先將待排序的數(shù)據(jù)構(gòu)建成一個(gè)最大堆，然后將堆頂元素（最大元素）與堆的最后一個(gè)元素交換，然后對(duì)剩余的元素重新調(diào)整為最大堆，重復(fù)這個(gè)過(guò)程直到整個(gè)序列有序。
兩個(gè)動(dòng)作：首先是將數(shù)組中的元素構(gòu)建成一個(gè)大頂堆的形式，接著從堆的最后一個(gè)元素與堆頂元素進(jìn)行交換，再對(duì)當(dāng)前的堆頂元素進(jìn)行下潛處理，循環(huán)該過(guò)程即可。
堆排序的動(dòng)態(tài)演示過(guò)程：（該過(guò)程演示的是降序的排序過(guò)程，那么相反，建立一個(gè)小頂堆）
代碼如下：
建立大頂堆的代碼：下潛、交換元素
class Heap {
int[] arr;
int size = 0;
public Heap(int[] arr) {
this.arr = arr;
this.size = arr.length;
buildBigHeap(arr,size);
heapSort(arr);
}
public void buildBigHeap(int[] arr,int size) {
for (int i = size / 2 - 1; i >= 0 ; i--) {
down(i,size);
}
}
private void down(int i,int size) {
int left = i * 2 + 1;
int right = left + 1;
int max = i;
if (left < size && arr[max] < arr[left]) {
max = left;
}
if (right < size && arr[max] < arr[right]) {
max = right;
}
if (max != i) {
swap(arr,max,i);
down(max,size);
}
}
private void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}堆排序的完整代碼：
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr = {1,10,7,4,8,3,2,6,9,5};
Heap heap = new Heap(arr);
System.out.println(Arrays.toString(arr));
}
}
class Heap {
int[] arr;
int size = 0;
public Heap(int[] arr) {
this.arr = arr;
this.size = arr.length;
buildBigHeap(arr,size);
heapSort(arr);
}
public void buildBigHeap(int[] arr,int size) {
for (int i = size / 2 - 1; i >= 0 ; i--) {
down(i,size);
}
}
private void down(int i,int size) {
int left = i * 2 + 1;
int right = left + 1;
int max = i;
if (left < size && arr[max] < arr[left]) {
max = left;
}
if (right < size && arr[max] < arr[right]) {
max = right;
}
if (max != i) {
swap(arr,max,i);
down(max,size);
}
}
private void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void heapSort(int[] arr) {
for (int i = arr.length - 1; i > 0 ; i--) {
swap(arr,i,0);
down(0,i);
}
}
}實(shí)現(xiàn)插入排序
插入排序是一種簡(jiǎn)單直觀的排序算法，它的工作原理是通過(guò)構(gòu)建有序序列，對(duì)未排序的數(shù)據(jù)逐個(gè)進(jìn)行插入，從而達(dá)到排序的目的。插入排序的時(shí)間復(fù)雜度為 O(n^2) ，在最壞情況下（逆序排列的數(shù)組），需要進(jìn)行 n*(n-1)/2 次比較和交換操作。插入排序適用于小規(guī)模數(shù)據(jù)或部分有序的數(shù)據(jù)。是一個(gè)穩(wěn)定排序。
具體來(lái)說(shuō)，插入排序的算法步驟如下：
1.從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序。
2.取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描。
3.如果該元素（已排序）大于新元素，將該元素移到下一位置。
4.重復(fù)步驟3，直到找到已排序的元素小于或等于新元素的位置。
5.將新元素插入到該位置后。
6.重復(fù)步驟2~5。
插入排序動(dòng)態(tài)圖演示過(guò)程：
代碼如下：
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr = {1,10,7,4,8,3,2,6,9,5};
insert(arr);
System.out.println(Arrays.toString(arr));
}
public static void insert(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while(j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
}實(shí)現(xiàn)希爾排序
希爾排序（Shell Sort）是一種改進(jìn)的插入排序算法，也被稱為“縮小增量排序”。它通過(guò)將數(shù)組分割成若干個(gè)子序列，對(duì)每個(gè)子序列進(jìn)行插入排序，最終進(jìn)行一次完整的插入排序得到有序序列。希爾排序的工作原理是通過(guò)逐步減小增量的方式，最終達(dá)到增量為1的插入排序。希爾排序的時(shí)間復(fù)雜度取決于增量序列的選擇，通常為 O(n logn) 。
希爾排序的算法步驟如下：
1. 選擇一個(gè)增量序列，通常為 n/2、n/4、n/8……直到增量為 1 。
2. 對(duì)每個(gè)增量進(jìn)行插入排序，即將數(shù)組分割成若干個(gè)子序列，對(duì)每個(gè)子序列進(jìn)行插入排序。
3. 逐步縮小增量，重復(fù)步驟 2 ，直到增量為 1 。
4. 最后進(jìn)行一次增量為 1 的插入排序，完成排序過(guò)程。
希爾排序的動(dòng)態(tài)演示過(guò)程：
代碼如下：
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] arr = {8,9,1,7,2,3,5,4,6,0};
shell(arr);
System.out.println(Arrays.toString(arr));
}
public static void shell(int[] arr) {
int size = arr.length;
for (int gap = size >> 1;gap >= 1; gap >>= 1) {
for (int i = gap; i < size;i++) {
int key = arr[i];
int j = i-gap;
while(j >= 0 && arr[j] > key) {
arr[j+gap] = arr[j];
j -= gap;
}
arr[j + gap] = key;
}
}
}
}實(shí)現(xiàn)歸并排序
歸并排序（Merge Sort）是一種經(jīng)典的分治算法，它的基本思想是將待排序的數(shù)組遞歸地分成兩個(gè)子數(shù)組，分別對(duì)兩個(gè)子數(shù)組進(jìn)行排序，然后將兩個(gè)已排序的子數(shù)組合并成一個(gè)有序的數(shù)組。歸并排序的過(guò)程可以描述為“分而治之”。
歸并排序是一種穩(wěn)定的排序算法，它的時(shí)間復(fù)雜度始終為 O(n log n) ，這使得它在處理大規(guī)模數(shù)據(jù)時(shí)具有較好的性能。然而，歸并排序的空間復(fù)雜度較高，因?yàn)樗枰~外的空間來(lái)存儲(chǔ)臨時(shí)數(shù)組。
遞歸實(shí)現(xiàn)歸并排序
歸并排序的算法步驟如下：
1. 分：將待排序的數(shù)組分成兩個(gè)子數(shù)組，直到子數(shù)組的長(zhǎng)度為1。
2. 治：對(duì)每個(gè)子數(shù)組進(jìn)行遞歸排序，直到子數(shù)組有序。
3. 合：將兩個(gè)有序的子數(shù)組合并成一個(gè)有序的數(shù)組。
使用遞歸實(shí)現(xiàn)歸并的動(dòng)態(tài)演示過(guò)程：
代碼如下：
import javax.print.DocFlavor;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.IllegalFormatCodePointException;
public class mergeSort {
public static void main(String[] args) {
int[] arr = {1,10,7,4,8,3,2,6,9,5};
int[] a = new int[arr.length];
//spilt(arr,0, arr.length - 1,a);
//merge(arr);
spiltInsert(arr,0,arr.length,a);
System.out.println(Arrays.toString(arr));
}
//使用遞歸實(shí)現(xiàn)歸并排序
public static void spilt(int[] arr,int left,int right, int[] a) {
if (left == right) {
return;
}
//分
int mid = (left + right) >>> 1;
spilt(arr,left,mid,a);
spilt(arr,mid+1,right,a);
//合
mergeArr(arr,left,mid,mid + 1,right,a);
System.arraycopy(a,left,arr,left,right - left + 1);
}
//非遞歸實(shí)現(xiàn)兩個(gè)有序數(shù)組合并
public static void mergeArr(int[] arr,int i,int iEnd,int j,int jEnd,int[] a) {
int k = i;
while(i <= iEnd && j <= jEnd) {
if (arr[i] < arr[j]) {
a[k] = arr[i];
i++;
}else {
a[k] = arr[j];
j++;
}
k++;
}
if (i > iEnd) {
System.arraycopy(arr,j,a,k,jEnd - j + 1);
}
if (j > jEnd) {
System.arraycopy(arr,i,a,k,iEnd - i + 1);
}
}
}使用非遞歸實(shí)現(xiàn)歸并排序
非遞歸歸并排序的關(guān)鍵是正確地計(jì)算子數(shù)組的大小并進(jìn)行合并操作，直到整個(gè)數(shù)組都被合并為一個(gè)有序序列。
以下是非遞歸歸并排序的主要步驟：
1. 從數(shù)組中的每個(gè)元素開始，將其視為一個(gè)大小為1的有序序列。
2. 通過(guò)迭代，將相鄰的有序序列合并為更大的有序序列，直到整個(gè)數(shù)組變?yōu)橐粋€(gè)有序序列。
3. 在每次迭代中，合并的子數(shù)組大小以指數(shù)級(jí)增加，直到整個(gè)數(shù)組都被合并為一個(gè)有序序列。
代碼如下：
//使用非遞歸實(shí)現(xiàn)歸并排序
public static void merge(int[] arr) {
int n = arr.length;;
int[] a = new int[n];
for (int width = 1;width < n ;width *= 2) {
//[left,right] 分別代表帶合并區(qū)間的左右邊界
for (int left = 0;left < n; left = left + 2 * width) {
int right = Math.min(left + 2 * width - 1,n - 1);
int m = Math.min(left + width - 1,n - 1);
mergeArr(arr,left,m,m+1,right,a);
}
System.arraycopy(a,0,arr,0,n);
}
}
//非遞歸實(shí)現(xiàn)兩個(gè)有序數(shù)組合并
public static void mergeArr(int[] arr,int i,int iEnd,int j,int jEnd,int[] a) {
int k = i;
while(i <= iEnd && j <= jEnd) {
if (arr[i] < arr[j]) {
a[k] = arr[i];
i++;
}else {
a[k] = arr[j];
j++;
}
k++;
}
if (i > iEnd) {
System.arraycopy(arr,j,a,k,jEnd - j + 1);
}
if (j > jEnd) {
System.arraycopy(arr,i,a,k,iEnd - i + 1);
}
}遞歸歸并排序與插入排序
即集合了遞歸排序的優(yōu)點(diǎn)與插入排序的優(yōu)點(diǎn)實(shí)現(xiàn)更加高效排序。
代碼如下：
//遞歸歸并 + 插入排序
public static void spiltInsert(int[] arr,int left,int right,int[] a) {
if (right - left <= 32) {
insert(arr,left,right);
return;
}
int m = (left + right) >>> 1;
spiltInsert(arr,left,m,a);
spiltInsert(arr,m+1,right,a);
mergeArr(arr,left,m,m+1,right,a);
System.arraycopy(a,left,arr,left,right-left+1);
}
//插入排序
public static void insert(int[] arr,int left, int right) {
for (int i = left + 1; i < right; i++) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}快速排序
快速排序是一種常用的排序算法，它基于分治的思想?？焖倥判虻幕舅枷胧沁x擇一個(gè)基準(zhǔn)值，然后將數(shù)組分割成兩部分，使得左邊的元素都小于基準(zhǔn)值，右邊的元素都大于基準(zhǔn)值。然后對(duì)左右兩部分分別進(jìn)行遞歸排序，直到整個(gè)數(shù)組有序。
以下是快速排序的主要步驟：
1.選擇一個(gè)基準(zhǔn)值（通常是數(shù)組中的第一個(gè)元素）。
2.將數(shù)組分割成兩部分，使得左邊的元素都小于基準(zhǔn)值，右邊的元素都大于基準(zhǔn)值。這一步稱為分區(qū)操作。
3. 遞歸地對(duì)左右兩部分進(jìn)行快速排序。
4. 當(dāng)左右兩部分都有序時(shí)，整個(gè)數(shù)組也就有序了。
單邊循環(huán)快排
單邊循環(huán)快排的時(shí)間復(fù)雜度為 O(n logn)，空間復(fù)雜度為 O(logn)。單邊循環(huán)快排（也稱為荷蘭國(guó)旗問(wèn)題解法）是快速排序算法的一種實(shí)現(xiàn)方式，它通過(guò)使用單個(gè)指針在數(shù)組中進(jìn)行循環(huán)遍歷，實(shí)現(xiàn)數(shù)組的分區(qū)和排序。
代碼如下：
//單邊循環(huán)快排要點(diǎn):
//選擇最右側(cè)元素作為基準(zhǔn)點(diǎn)
//j 找比基準(zhǔn)點(diǎn)小的，i 找基準(zhǔn)點(diǎn)大的，一旦找到，二者進(jìn)行交換:
// 交換時(shí)機(jī): j 找到小的，且與 i 不相等
// i 找到 >= 基準(zhǔn)點(diǎn)元素后，不應(yīng)自增
// 最后基準(zhǔn)點(diǎn)與 i 交換， i 即為基準(zhǔn)點(diǎn)最終索引
public static void quickSort(int[] arr) {
recursion(arr,0,arr.length-1);
}
private static void recursion(int[] arr,int left,int right) {
if (left >= right) {
return;
}
//先找到基準(zhǔn)點(diǎn)
int m = benchmark(arr,left,right);
//切分基準(zhǔn)點(diǎn)兩側(cè)
recursion(arr, left, m - 1);
recursion(arr, m + 1, right);
}
private static int benchmark(int[] arr,int left,int right) {
int temp = arr[right];
//i 找最大值、 j 找最小值，一旦 j 找到最小值且 j != i 就可以交換了
int i = left;
int j = left;
while (j < right) {
if (arr[j] < temp) {
if (i != j) {
//交換
swap(arr,i,j);
}
i++;
}
j++;
}
swap(arr,i,right);
return i;
}
private static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}雙邊循環(huán)快排
雙邊循環(huán)快排是一種快速排序算法的實(shí)現(xiàn)方式，它通過(guò)不斷地將數(shù)組分割成兩部分并對(duì)每一部分進(jìn)行遞歸排序來(lái)實(shí)現(xiàn)排序。與單邊循環(huán)快排相比，雙邊循環(huán)快排在分割數(shù)組時(shí)使用兩個(gè)指針?lè)謩e從數(shù)組的兩端向中間移動(dòng)，以實(shí)現(xiàn)更高效的分割操作。
雙邊循環(huán)快排的時(shí)間復(fù)雜度為 O(nlogn)，空間復(fù)雜度為 O(logn)。它是一種高效的排序算法，在大多數(shù)情況下都能夠快速地對(duì)數(shù)組進(jìn)行排序。
具體實(shí)現(xiàn)過(guò)程如下：
1. 選擇數(shù)組中的一個(gè)元素作為基準(zhǔn)值（通常選擇第一個(gè)元素）。
2. 設(shè)置兩個(gè)指針，一個(gè)指向數(shù)組的起始位置，另一個(gè)指向數(shù)組的末尾位置。
3. 從起始位置開始，找到第一個(gè)大于基準(zhǔn)值的元素，并將其位置記錄下來(lái)。
4. 從末尾位置開始，找到第一個(gè)小于基準(zhǔn)值的元素，并將其位置記錄下來(lái)。
5. 交換這兩個(gè)元素的位置，然后繼續(xù)尋找下一個(gè)需要交換的元素，直到兩個(gè)指針相遇。
6. 將基準(zhǔn)值與指針相遇的位置的元素交換位置，這樣基準(zhǔn)值左邊的元素都小于基準(zhǔn)值，右邊的元素都大于基準(zhǔn)值。
7. 對(duì)基準(zhǔn)值左右兩個(gè)子數(shù)組分別進(jìn)行遞歸排序。
代碼如下：
//雙邊循環(huán)快排要點(diǎn):
//選擇最左側(cè)元素作為基準(zhǔn)點(diǎn)
//j 找比基準(zhǔn)點(diǎn)小的, i 找比基準(zhǔn)點(diǎn)大的，一旦找到，二者進(jìn)行交換
// i 從左向右
// j 從右先左
// 最后基準(zhǔn)點(diǎn)與 i 交換， i 即為基準(zhǔn)點(diǎn)最終索引
public static void quickSort1(int[] arr) {
recursion1(arr,0,arr.length-1);
}
private static void recursion1(int[] arr,int left,int right) {
if (left >= right) {
return;
}
int m = benchmark1(arr,left,right);
recursion1(arr,left,m - 1);
recursion1(arr,m + 1,right);
}
private static int benchmark1(int[] arr,int left,int right) {
int temp = arr[left];
int i = left;
int j = right;
while (i < j) {
while (i < j && temp < arr[j]) {
j--;
}
while (i < j && temp >= arr[i]) {
i++;
}
swap(arr,i,j);
}
swap(arr,left,i);
return i;
}
private static void swap(int[] arr,int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}快速排序的改良升級(jí)
考慮快排時(shí)，遇到的重復(fù)元素過(guò)多而進(jìn)行改良。
代碼如下：
public static void quickSort1(int[] arr) {
recursion1(arr,0,arr.length-1);
}
private static void recursion1(int[] arr,int left,int right) {
if (left >= right) {
return;
}
int m = benchmark2(arr,left,right);
recursion1(arr,left,m - 1);
recursion1(arr,m + 1,right);
}
//考慮快排時(shí)，遇到的重復(fù)元素過(guò)多而進(jìn)行改良
private static int benchmark2(int[] arr,int left,int right) {
int temp = arr[left];
int i = left + 1;
int j = right;
while(i <= j) {
while(i <= j && arr[i] < temp) {
i++;
}
while (i <= j && arr[j] > temp ) {
j--;
}
if (i <= j) {
swap(arr,i,j);
i++;
j--;
}
}
swap(arr,left,j);
return j;
}到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)中七種排序算法實(shí)現(xiàn)詳解的文章就介紹到這了,更多相關(guān)Java排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java數(shù)據(jù)結(jié)構(gòu)之紅黑樹的實(shí)現(xiàn)方法和原理詳解
- Java數(shù)據(jù)結(jié)構(gòu)中關(guān)于AVL樹的實(shí)現(xiàn)方法詳解
- Java數(shù)據(jù)結(jié)構(gòu)和算法之鏈表詳解
- Java數(shù)據(jù)結(jié)構(gòu)篇之實(shí)現(xiàn)二叉搜索樹的核心方法
- Java數(shù)據(jù)結(jié)構(gòu)與算法之二分查找詳解
- Java數(shù)據(jù)結(jié)構(gòu)中的HashMap和HashSet詳解
- Java常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列詳解
- java手動(dòng)實(shí)現(xiàn)常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的示例代碼
相關(guān)文章
IDEA創(chuàng)建springboot + mybatis項(xiàng)目全過(guò)程(步驟詳解)
這篇文章主要介紹了IDEA創(chuàng)建springboot + mybatis項(xiàng)目全過(guò)程及步驟詳解，本文通圖文實(shí)例代碼相結(jié)合給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-07-07
本文介紹了Spring框架中的BeanScope（作用域）,包括Singleton（單例）和Prototype（原型）兩種常見(jiàn)作用域的定義、生命周期和適用場(chǎng)景2025-01-01
Java 實(shí)戰(zhàn)項(xiàng)目錘煉之IT設(shè)備固定資產(chǎn)管理系統(tǒng)的實(shí)現(xiàn)流程
讀萬(wàn)卷書不如行萬(wàn)里路，只學(xué)書上的理論是遠(yuǎn)遠(yuǎn)不夠的，只有在實(shí)戰(zhàn)中才能獲得能力的提升，本篇文章手把手帶你用Java+SSM+jsp+mysql+maven實(shí)現(xiàn)一個(gè)IT設(shè)備固定資產(chǎn)管理系統(tǒng),大家可以在過(guò)程中查缺補(bǔ)漏，提升水平2021-11-11
SpringBoot使用Quartz無(wú)法注入Bean的問(wèn)題及解決
這篇文章主要介紹了SpringBoot使用Quartz無(wú)法注入Bean的問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-11-11
SpringBoot實(shí)現(xiàn)多數(shù)據(jù)源的實(shí)戰(zhàn)案例
這篇文章主要介紹了SpringBoot實(shí)現(xiàn)多數(shù)據(jù)源的實(shí)戰(zhàn)案例,文中通過(guò)示例代碼和圖文展示介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2024-01-01
IntelliJ?IDEA運(yùn)行SpringBoot項(xiàng)目的詳細(xì)步驟
這篇文章主要介紹了IntelliJ?IDEA如何運(yùn)行SpringBoot項(xiàng)目,步驟一配置maven，步驟二配置JDK環(huán)境，緊接著通過(guò)步驟三檢查數(shù)據(jù)庫(kù)的配置，最后一步數(shù)據(jù)庫(kù)連接，本文給大家介紹的非常詳細(xì)，需要的朋友可以參考下2022-08-08
datax-web在windows環(huán)境idea中模塊化打包部署操作步驟
這篇文章主要介紹了datax-web在windows環(huán)境idea中模塊化打包部署操作步驟,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-05-05
spring boot加載資源路徑配置和classpath問(wèn)題解決
這篇文章主要介紹了spring boot加載資源路徑配置和classpath問(wèn)題解決，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-03-03
詳解SpringBoot 快速整合MyBatis（去XML化）
本篇文章主要介紹了詳解SpringBoot 快速整合MyBatis（去XML化），非常具有實(shí)用價(jià)值，需要的朋友可以參考下2017-10-10
詳細(xì)分析java并發(fā)之volatile關(guān)鍵字
這篇文章主要介紹了java并發(fā)之volatile關(guān)鍵字的的相關(guān)資料，文中代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-06-06