Java에서 일반적으로 사용되는 6가지 정렬 알고리즘에 대한 자세한 분석
- 高洛峰원래의
- 2017-01-17 13:11:451388검색
정렬 알고리즘은 여러 곳에서 사용됩니다. 최근에 알고리즘을 다시 검토하고 나중에 검토할 자료를 저장하기 위해 간단히 직접 구현했습니다.
더 이상 고민하지 않고 고전적인 정렬 알고리즘을 하나씩 살펴보겠습니다.
1. 선택 정렬
선택 정렬의 기본 개념은 순회하는 것입니다. i가 있는 배열은 정렬해야 할 현재 시퀀스 번호를 나타내며, 나머지 [i...n-1] 중에서 최소값을 찾은 다음 찾은 최소값을 i가 가리키는 값과 교환해야 합니다. 요소를 결정하는 각 프로세스에는 최대값을 선택하는 하위 프로세스가 있기 때문에 사람들은 이를 선택 정렬이라고 생생하게 부릅니다. 예를 들어보겠습니다:
초기: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
i = 0: [2, 17 , 16 , 16, 7, 31, 39, 32, 38, 11] (0번째 [38]8번째 [2])
i = 1: [2, 7, 16, 16, 17 , 31, 39, 32, 38, 11] (1번째 [38]->4번째 [17])
i = 2: [2, 7, 11 , 16, 17, 31 , 39 , 32, 38, 16 ] (2번째 [11]->9번째 [16])
i = 3: [2, 7, 11, 16, 17, 31, 39, 32 , 38 , 16] (교환 불필요)
i = 4: [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4일 [17]-> 9일 [16])
i = 5: [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5번째 [31]9번째 [17] )
i = 6: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39 ] (6번째 [39]->9번째 [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. 삽입 정렬
삽입 정렬의 기본 아이디어는 배열을 순회하는 과정에서 시퀀스 앞의 요소를 가정하는 것입니다. number i는 [0. .i-1]이 모두 정렬되었습니다. 이번에는 "위치를 비우십시오"라는 요소의 올바른 위치 k를 찾고 마지막으로 k에 해당하는 요소 값을 x에 할당해야 합니다. 정렬의 특성에 따라 이름이 붙여지기도 합니다.
다음은 빨간색으로 표시된 숫자가 삽입된 숫자입니다. 빨간색으로 표시된 숫자와 X로 표시된 숫자 사이에 있는 요소입니다. 이후에 이동되는 요소는 1개씩 입니다. 예를 들어 2차 정렬에 참여하는 요소는 [11, 31, 12]이고, 삽입해야 할 요소는 12인데 현재 12는 없습니다. 정확한 위치를 찾기 때문에 이전 요소인 31, 11과 순서대로 이동해야 합니다. 비교를 하면서 비교된 요소를 이동하고, 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] (움직이는 요소 없음)
두 번째 패스: [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (뒤로 이동하려면 31)
세 번째 여행: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 모두 뒤로 이동)
네 번째 패스 : [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (움직이는 요소 없음)
다섯 번째 패스: [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] (31, 34 뒤로 이동)
여섯 번째 여행: [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은 뒤로 이동)
아홉 번째 여행: [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中文网！