1T數據快速排序！十種經典排序演算法總結
- 2020 年 10 月 15 日
- 筆記
- JDK, spring, springboot
1 冒泡排序
每次循環都比較前後兩個元素的大小，如果前者大於後者，則將兩者進行交換。這樣做會將每次循環中最大的元素替換到末尾，逐漸形成有序集合。將每次循環中的最大元素逐漸由隊首轉移到隊尾的過程形似「冒泡」過程，故因此得名。
一個優化冒泡排序的方法就是如果在一次循環的過程中沒有發生交換，則可以立即退出當前循環，因為此時已經排好序了（也就是時間複雜度最好情況下是
的由來）。
public int[] bubbleSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
for (int i = 0; i < array.length - 1; i++) {
boolean flag = false;
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
//這裡交換兩個數據並沒有使用中間變數，而是使用異或的方式來實現
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
flag = true;
}
}
if (!flag) {
break;
}
}
return array;
}
2 選擇排序
每次循環都會找出當前循環中最小的元素，然後和此次循環中的隊首元素進行交換。
public int[] selectSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
if (minIndex > i) {
array[i] = array[i] ^ array[minIndex];
array[minIndex] = array[i] ^ array[minIndex];
array[i] = array[i] ^ array[minIndex];
}
}
return array;
}
3 插入排序
插入排序的精髓在於每次都會在先前排好序的子集合中插入下一個待排序的元素，每次都會判斷待排序元素的上一個元素是否大於待排序元素，如果大於，則將元素右移，然後判斷再上一個元素與待排序元素…以此類推。直到小於等於比較元素時就是找到了該元素的插入位置。這裡的等於條件放在哪裡很重要，因為它是決定插入排序穩定與否的關鍵。
public int[] insertSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
for (int i = 1; i < array.length; i++) {
int temp = array[i];
int j = i - 1;
while (j >= 0 && array[j] > temp) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = temp;
}
return array;
}
4 希爾排序
希爾排序可以認為是插入排序的改進版本。首先按照初始增量來將數組分成多個組，每個組內部使用插入排序。然後縮小增量來重新分組，組內再次使用插入排序…重複以上步驟，直到增量變為1的時候，這個時候整個數組就是一個分組，進行最後一次完整的插入排序即可結束。
在排序開始時的增量較大，分組也會較多，但是每個分組中的數據較少，所以插入排序會很快。隨著每一輪排序的進行，增量和分組數會逐漸變小，每個分組中的數據會逐漸變多。但因為之前已經經過了多輪的分組排序，而此時的數組會趨近於一個有序的狀態，所以這個時候的排序也是很快的。而對於數據較多且趨向於無序的數據來說，如果只是使用插入排序的話效率就並不高。所以總體來說，希爾排序的執行效率是要比插入排序高的。
希爾排序執行示意圖：
具體的實現程式碼如下：
public int[] shellSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
int gap = array.length >>> 1;
while (gap > 0) {
for (int i = gap; i < array.length; i++) {
int temp = array[i];
int j = i - gap;
while (j >= 0 && array[j] > temp) {
array[j + gap] = array[j];
j = j - gap;
}
array[j + gap] = temp;
}
gap >>>= 1;
}
return array;
}
5 堆排序
堆排序的過程是首先構建一個大頂堆，大頂堆首先是一棵完全二叉樹，其次它保證堆中某個節點的值總是不大於其父節點的值。
因為大頂堆中的最大元素肯定是根節點，所以每次取出根節點即為當前大頂堆中的最大元素，取出後剩下的節點再重新構建大頂堆，再取出根節點，再重新構建…重複這個過程，直到數據都被取出，最後取出的結果即為排好序的結果。
public class MaxHeap {
/**
* 排序數組
*/
private int[] nodeArray;
/**
* 數組的真實大小
*/
private int size;
private int parent(int index) {
return (index - 1) >>> 1;
}
private int leftChild(int index) {
return (index << 1) + 1;
}
private int rightChild(int index) {
return (index << 1) + 2;
}
private void swap(int i, int j) {
nodeArray[i] = nodeArray[i] ^ nodeArray[j];
nodeArray[j] = nodeArray[i] ^ nodeArray[j];
nodeArray[i] = nodeArray[i] ^ nodeArray[j];
}
private void siftUp(int index) {
//如果index處節點的值大於其父節點的值，則交換兩個節點值，同時將index指向其父節點，繼續向上循環判斷
while (index > 0 && nodeArray[index] > nodeArray[parent(index)]) {
swap(index, parent(index));
index = parent(index);
}
}
private void siftDown(int index) {
//左孩子的索引比size小，意味著索引index處的節點有左孩子，證明此時index節點不是葉子節點
while (leftChild(index) < size) {
//maxIndex記錄的是index節點左右孩子中最大值的索引
int maxIndex = leftChild(index);
//右孩子的索引小於size意味著index節點含有右孩子
if (rightChild(index) < size && nodeArray[rightChild(index)] > nodeArray[maxIndex]) {
maxIndex = rightChild(index);
}
//如果index節點值比左右孩子值都大，則終止循環
if (nodeArray[index] >= nodeArray[maxIndex]) {
break;
}
//否則進行交換，將index指向其交換的左孩子或右孩子，繼續向下循環，直到葉子節點
swap(index, maxIndex);
index = maxIndex;
}
}
private void add(int value) {
nodeArray[size] = value;
size++;
//構建大頂堆
siftUp(size - 1);
}
private void extractMax() {
//將堆頂元素和最後一個元素進行交換
swap(0, size - 1);
//此時並沒有刪除元素，而只是將size-1，剩下的元素重新構建成大頂堆
size--;
//重新構建大頂堆
siftDown(0);
}
public int[] heapSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
nodeArray = new int[array.length];
for (int value : array) {
add(value);
}
for (int i = 0; i < array.length; i++) {
extractMax();
}
return nodeArray;
}
}
上面的經典實現中，如果需要變動節點時，都會來一次父子節點的互相交換操作（包括刪除節點時首先做的要刪除節點和最後一個節點之間的交換操作也是如此）。如果仔細思考的話，就會發現這其實是多餘的。在需要交換節點的時候，只需要siftUp操作時的父節點或siftDown時的孩子節點重新移到當前需要比較的節點位置上，而比較節點是不需要移動到它們的位置上的。此時直接進入到下一次的判斷中，重複siftUp或siftDown過程，直到最後找到了比較節點的插入位置後，才會將其插入進去。這樣做的好處是可以省去一半的節點賦值的操作，提高了執行的效率。同時這也就意味著，需要將要比較的節點作為參數保存起來，而在ScheduledThreadPoolExecutor源碼中也正是這麼實現的（《較真兒學源碼系列-ScheduledThreadPoolExecutor（逐行源碼帶你分析作者思路）》）。
6 歸併排序
歸併排序使用的是分治的思想，首先將數組不斷拆分，直到最後拆分成兩個元素的子數組，將這兩個元素進行排序合併，再向上遞歸。不斷重複這個拆分和合併的遞歸過程，最後得到的就是排好序的結果。
合併的過程是將兩個指針指向兩個子數組的首位元素，兩個元素進行比較，較小的插入到一個temp數組中，同時將該數組的指針右移一位，繼續比較該數組的第二個元素和另一個元素…重複這個過程。這樣temp數組保存的便是這兩個子數組排好序的結果。最後將temp數組複製回原數組的位置處即可。
public int[] mergeSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
return mergeSort(array, 0, array.length - 1);
}
private int[] mergeSort(int[] array, int left, int right) {
if (left < right) {
//這裡沒有選擇「(left + right) / 2」的方式，是為了防止數據溢出
int mid = left + ((right - left) >>> 1);
// 拆分子數組
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
// 對子數組進行合併
merge(array, left, mid, right);
}
return array;
}
private void merge(int[] array, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
// p1和p2為需要對比的兩個數組的指針，k為存放temp數組的指針
int p1 = left, p2 = mid + 1, k = 0;
while (p1 <= mid && p2 <= right) {
if (array[p1] <= array[p2]) {
temp[k++] = array[p1++];
} else {
temp[k++] = array[p2++];
}
}
// 把剩餘的數組直接放到temp數組中
while (p1 <= mid) {
temp[k++] = array[p1++];
}
while (p2 <= right) {
temp[k++] = array[p2++];
}
// 複製回原數組
for (int i = 0; i < temp.length; i++) {
array[i + left] = temp[i];
}
}
7 快速排序
快速排序的核心是要有一個基準數據temp，一般取數組的第一個位置元素。然後需要有兩個指針left和right，分別指向數組的第一個和最後一個元素。
首先從right開始，比較right位置元素和基準數據。如果大於等於，則將right指針左移，比較下一位元素；如果小於，就將right指針處數據賦給left指針處（此時left指針處數據已保存進temp中），left指針+1，之後開始比較left指針處數據。
拿left位置元素和基準數據進行比較。如果小於等於，則將left指針右移，比較下一位元素；而如果大於就將left指針處數據賦給right指針處，right指針-1，之後開始比較right指針處數據…重複這個過程。
直到left和right指針相等時，說明這一次比較過程完成。此時將先前存放進temp中的基準數據賦值給當前left和right指針共同指向的位置處，即可完成這一次排序操作。
之後遞歸排序基礎數據的左半部分和右半部分，遞歸的過程和上面講述的過程是一樣的，只不過數組範圍不再是原來的全部數組了，而是現在的左半部分或右半部分。當全部的遞歸過程結束後，最終結果即為排好序的結果。
快速排序執行示意圖：
正如上面所說的，一般取第一個元素作為基準數據，但如果當前數據為從大到小排列好的數據，而現在要按從小到大的順序排列，則數據分攤不均勻，時間複雜度會退化為
，而不是正常情況下的
。此時採取一個優化手段，即取最左邊、最右邊和最中間的三個元素的中間值作為基準數據，以此來避免時間複雜度為的情況出現，當然也可以選擇更多的錨點或者隨機選擇的方式來進行選取。
還有一個優化的方法是：像快速排序、歸併排序這樣的複雜排序方法在數據量大的情況下是比選擇排序、冒泡排序和插入排序的效率要高的，但是在數據量小的情況下反而要更慢。所以我們可以選定一個閾值，這裡選擇為47（和源碼中使用的一樣）。當需要排序的數據量小於47時走插入排序，大於47則走快速排序。
private static final int THRESHOLD = 47;
public int[] quickSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
return quickSort(array, 0, array.length - 1);
}
private int[] quickSort(int[] array, int start, int end) {
// 如果當前需要排序的數據量小於等於THRESHOLD則走插入排序的邏輯，否則繼續走快速排序
if (end - start <= THRESHOLD - 1) {
return insertSort(array);
}
// left和right指針分別指向array的第一個和最後一個元素
int left = start, right = end;
/*
取最左邊、最右邊和最中間的三個元素的中間值作為基準數據，以此來盡量避免每次都取第一個值作為基準數據、
時間複雜度可能退化為O(n^2)的情況出現
*/
int middleOf3Indexs = middleOf3Indexs(array, start, end);
if (middleOf3Indexs != start) {
swap(array, middleOf3Indexs, start);
}
// temp存放的是array中需要比較的基準數據
int temp = array[start];
while (left < right) {
// 首先從right指針開始比較，如果right指針位置處數據大於temp，則將right指針左移
while (left < right && array[right] >= temp) {
right--;
}
// 如果找到一個right指針位置處數據小於temp，則將right指針處數據賦給left指針處
if (left < right) {
array[left] = array[right];
left++;
}
// 然後從left指針開始比較，如果left指針位置處數據小於temp，則將left指針右移
while (left < right && array[left] <= temp) {
left++;
}
// 如果找到一個left指針位置處數據大於temp，則將left指針處數據賦給right指針處
if (left < right) {
array[right] = array[left];
right--;
}
}
// 當left和right指針相等時，此時循環跳出，將之前存放的基準數據賦給當前兩個指針共同指向的數據處
array[left] = temp;
// 一次替換後，遞歸交換基準數據左邊的數據
if (start < left - 1) {
array = quickSort(array, start, left - 1);
}
// 之後遞歸交換基準數據右邊的數據
if (right + 1 < end) {
array = quickSort(array, right + 1, end);
}
return array;
}
private int middleOf3Indexs(int[] array, int start, int end) {
int mid = start + ((end - start) >>> 1);
if (array[start] < array[mid]) {
if (array[mid] < array[end]) {
return mid;
} else {
return array[start] < array[end] ? end : start;
}
} else {
if (array[mid] > array[end]) {
return mid;
} else {
return array[start] < array[end] ? start : end;
}
}
}
private void swap(int[] array, int i, int j) {
array[i] = array[i] ^ array[j];
array[j] = array[i] ^ array[j];
array[i] = array[i] ^ array[j];
}
8 計數排序
以上的七種排序演算法都是比較排序，也就是基於元素之間的比較來進行排序的。而下面將要介紹的三種排序演算法是非比較排序，首先是計數排序。
計數排序會創建一個臨時的數組，裡面存放每個數出現的次數。比如一個待排序的數組是[3, 3, 5, 2, 7, 4, 2]，那麼這個臨時數組中記錄的數據就是[2, 2, 1, 1, 0, 1]。表示2出現了兩次、3出現了兩次、4出現了一次、5出現了一次、6出現了零次、7出現了一次。那麼最後只需要遍歷這個臨時數組中的計數值就可以了。
public int[] countingSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
//記錄待排序數組中的最大值
int max = array[0];
//記錄待排序數組中的最小值
int min = array[0];
for (int i : array) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
int[] temp = new int[max - min + 1];
//記錄每個數出現的次數
for (int i : array) {
temp[i - min]++;
}
int index = 0;
for (int i = 0; i < temp.length; i++) {
//當輸出一個數之後，當前位置的計數就減一，直到減到0為止
while (temp[i]-- > 0) {
array[index++] = i + min;
}
}
return array;
}
從上面的實現中可以看到，計數排序僅適合數據跨度不大的場景。如果最大值和最小值之間的差距比較大，生成的臨時數組就會比較長。比如說一個數組是[2, 1, 3, 1000]，最小值是1，最大值是1000。那麼就會生成一個長度為1000的臨時數組，但是其中絕大部分的空間都是沒有用的，所以這就會導致空間複雜度變得很高。
計數排序是穩定的排序演算法，但在上面的實現中並沒有體現出這一點，上面的實現沒有維護相同元素之間的先後順序。所以需要做些變換：將臨時數組中從第二個元素開始，每個元素都加上前一個元素的值。還是拿之前的[3, 3, 5, 2, 7, 4, 2]數組來舉例。計完數後的臨時數組為[2, 2, 1, 1, 0, 1]，此時做上面的變換，每個數都累加前面的一個數，結果為[2, 4, 5, 6, 6, 7]。這個時候臨時數組的含義就不再是每個數出現的次數了，此時記錄的是每個數在最後排好序的數組中應該要存放的位置+1（如果有重複的就記錄最後一個）。對於上面的待排序數組來說，最後排好序的數組應該為[2, 2, 3, 3, 4, 5, 7]。也就是說，此時各個數最後一次出現的索引位為：1, 3, 4, 5, 6，分別都+1後就是2, 4, 5, 6, 7，這不就是上面做過變換之後的數組嗎？（沒有出現過的數字不管它）所以，此時從後往前遍歷原數組中的每一個值，將其減去最小值後，找到其在變換後的臨時數組中的索引，也就是找到了最後排好序的數組中的位置了。當然，每次找到臨時數組中的索引後，這個位置的數需要-1。這樣如果後續有重複的該數字的話，就會插入到當前位置的前一個位置了。由此也說明了遍歷必須是從後往前遍歷，以此來維護相同數字之間的先後順序。
public int[] stableCountingSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
//記錄待排序數組中的最大值
int max = array[0];
//記錄待排序數組中的最小值
int min = array[0];
for (int i : array) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
int[] temp = new int[max - min + 1];
//記錄每個數出現的次數
for (int i : array) {
temp[i - min]++;
}
//將temp數組進行轉換，記錄每個數在最後排好序的數組中應該要存放的位置+1（如果有重複的就記錄最後一個）
for (int j = 1; j < temp.length; j++) {
temp[j] += temp[j - 1];
}
int[] sortedArray = new int[array.length];
//這裡必須是從後往前遍歷，以此來保證穩定性
for (int i = array.length - 1; i >= 0; i--) {
sortedArray[temp[array[i] - min] - 1] = array[i];
temp[array[i] - min]--;
}
return sortedArray;
}
9 桶排序
上面的計數排序在數組最大值和最小值之間的差值是多少，就會生成一個多大的臨時數組，也就是生成了一個這麼多的桶，而每個桶中就只插入一個數據。如果差值比較大的話，會比較浪費空間。那麼我能不能在一個桶中插入多個數據呢？當然可以，而這就是桶排序的思路。桶排序類似於哈希表，通過一定的映射規則將數組中的元素映射到不同的桶中，每個桶內進行內部排序，最後將每個桶按順序輸出就行了。桶排序執行的高效與否和是否是穩定的取決於哈希散列的演算法以及內部排序的結果。需要注意的是，這個映射演算法並不是常規的映射演算法，要求是每個桶中的所有數都要比前一個桶中的所有數都要大。這樣最後輸出的才是一個排好序的結果。比如說第一個桶中存1-30的數字，第二個桶中存31-60的數字，第三個桶中存61-90的數字…以此類推。下面給出一種實現：
public int[] bucketSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
//記錄待排序數組中的最大值
int max = array[0];
//記錄待排序數組中的最小值
int min = array[0];
for (int i : array) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
//計算桶的數量（可以自定義實現）
int bucketNumber = (max - min) / array.length + 1;
List<Integer>[] buckets = new ArrayList[bucketNumber];
//計算每個桶存數的範圍（可以自定義實現或者不用實現）
int bucketRange = (max - min + 1) / bucketNumber;
for (int value : array) {
//計算應該放到哪個桶中（可以自定義實現）
int bucketIndex = (value - min) / (bucketRange + 1);
//延遲初始化
if (buckets[bucketIndex] == null) {
buckets[bucketIndex] = new ArrayList<>();
}
//放入指定的桶
buckets[bucketIndex].add(value);
}
int index = 0;
for (List<Integer> bucket : buckets) {
//對每個桶進行內部排序，我這裡使用的是快速排序，也可以使用別的排序演算法，當然也可以繼續遞歸去做桶排序
quickSort(bucket);
if (bucket == null) {
continue;
}
//將不為null的桶中的數據按順序寫回到array數組中
for (Integer integer : bucket) {
array[index++] = integer;
}
}
return array;
}
10 基數排序
基數排序不是根據一個數的整體來進行排序的，而是將數的每一位上的數字進行排序。比如說第一輪排序，我拿到待排序數組中所有數個位上的數字來進行排序；第二輪排序我拿到待排序數組中所有數十位上的數字來進行排序；第三輪排序我拿到待排序數組中所有數百位上的數字來進行排序…以此類推。每一輪的排序都會累加上一輪所有前幾位上排序的結果，最終的結果就會是一個有序的數列。
基數排序一般是對所有非負整數進行排序的，但是也可以有別的手段來去掉這種限制（比如都加一個固定的數或者都乘一個固定的數，排完序後再恢復等等）。基數排序和桶排序很像，桶排序是按數值的區間進行劃分，而基數排序是按數的位數進行劃分。同時這兩個排序都是需要依靠其他排序演算法來實現的（如果不算遞歸調用桶排序本身的話）。基數排序每一輪的內部排序會使用到計數排序來實現，因為每一位上的數字無非就是0-9，是一個小範圍的數，所以使用計數排序很合適。
基數排序執行示意圖：
具體的實現程式碼如下：
public int[] radixSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
//記錄待排序數組中的最大值
int max = array[0];
for (int i : array) {
if (i > max) {
max = i;
}
}
//獲取最大值的位數
int maxDigits = 0;
while (max != 0) {
max /= 10;
maxDigits++;
}
//用來計數排序的臨時數組
int[] temp = new int[10];
//用來存放每輪排序後的結果
int[] sortedArray = new int[array.length];
for (int d = 1; d <= maxDigits; d++) {
//每次循環開始前都要清空temp數組中的值
replaceArray(temp, null);
//記錄每個數出現的次數
for (int a : array) {
temp[getNumberFromDigit(a, d)]++;
}
//將temp數組進行轉換，記錄每個數在最後排好序的數組中應該要存放的位置+1（如果有重複的就記錄最後一個）
for (int j = 1; j < temp.length; j++) {
temp[j] += temp[j - 1];
}
//這裡必須是從後往前遍歷，以此來保證穩定性
for (int i = array.length - 1; i >= 0; i--) {
int index = getNumberFromDigit(array[i], d);
sortedArray[temp[index] - 1] = array[i];
temp[index]--;
}
//一輪計數排序過後，將這次排好序的結果賦值給原數組
replaceArray(array, sortedArray);
}
return array;
}
private final static int[] sizeTable = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
/**
* 獲取指定位數上的數字是多少
*/
private int getNumberFromDigit(int number, int digit) {
if (digit < 0) {
return -1;
}
return (number / sizeTable[digit - 1]) % 10;
}
private void replaceArray(int[] originalArray, int[] replaceArray) {
if (replaceArray == null) {
for (int i = 0; i < originalArray.length; i++) {
originalArray[i] = 0;
}
} else {
for (int i = 0; i < originalArray.length; i++) {
originalArray[i] = replaceArray[i];
}
}
}
11 複雜度及穩定性
| 排序演算法 | 時間複雜度 | 空間複雜度 | 穩定性 | ||
|---|---|---|---|---|---|
| 平均情況 | 最好情況 | 最壞情況 | |||
| 冒泡排序 | |
|
|
 |
穩定 |
| 選擇排序 | |
|
|
|
不穩定 |
| 插入排序 | |
|
|
|
穩定 |
| 希爾排序 | 取決於增量的選擇 | |
不穩定 | ||
| 堆排序 | |
|
|
|
不穩定 |
| 歸併排序 | |
|
|
|
穩定 |
| 快速排序 | |
|
|
 |
不穩定 |
| 計數排序 |  |
|
|
 |
穩定 |
| 桶排序 | 取決於桶散列的結果和內部排序演算法的時間複雜度 |  |
穩定 | ||
| 基數排序 |  |
|
|
 |
穩定 |
（其中：
- k表示計數排序中最大值和最小值之間的差值；
- l表示桶排序中桶的個數；
- d表示基數排序中最大值的位數，r表示是多少進位；
- 希爾排序的時間複雜度很大程度上取決於增量gap sequence的選擇，不同的增量會有不同的時間複雜度。文中使用的「gap=length/2」和「gap=gap/2」是一種常用的方式，也被稱為希爾增量，但其並不是最優的。其實希爾排序增量的選擇與證明一直都是個數學難題，而下圖列出的是迄今為止大部分的gap sequence選擇的方案）
12 小彩蛋：猴子排序
在幾十年的電腦科學發展中，誕生了很多優秀的演算法，大家都在為了能開發出更高效的演算法而努力。但是在這其中也誕生了一些僅供娛樂的搞笑演算法，猴子排序就是其中的一種。
猴子排序的實現很簡單，隨機找出兩個元素進行交換，直到隨機交換到最後能正確排好序的時候才會停止。
public int[] bogoSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
Random random = new Random();
while (!inOrder(array)) {
for (int i = 0; i < array.length; i++) {
int swapPosition = random.nextInt(i + 1);
if (swapPosition == i) {
continue;
}
array[i] = array[i] ^ array[swapPosition];
array[swapPosition] = array[i] ^ array[swapPosition];
array[i] = array[i] ^ array[swapPosition];
}
}
return array;
}
private boolean inOrder(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1]) {
return false;
}
}
return true;
}
更多內容請關注微信公眾號：奇客時間
原創不易，未得准許，請勿轉載，翻版必究
