高等排序算法,归并排序和高效排序的衍生难点

作者: 网络工程  发布:2019-09-06
逆序对难点

先是我们介绍一下怎么着是逆序对?以下内容摘自百度完善:

设 A 为叁个有 n 个数字的不改变集 ,在那之中具备数字各差别样。要是存在正整数 i, j 使得 1 ≤ i < j ≤ n 并且 A[i] > A[j],则 <A[i], A[j]> 这几个不变对可以称作 A 的一个逆序对,也称作逆序数。

看完逆序对的定义后相信我们已经对逆序对有了迟早的打听。现在大家来思量什么求出三个随便数据中逆序对的个数。情理之中的话,大家大致和自个儿一致想到了叁个最简易但最笨的格局——遍历整个随机数据集,二个一个相比,假诺是逆序对则计数器加1,反之则继续比较。

此方法在任性数据比较少时就是叁个好法子,就算其时间复杂度为O。但随意数据若是比较多,该方式就不适用了。既然以前大家上学了归并排序,那么能否用此算法来化解该难点呢?答案鲜明是足以的。

那边大家采用自底向上的合併排序算法,其算法理念为:假定待排序表含有n个记录,则足以看做是n个有序的子表,每种子表长度为1,然则两两归并,得到「n/2」个长度为2或1的有序表;再两两归并,······如此重复,直到合併成叁个长短为n的平稳表截至。

在合并arr[i...i+sz-1]和arr[i+sz...i+sz*2-1]那五个子表的进程中,当arr[i+sz] < arr[i]时,则设有sz个逆序对。因而,我们能够使用那贰个法规求得随机数据汇总的逆序对个数。

宗旨代码如下:

template<typename T>long long __merge(T arr[], int l, int mid, int r) { T aux[r - l + 1]; for (int i = 0; i <= r; i++) aux[i - l] = arr[i]; int i = l, j = mid + 1; long long count = 0; for (int k = l; k <= r; k++) { if (i > mid) { arr[k] = aux[j - l]; j++; } else if  { arr[k] = aux[i - l]; i++; } else if (aux[i - l] < aux[j - l]) { arr[k] = aux[i - l]; i++; } else { arr[k] = aux[j - l]; count += (long long) (mid - i + 1); j++; } } return count;}template<typename T>long long inversionCount(T arr[], int n) { long long count; for (int step = 1; step <= n; step += step) { for (int i = 0; i + step < n; i += step + step) { count = __merge(arr, i, i + step - 1, min(i + step + step - 1, n - 1)); } } return count;}

为了测量检验该算法在一齐有序和完全冬天的专擅数据集的情景下是或不是正确,我们在TestHelper.h文件中加多如下代码:

 // 生成一个完全有序的数组 int *generateOrderedArray { return generateNearlyOrderedArray; } // 生成一个完全逆序的数组 int *generateInversedArray { int *arr = generateOrderedArray; for (int i = n / 2 - 1; i >= 0; i--) swap(arr[i], arr[n - i - 1]); return arr; }

下一场大家在main()中调用,看看其运转结果吧:

Test Inversion Count for Random Array, n = 100000 :2511332485Test Inversion Count for Ordered Array, n = 100000 :0Test Inversion Count for Inversed Array, n = 100000 :4999950000

除此而外,大家还足以选择自顶向下的统一排序算法来求取随机数据聚集的逆序对个数,其算法观念为:假定待排序表含有n个记录,递归地将前半有个别笔录和后半有个别记录各自归并,获得排序后的两有的记录,然后再选用合併算法将这两局地联合在一块。

其主干代码如下:

// merge函数求出在arr[l...mid]和arr[mid+1...r]有序的基础上, arr[l...r]的逆序数对个数template<typename T>long long __merge(T arr[], int l, int mid, int r) { int *aux = new int[r - l + 1]; for (int i = l; i <= r; i++) aux[i - l] = arr[i]; // 初始化逆序数对个数 res = 0 long long res = 0; // 初始化,i指向左半部分的起始索引位置l;j指向右半部分起始索引位置mid+1 int j = l, k = mid + 1; for (int i = l; i <= r; i++) { if (j > mid) { // 如果左半部分元素已经全部处理完毕 arr[i] = aux[k - l]; k++; } else if  { // 如果右半部分元素已经全部处理完毕 arr[i] = aux[j - l]; j++; } else if (aux[j - l] <= aux[k - l]) { // 左半部分所指元素 <= 右半部分所指元素 arr[i] = aux[j - l]; j++; } else { // 右半部分所指元素 < 左半部分所指元素 arr[i] = aux[k - l]; k++; // 此时, 因为右半部分k所指的元素小 // 这个元素和左半部分的所有未处理的元素都构成了逆序数对 // 左半部分此时未处理的元素个数为 mid - j + 1 res += (long long) (mid - j + 1); } } delete[] aux; return res;}// 求arr[l..r]范围的逆序数对个数// 思考: 归并排序的优化可否用于求逆序数对的算法? :)template<typename T>long long __inversionCount(T arr[], int l, int r) { if (l >= r) return 0; int mid = l +  / 2; // 求出 arr[l...mid] 范围的逆序数 long long res1 = __inversionCount(arr, l, mid); // 求出 arr[mid+1...r] 范围的逆序数 long long res2 = __inversionCount(arr, mid + 1, r); return res1 + res2 + __merge(arr, l, mid, r);}// 递归求arr的逆序数对个数template<typename T>long long inversionCount(T arr[], int n) { return __inversionCount(arr, 0, n - 1);}

其运转结果为:

Test Inversion Count for Random Array, n = 1000000 :250154505378Test Inversion Count for Ordered Array, n = 1000000 :0Test Inversion Count for Inversed Array, n = 1000000 :499999500000
O的排序算法

大家先来探视nlogn比n2快略带?

图片 1

归并排序(Merge Sort)

算法观念:假定待排序表含有n个记录,递归地将前半片段记下和后半部分记录各自归并,获得排序后的两有个别记录,然后在利用合併算法将这两有的联合在同步。

算法演示:

图片 2归并排序

着力代码如下:

// 合并算法,将arr[l...mid]和arr[mid+1...r]两部分进行归并template<typename T>void __merge(T arr[], int l, int mid, int r) { T aux[r - l + 1]; for (int i = l; i <= r; i++) aux[i - l] = arr[i]; int i = l, j = mid + 1; for (int k = l; k <= r; k++) { if (i > mid) { arr[k] = aux[j - l]; j++; } else if  { arr[k] = aux[i - l]; i++; } else if (aux[i - l] < aux[j - l]) { arr[k] = aux[i - l]; i++; } else { arr[k] = aux[j - l]; j++; } }}// 递归使用归并排序,对arr[l...r]的范围进行排序template<typename T>void __mergeSort(T arr[], int l, int r) { if (l >= r) return; int mid =  / 2; __mergeSort(arr, l, mid); __mergeSort(arr, mid + 1, r); __merge(arr, l, mid, r);}template<typename T>void mergeSort(T arr[], int n) { __mergeSort(arr, 0, n - 1);}

这我们在main()中调用mergeSort(),以及大家事先学习过的排序算法,这里就不在演示如何增添代码了。前边介绍4种基本排序算法时,已经清楚介绍了怎么增多代码,若是忘记请查看以前的排序基础文章。好了,大家运营我们的主次,看看运营结果吗,结果如下:

Merge Sort : 0.012 sInsertion Sort : 2.121 sShell Sort : 0.014 s

安分守纪大家事先的惯例,本次运维结果是在处理随机数据的气象下得出来的,但本次我们将数据规模调度到了50000个随机数据。大家得以显著发掘在拍卖大范围随机数据下归并排序的频率如此之高。

随之我们来看看在看似有序的人身自由数据的状态下,大家的联合排序是或不是能维持这种高功用呢?结果如下:

Merge Sort : 0.008 sInsertion Sort : 0.002 sShell Sort : 0.011 s

从结果中开采,大家的联合排序还是能维系高效地管理周边有序的数量。但大家再回忆一下归并排序的代码,不知有未有察觉大家的代码中仍有不足之处?不及大家先看看优化后的代码:

// 递归使用归并排序,对arr[l...r]的范围进行排序template<typename T>void __mergeSort(T arr[], int l, int r) { if (r - l <= 15) { __insertionSort(arr, l, r); return; } int mid =  / 2; __mergeSort(arr, l, mid); __mergeSort(arr, mid + 1, r); if (arr[mid] > arr[mid + 1]) __merge(arr, l, mid, r);

当大家待排序的数目很少时,大家得以将排序转换为插入排序。即便插入排序是时刻复杂度为O的排序算法,但在拍卖小框框数量时其功能还是较高的。此处的插入排序算法源码如下:

template<typename T>void __insertionSort(T arr[], int l, int r) { for (int i = l + 1; i <= r; i++) { // 寻找元素arr[i]合适的插入位置 T e = arr[i]; // j保存元素e应该插入的位置 int j; for (j = i; j > l && arr[j - 1] > e; j--) { arr[j] = arr[j - 1]; } arr[j] = e; } return;}

再有一处优化正是大家扩充了贰个if推断,为何要加进这几个论断呢?因为,我们若要进行合并排序操作都以在arr[mid] > arr[mid + 1]的意况下。假诺arr[mid] <= arr[mid + 1]则已表明待排序已经稳步了,无需再举行合併排序操作了。

好了让大家看看优化后的周转结果吗:

Merge Sort : 0.003 sInsertion Sort : 0.001 sShell Sort : 0.006 s

上述归并排序都以选拔了自顶向下的递归达成进行排序,今后大家来拜谒使用递归实现自底向上的会合排序。

算法观念:假定待排序表含有n个记录,则可以作为是n个有序的子表,每一种子表长度为1,但是两两归并,获得「n/2」个长度为2或1的有序表;再两两归并,······如此重复,直到合并成叁个长度为n的不改变表甘休。

算法演示:

图片 3归并排序

基本代码如下:

template<typename T>void mergeSortBU(T arr[], int n) { for (int sz = 1; sz <= n; sz += sz) { for (int i = 0; i + sz < n; i += sz + sz) { // 对arr[i...i+sz-1]和arr[i+sz...i+sz*2-1]进行合并 __merge(arr, i, i + sz - 1, min(i + sz + sz - 1, n - 1)); } }}

归并部分大家利用在此以前的__merge()。好了,我们在main()中调用一下呢,其运行结果如下:

Merge SortBU : 0.013 s

本文由今晚买四不像发布于网络工程,转载请注明出处:高等排序算法,归并排序和高效排序的衍生难点

关键词: