高级排序算法

本篇包括归并排序和快速排序，它们都是采用了分治法的 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));       }   }}

归并排序特点

快速排序

快速排序将一个序列分成两个子序列，两部分独立地排序。

步骤：

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;   }}

算法改进——保持序列的随机性

快速排序的最好情况是每次都正好将序列对半分，但对于一个趋近有序的序列，会出现切分不平衡的情况，使得算法极为低效。此时打乱原有序列的顺序便能预防这种情况。

random.shuffle(lst)

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] 排序}

快速排序特点

源码地址

https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Python/merge_sort

https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Java/mergeSort

https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Python/quick_sort

https://github.com/tyrotalk/Algorithms-in-Action/tree/master/02-Sorting-Advance/Code-Java/quickSort

生成海报

免责声明：本网站内容主要来自原创、合作伙伴供稿和第三方自媒体作者投稿，凡在本网站出现的信息，均仅供参考。本网站将尽力确保所提供信息的准确性及可靠性，但不保证有关资料的准确性及可靠性，读者在使用前请进一步核实，并对任何自主决定的行为负责。本网站对有关资料所引致的错误、不确或遗漏，概不负任何法律责任。任何单位或个人认为本网站中的网页或链接内容可能涉嫌侵犯其知识产权或存在不实内容时，应及时向本网站提出书面权利通知或不实情况说明，并提供身份证明、权属证明及详细侵权或不实情况证明。本网站在收到上述法律文件后，将会依法尽快联系相关文章源头核实，沟通删除相关内容或断开相关链接。