Java で一般的に使用される 6 つのソート アルゴリズムの詳細な内訳
- 高洛峰オリジナル
- 2017-01-17 13:11:451361ブラウズ
ソート アルゴリズムは多くの場所で使用されています。私は最近このアルゴリズムを再度見直し、将来のレビューのために資料を保存するためにそれを簡単に実装しました。
早速、古典的な並べ替えアルゴリズムを 1 つずつ見てみましょう:
1. 選択並べ替え
選択並べ替えの基本的な考え方は、配列を走査する過程で i が現在のシーケンスを表すということです。 [i...n-1] の中から最小値を求め、求めた最小値を i が指す値と交換します。要素を決定する各プロセスには、最大値を選択するサブプロセスがあるため、人々はそれを明確に選択ソートと呼んでいます。例を見てみましょう:
Initial: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
i = 0: [2, 17, 16, 16, 7, 31 , 39 , 32, 38, 11] (0 番目 [38]6ea4592b24bc7db0e0f4c2adf7135ebc4 番目 [17])
i = 2: [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2 番目 [11]84bdcd0f459e618d614012e7ae8457f99 番目 [31])
i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (交換の必要はありません)
i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (交換不要)
i = 9: [2, 7, 11, 16, 16, 17, 31, 32 , 38, 39] (交換する必要はありません)
この例からわかるように、ソートが進むにつれて (i が徐々に増加して)、比較の数はますます少なくなりますが、配列が最初に順序付けされているかどうかに関係なく、選択ソートは i から配列の末尾まで実行されるため、指定された長さの配列の場合、選択ソートの比較数は固定されます: 1 + 2 + 3 + … + n = n *。 (n + 1) / 2、交換回数は初期配列の順序に関係します。初期配列の順序がランダムな場合、最悪の場合、配列要素は n 回交換されます。最良の場合は 0 回です (配列自体が順序付けされています)。
選択ソートの時間計算量と空間計算量はそれぞれ O(n2) と O(1) であると推測できます (選択ソートには配列要素の交換のための追加スペースのみが必要です)。
実装コード:
/**
* Selection Sorting
*/
SELECTION(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.length;
for (int i = 0; i < len; i++) {
int selected = i;
for (int j = i + 1; j < len; j++) {
int compare = array[j].compareTo(array[selected]);
if (compare != 0 && compare < 0 == ascend) {
selected = j;
}
}
exchange(array, i, selected);
}
}
})2. 挿入ソート
挿入ソートの基本的な考え方は、配列番号 i より前の要素、つまり [0..i-] を走査するプロセス中に、 1] がソートされている場合、これは要素の正しい位置 k を見つける必要があります。x の場合、挿入ソートにもソートの特性に従って名前が付けられます。
以下は例です。赤でマークされた数字は、このソートに関与しない要素です。たとえば、2 番目の並べ替えに参加する要素は [11, 31, 12] で、挿入する必要がある要素は 12 ですが、12 は現在正しい位置にないため、必要があります。比較中に、12 より小さい最初の要素 11 が見つかるまで比較が停止され、31 に対応するインデックス 1 が比較されます。 12 を挿入する必要がある位置。
初期: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
最初の旅行: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] ] (移動要素なし)
2 番目のパス: [11、12、31、5、34、30、26、38、36、18] (31 を後方に移動)
3 番目のパス: [5、11、12、31 、34、30、26、38、36、18] (11、12、31 はすべて後退します)
4 番目の旅行: [5、11、12、31、34、30、26、38、36、18] (移動要素なし)
5 番目のトリップ: [5、11、12、30、31、34、26、38、36、18] (31、34 は後方に移動)
6 番目のトリップ: [5、11、 12、26、30、31、34、38、36、18] (30、31、34 は後退します)
7 番目の旅行: [5、11、12、26、30 、31、34、38、36、18 ] (移動要素なし)
8 番目のパス: [5、11、12、26、30、31、34、36、38、18] (38 は後方に移動)
9 番目の移動: [5、11、12、 18、26、30、31、34、36、38] (26、30、31、34、36、38 を後ろに移動)
插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下（给定的数组恰好为倒序）插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ，这种极端情况下，插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法，插入效率与数组初始顺序息息相关。一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。
实现代码：
/**
* Insertion Sorting
*/
INSERTION(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int len = array.length;
for (int i = 1; i < len; i++) {
T toInsert = array[i];
int j = i;
for (; j > 0; j–) {
int compare = array[j - 1].compareTo(toInsert);
if (compare == 0 || compare < 0 == ascend) {
break;
}
array[j] = array[j - 1];
}
array[j] = toInsert;
}
}
})3. 冒泡排序
冒泡排序可以算是最经典的排序算法了，记得小弟上学时最先接触的也就是这个算法了，因为实现方法最简单，两层 for 循环，里层循环中判断相邻两个元素是否逆序，是的话将两个元素交换，外层循环一次，就能将数组中剩下的元素中最小的元素“浮”到最前面，所以称之为冒泡排序。
照例举个简单的实例吧：
初始状态： [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
内层第一趟： [24, 19, 26, 39, 36, 7, 31, 29, 23 , 38 ] （ 9th [23]e09be6022d700e04aeaa85a5f42fdcb28th [38 ）
内层第二趟： [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] （ 8th [23]e09be6022d700e04aeaa85a5f42fdcb27th [29] ）
内层第三趟： [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] （ 7th [23]e09be6022d700e04aeaa85a5f42fdcb26th [31] ）
内层第四趟： [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] （ 7 、 23 都位于正确的顺序，无需交换）
内层第五趟： [24, 19, 26, 39, 7 , 36 , 23, 31, 29, 38] （ 5th [7]e09be6022d700e04aeaa85a5f42fdcb24th [36] ）
内层第六趟： [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] （ 4th [7]e09be6022d700e04aeaa85a5f42fdcb23rd [39] ）
内层第七趟： [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] （ 3rd [7]e09be6022d700e04aeaa85a5f42fdcb22nd [26] ）
内层第八趟： [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] （ 2nd [7]e09be6022d700e04aeaa85a5f42fdcb21st [19] ）
内层第九趟： [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] （ 1st [7]e09be6022d700e04aeaa85a5f42fdcb20th [24] ）
……… .
其实冒泡排序跟选择排序比较相像，比较次数一样，都为 n * (n + 1) / 2 ，但是冒泡排序在挑选最小值的过程中会进行额外的交换（冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换，与之对应的是选择排序，只会在内层循环比较结束之后根据情况决定是否进行交换），所以在我看来，选择排序属于冒泡排序的改进版。
实现代码：
/**
* Bubble Sorting, it's very similar with Insertion Sorting
*/
BUBBLE(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int length = array.length;
int lastExchangedIdx = 0;
for (int i = 0; i < length; i++) {
// mark the flag to identity whether exchange happened to false
boolean isExchanged = false;
// last compare and exchange happened before reaching index i
int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i;
for (int j = length – 1; j > currOrderedIdx; j–) {
int compare = array[j - 1].compareTo(array[j]);
if (compare != 0 && compare > 0 == ascend) {
exchange(array, j – 1, j);
isExchanged = true;
lastExchangedIdx = j;
}
}
// if no exchange happen means array is already in order
if (isExchanged == false) {
break;
}
}
}
})4. 希尔排序
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”，划分为若干个小的数组，以 gap 来划分，比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ，如果以 gap = 2 来划分，可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组（对应的，如 gap = 3 ，则划分的数组为： [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] ）然后分别对划分出来的数组进行插入排序，待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤，直至 gap = 1 ，即对整个数组进行插入排序，此时的数组已经基本上快排好序了，所以需要移动的元素会很小很小，解决了插入排序在处理大规模数组时较多移动次数的问题。
具体实例请参照插入排序。
希尔排序是插入排序的改进版，在数据量大的时候对效率的提升帮助很大，数据量小的时候建议直接使用插入排序就好了。
实现代码：
/**
* Shell Sorting
*/
SHELL(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
int length = array.length;
int gap = 1;
// use the most next to length / 3 as the first gap
while (gap < length / 3) {
gap = gap * 3 + 1;
}
while (gap >= 1) {
for (int i = gap; i < length; i++) {
T next = array[i];
int j = i;
while (j >= gap) {
int compare = array[j - gap].compareTo(next);
// already find its position
if (compare == 0 || compare < 0 == ascend) {
break;
}
array[j] = array[j - gap];
j -= gap;
}
if (j != i) {
array[j] = next;
}
}
gap /= 3;
}
}
})5. 归并排序
归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间，比如需要规定的数组分别为： [3, 6, 8, 11] 和 [1, 3, 12, 15] （虽然逻辑上被划为为两个数组，但实际上这些元素还是位于原来数组中的，只是通过一些 index 将其划分成两个数组，原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ，我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分）那么需要的额外数组的长度为 4 + 4 = 8 。归并的过程可以简要地概括为如下：
1） 将两个子数组中的元素复制到新数组 copiedArray 中，以前面提到的例子为例，则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ；
2） 设置两个指针分别指向原子数组中对应的第一个元素，假定这两个指针取名为 leftIdx 和 rightIdx ，则 leftIdx = 0 （对应 copiedArray 中的第一个元素 [3] ）， rightIdx = 4 （对应 copiedArray 中的第五个元素 [1] ）；
3） 比较 leftIdx 和 rightIdx 指向的数组元素值，选取其中较小的一个并将其值赋给原数组中对应的位置 i ，赋值完毕后分别对参与赋值的这两个索引做自增 1 操作，如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾，则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。
下面给个归并的具体实例：
第一趟：
辅助数组 [21 , 28, 39 | 35, 38] （数组被拆分为左右两个子数组，以 | 分隔开）
[21 , , , , ] （第一次 21 与 35 比较 , 左边子数组胜出， leftIdx = 0 ， i = 0 ）
第二趟：
辅助数组 [21, 28 , 39 | 35, 38]
[21 , 28, , , ] （第二次 28 与 35 比较，左边子数组胜出， leftIdx = 1 ， i = 1 ）
第三趟： [21, 28, 39 | 35 , 38]
[21 , 28 , 35, , ] （第三次 39 与 35 比较，右边子数组胜出， rightIdx = 0 ， i = 2 ）
第四趟： [21, 28, 39 | 35, 38 ]
[21 , 28 , 35 , 38, ] （第四次 39 与 38 比较，右边子数组胜出， rightIdx = 1 ， i = 3 ）
第五趟： [21, 28, 39 | 35, 38]
[21 , 28 , 35 , 38 , 39] （第五次时右边子数组已复制完，无需比较 leftIdx = 2 ， i = 4 ）
以上便是一次归并的过程，我们可以将整个需要排序的数组做有限次拆分（每次一分为二）直到分为长度为 1 的小数组为止，长度为 1 时数组已经不用排序了。在这之后再逆序（由于采用递归）依次对这些数组进行归并操作，直到最后一次归并长度为 n / 2 的子数组，归并完成之后数组排序也完成。
归并排序需要的额外空间是所有排序中最多的，每次归并需要与参与归并的两个数组长度之和相同个元素（为了提供辅助数组）。则可以推断归并排序的空间复杂度为 1 + 2 + 4 + … + n = n * ( n + 2) / 4 （忽略了 n 的奇偶性的判断），时间复杂度比较难估，这里小弟也忘记是多少了（囧）。
实现代码：
/**
* Merge sorting
*/
MERGE(new Sortable() {
public <T extends Comparable<T>> void sort(T[] array, boolean ascend) {
this.sort(array, 0, array.length – 1, ascend);
}
private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) {
// OPTIMIZE ONE
// if the substring's length is less than 20,
// use insertion sort to reduce recursive invocation
if (hi – lo < 20) {
for (int i = lo + 1; i <= hi; i++) {
T toInsert = array[i];
int j = i;
for (; j > lo; j–) {
int compare = array[j - 1].compareTo(toInsert);
if (compare == 0 || compare < 0 == ascend) {
break;
}
array[j] = array[j - 1];
}
array[j] = toInsert;
}
return;
}
int mid = lo + (hi – lo) / 2;
sort(array, lo, mid, ascend);
sort(array, mid + 1, hi, ascend);
merge(array, lo, mid, hi, ascend);
}
private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) {
// OPTIMIZE TWO
// if it is already in right order, skip this merge
// since there's no need to do so
int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) {
return;
}
@SuppressWarnings("unchecked")
T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
int lowIdx = 0;
int highIdx = mid – lo + 1;
for (int i = lo; i <= hi; i++) {
if (lowIdx > mid – lo) {
// left sub array exhausted
array[i] = arrayCopy[highIdx++];
} else if (highIdx > hi – lo) {
// right sub array exhausted
array[i] = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {
array[i] = arrayCopy[lowIdx++];
} else {
array[i] = arrayCopy[highIdx++];
}
}
}
})6. 快速排序
快速排序也是用归并方法实现的一个“分而治之”的排序算法，它的魅力之处在于它能在每次 partition （排序算法的核心所在）都能为一个数组元素确定其排序最终正确位置（一次就定位准，下次循环就不考虑这个元素了）。
更多Java中常用的6种排序算法详细分解相关文章请关注PHP中文网！