科技猎高级排序算法
本篇包括归并排序和快速排序，它们都是采用了分治法的 O(NlogN) 算法。
归并排序
归并排序是建立在归并操作上的一种有效的排序算法，其将两个有序的序列归并成一个更大的有序序列。
原地归并
原地归并将两个不同的有序序列归并到第三个序列中，在实现过程中就需要一个辅助序列。
Python3 实现
def merge(lst, l, mid, r): """ 将 lst[l...mid] 和 lst[mid+1...r] 两部分进行归并 """ aux = copy.deepcopy(lst[l:r + 1]) #辅助序列aux i, j = l, mid + 1 for k in range(l, r + 1): if i > mid: # 左半部分元素已经处理完毕 lst[k] = aux[j - l] j += 1 elif j > r: # 右半部分元素已经处理完毕 lst[k] = aux[i - l] i += 1 elif aux[i - l] < aux[j - l]: lst[k] = aux[i - l] i += 1 else: lst[k] = aux[j - l] j += 1
Java 实现
// 将 arr[l...mid] 和 arr[mid+1...r] 两部分进行归并
public static void merge(Comparable[] arr, int l, int mid, int r) {
int i = l;
int j = mid + 1;
System.arraycopy(arr, l, aux, l, r - l + 1); //辅助序列aux
for (int k = l; k <= r; k++) {
if (i > mid) arr[k] = aux[j++]; //左半部分元素已经处理完毕
else if (j > r) arr[k] = aux[i++]; //右半部分元素已经处理完毕
else if (aux[i].compareTo(aux[j]) < 0) arr[k] = aux[i++];
else arr[k] = aux[j++];
}
}
自顶向下归并排序
对子序列 a[l…r] 进行排序， 先将其分为 a[l…mid] 和 a[mid+1…r] 两部分，分别通过递归调用将它们单独排序，最后将有序的子序列归并为最终的排序结果。
Python3 实现
def sort(lst): """ 初始化，使归并排序边界正确 """ sort_next(lst, 0, len(lst) - 1) def sort_next(lst, l, r): """ 使用自顶向下、递归进行归并排序,对 lst[l...r] 的范围进行排序 """ if l >= r: return mid = (l + r) // 2 sort_next(lst, l, mid) #将左半部分排序 sort_next(lst, mid + 1, r) #将右半部分排序 # 对于 lst[mid] <= lst[mid + 1]的情况, 不进行merge if lst[mid] > lst[mid + 1]: merge(lst, l, mid, r) #归并
Java 实现
private static Comparable[] aux; // 辅助数组
public static void newSort(Comparable[] arr) {
int n = arr.length;
aux = new Comparable[n]; // 一次性分配空间
newSort(arr, 0, n - 1);
}
// 使用递归进行归并排序,对 arr[l...r] 的范围进行排序
public static void newSort(Comparable[] arr, int l, int r) {
if (l >= r)
return;
int mid = (l + r) / 2;
newSort(arr, l, mid); // 将左半部分排序
newSort(arr, mid + 1, r); // 将右半部分排序
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
if (arr[mid].compareTo(arr[mid + 1]) > 0)
merge(arr, l, mid, r); // 归并
}
自底向上归并排序
原理：首先进行两两归并，然后四四归并，接着八八归并，一直下去，即先归并微型序列，再成对归并得到的子序列，一直下去，直到将整个序列归并。
Python3 实现
def sort(lst): """ 进行 lgN 次两两归并 """ n = len(lst) sz = 1 # sz 子数组大小 while sz < n: l = 0 # l 子数组索引 while l < n - sz: # 对于 lst[mid] <= lst[mid + 1]的情况, 不进行merge if lst[l + sz - 1] > lst[l + sz]: merge(lst, l, l + sz - 1, min(l + sz + sz - 1, n - 1)) l += sz + sz sz += sz
Java 实现
private static Comparable[] aux;
// 进行 lgN 次两两归并
public static void newSort(Comparable[] arr) {
int n = arr.length;
aux = new Comparable[n];
for (int sz = 1; sz < n; sz += sz) {
for (int l = 0; l < n - sz; l += sz + sz) {
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
if (arr[l + sz - 1].compareTo(arr[l + sz]) > 0)
merge(arr, l, l + sz - 1,
Math.min(l + sz + sz - 1, n - 1));
}
}
}
归并排序特点
- 对于长度为 N 的序列，自顶向下的归并排序和自顶向上的归并排序都需要 1/2NlgN 至 NlgN 次比较，最多访问序列 6NlgN 次；
- 归并排序的主要缺点是辅助序列所使用的额外空间和 N 的大小成正比。
快速排序
快速排序将一个序列分成两个子序列，两部分独立地排序。
步骤：
- 从序列中挑出一个基准。
- 切分操作：重新排序序列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于序列的中间位置。
- 递归地把小于基准值元素的子序列和大于基准值元素的子序列排序。
Python3 版本
def sort(lst): """ 对序列所有元素进行随机排序 """ sort_next(lst, 0, len(lst) - 1) def sort_next(lst, l, r): """ 快速排序 """ if r <= l: return p = partition(lst, l, r) #切分 sort_next(lst, l, p - 1) #将左半部分 lst[l...p-1] 排序 sort_next(lst, p + 1, r) #将右半部分 lst[p+1...r] 排序 def partition(lst, l, r): """ 将序列切分为 lst[l...p-1], lst[p], lst[p+1, r] """ v = lst[l] j = l for i in range(l + 1, r + 1): if lst[i] < v: j += 1 lst[j], lst[i] = lst[i], lst[j] lst[l], lst[j] = lst[j], lst[l] return j
Java 版本
public class QuickSort {
public static void newSort(Comparable[] arr) {
newSort(arr, 0, arr.length - 1);
}
public static void newSort(Comparable[] arr, int l, int r) {
if (l >= r) return;
int p = partition(arr, l, r); //切分
newSort(arr, l, p - 1); //将左半部分 arr[l...p-1] 排序
newSort(arr, p + 1, r); //将右半部分 arr[p+1...r] 排序
}
//将序列切分为 arr[l...p-1], arr[p], arr[p+1, r]
public static int partition(Comparable[] arr, int l, int r) {
Comparable v = arr[l];
int j = l;
for (int i = l + 1; i <= r; i++) {
if (arr[i].compareTo(v) < 0) {
j++;
swap(arr, i, j);
}
}
swap(arr, l, j);
return j;
}
//交换数组中两个数
public static void swap(Object[] arr, int index1, int index2) {
Object temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
}
算法改进——保持序列的随机性
快速排序的最好情况是每次都正好将序列对半分，但对于一个趋近有序的序列，会出现切分不平衡的情况，使得算法极为低效。此时打乱原有序列的顺序便能预防这种情况。
-
Python3:
random.shuffle(lst)
-
Java:
StdRandom.shuffle(arr);
算法改进——双路快速排序
改进快速排序的第二个方法是使用双路快速排序，其切分部分在选定一个基准后，会从序列左端开始向右扫描直到找到一个大于等于它的元素，再从序列右端开始向左扫描直到找到一个小于等于它的元素，交换这两个元素，如此继续。
Python3 版本
def partition(lst, l, r): """ 将序列切分为 lst[l...p-1], lst[p], lst[p+1, r] """ v = lst[l] i, j = l, r + 1 while True: i += 1 j -= 1 while i <= r and lst[i] < v: i += 1 while j >= l and lst[j] > v: j -= 1 if i >= j: break lst[i], lst[j] = lst[j], lst[i] lst[l], lst[j] = lst[j], lst[l] return j
Java 版本
public static int partition(Comparable[] arr, int l, int r) {
Comparable v = arr[l];
int i = l, j = r + 1;
while (true) {
while (arr[++i].compareTo(v) < 0 && i <= r);
while (arr[--j].compareTo(v) > 0 && j >= l);
if (i >= j) break;
swap(arr, i, j);
}
swap(arr, l, j);
return j;
}
算法改进——三路快速排序
改进快速排序的第三种方法是使用三路快速排序，其将序列分为切分为三个部分，分别对应小于、等于和大于切分元素的序列元素，再对小于和大于部分进行递归排序。
Python3 版本
def sort_next(lst, l, r): if r <= l: return v = lst[l] lt = l # lst[l+1...lt] < v i = l + 1 # lst[lt+1...i] = v gt = r + 1 # lst[i+1...h] > v while i < gt: if lst[i] < v: lst[lt + 1], lst[i] = lst[i], lst[lt + 1] i += 1 lt += 1 elif lst[i] > v: lst[gt - 1], lst[i] = lst[i], lst[gt - 1] gt -= 1 else: i += 1 lst[l], lst[lt] = lst[lt], lst[l] sort_next(lst, l, lt - 1) #将前半部分 lst[l...lt-1] 排序 sort_next(lst, gt, r) #将后半部分 lst[gt...r] 排序
Java 版本
public static void newSort(Comparable[] arr, int l, int r) {
if (l >= r) return;
int lt = l, i = l + 1, gt = r + 1;
Comparable v = arr[l];
while (i < gt) {
int cmp = arr[i].compareTo(v);
if (cmp < 0) swap(arr, ++lt, i++);
else if (cmp > 0) swap(arr, --gt, i);
else i++;
}
swap(arr, l, lt);
newSort(arr, l, lt - 1); //将左半部分 arr[l...p-1] 排序
newSort(arr, gt, r); //将右半部分 arr[p+1...r] 排序
}
快速排序特点
- 长度为 N 的序列排序所需的时间和 NlgN 成正比，平均需要 2NlgN 次比较；
- 随机打乱原始序列的顺序能防止快速排序出现最坏的情况。
源码地址
-
归并排序
-
Python
https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Python/merge_sort
-
Java
https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Java/mergeSort
-
Python
-
快速排序
-
Python
https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Python/quick_sort
-
Java
https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Java/quickSort
-
Python
End.
转载请注明来自36大数据（36dsj.com)： 36大数据 » 高级排序算法