黑马程序员技术交流社区

标题: 关于一些常用的排序算法（付java代码）（二） [打印本页]

---

作者: 孙辉辉    时间: 2012-12-15 11:20
标题: 关于一些常用的排序算法（付java代码）（二）


接上一篇
4. 归并排序
归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间，比如需要规定的数组分别为： [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;
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 = arrayCopy[highIdx++];
} else if (highIdx > hi - lo) {
// right sub array exhausted
array = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) {
array = arrayCopy[lowIdx++];
} else {
array = arrayCopy[highIdx++];
}
}
}
})


5. 快速排序
快速排序也是用归并方法实现的一个“分而治之”的排序算法，它的魅力之处在于它能在每次partition（排序算法的核心所在）都能为一个数组元素确定其排序最终正确位置（一次就定位准，下次循环就不考虑这个元素了）。
快速排序的partition操作按以下逻辑进行，假定本次排序的数组为arr：
1） 选择一个元素（为了简单起见，就选择本次partition的第一个元素，即arr[0]）作为基准元素，接下来的步骤会为其确定排序完成后最终的位置；
2） 1） 接下来需要遍历[1…n-1]对应的数组元素以帮助找到arr[0]值（以v替代）对应的位置，定义i为当前访问数组的索引，lt为值小于v的最大索引，gt为值大于v的最小索引，那么在遍历过程中，如果发现i指向的值与v相等，则将i值加1，继续下一次比较；如果i指向的值比v小，则将i和lt对应的元素进行交换，然后分别将两个索引加1；如果i指向的值比v大，则将i与gt对应的元素进行交换，然后i自增，gt自减。循环遍历完成（i > gt时结束）之后可以保证[0…lt-1]对应的值都是比v小的，[lt..gt]之间的值都是与v相等的，[gt+1…n-1]对应的值都是比v大的。
3） 分别对[0…lt-1]和[gt+1…n-1]两个子数组进行排序，如此递归，直至子子子数组的长度为0。
下面举个partition的具体实例：
初始（i = 1, lt = 0, gt = 8）：
[41, 59, 43, 26, 63, 30, 29, 26, 42]（需要确定位置的为0th[41]）
第一趟（i = 1, lt = 0, gt = 8）：
[41, 42, 43, 26, 63, 30, 29, 26, 59]（1st[59] > 41，1st[59]<->8th[42]，gt--）
第二趟（i = 1, lt = 0, gt = 7）：
[41, 26, 43, 26, 63, 30, 29, 42, 59]（1st[42] > 41，1st[42]<->7th[26]，gt--）
第三趟（i = 1, lt = 0, gt = 6）：
[26, 41, 43, 26, 63, 30, 29, 42, 59]（1st[26] < 41, 1st[26]<->0st[41]，i++, lt++）
第四趟（i = 2, lt = 1, gt = 6）：
[26, 41, 29, 26, 63, 30, 43, 42, 59]（2nd[43] > 41，2nd[43]<->6th[29]，gt--）
第五趟（i = 2, lt = 1, gt = 5）：
[26, 29, 41, 26, 63, 30, 43, 42, 59]（2nd[29] < 41, 2nd[29]<->1st[41]，i++，lt++）
第六趟（i = 3, lt = 2, gt = 5）：
[26, 29, 26, 41, 63, 30, 43, 42, 59]（3rd[26] < 41，3rd[26]<->2nd[41]，i++，lt++）
第七趟（i = 4, lt = 3, gt = 5）：
[26, 29, 26, 41, 30, 63, 43, 42, 59] （4th[63] > 41，4th[63]<->5th[30]，gt--）
第八趟（i = 4, lt = 3, gt = 4）：
[26, 29, 26, 30, 41, 63, 43, 42, 59]（4th[30] < 41，4th[30]<->3rd[41]，i++，lt++）
可以看出，在一次partition之后，以41为分割线，41左侧皆为比它小的元素，41右侧皆为比它大或相等的元素（当然这个实例比较特殊，没有出现和41相等的元素）。
一般情况下，冒泡排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(log2n)~O(n) 。
实现代码：
/**
* Quick Sorting
*/
QUICK(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) {
if (lo >= hi) {
return;
}

T toFinal = array[lo];
int leftIdx = lo;
int rightIdx = hi;

int i = lo + 1;

while (i <= rightIdx) {
int compare = array.compareTo(toFinal);
if (compare == 0) {
i++;
} else if (compare < 0 == ascend) {
exchange(array, leftIdx++, i++);
} else {
exchange(array, rightIdx--, i);
}
}

// partially sort left array and right array
// no need to include the leftIdx-th to rightIdx-th elements
// since they are already in its final position
sort(array, lo, leftIdx - 1, ascend);
sort(array, rightIdx + 1, hi, ascend);
}
})

---

作者: 胡胜    时间: 2012-12-15 11:30
好极了{:soso_e179:}

---

作者: 王晨    时间: 2012-12-15 15:21
整理的不错，不客气了，拷走！！！

---

作者: 黑马刘岩    时间: 2012-12-15 16:18
感谢分享！

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2