快排和归并排序的思想都是分治
归并排序
整体而已，归并排序比插入排序更优
但近乎有序的数组，归并排序还是比插入排序慢。
以下是自顶向下的归并排序
图片来自于https://www.cnblogs.com/nullzx/p/5968170.html
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename T>
void __merge(T arr[], int l, int mid, int r){
//* VS不支持动态长度数组, 即不能使用 T aux[r-l+1]的方式申请aux的空间
//* 使用VS的同学, 请使用new的方式申请aux空间
//* 使用new申请空间, 不要忘了在__merge函数的最后, delete掉申请的空间
T aux[r-l+1];
//T *aux = new T[r-l+1]; 用new 和delete还是挺费时的
for( int i = l ; i <= r; i ++ )
aux[i-l] = arr[i];
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
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 ++;
}
}
//delete[] aux;
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){
if( l >= r )
return;
int mid = (l+r)/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 );
}
归并排序的优化
经过优化后依然是nlogn级别的，但性能更优
利用类似剪枝的技巧
// 使用优化的归并排序算法, 对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort2(T arr[], int l, int r){
// 优化2: 对于小规模数组, 使用插入排序
if( r - l <= 15 ){
insertionSort(arr, l, r);
return;
}
int mid = (l+r)/2;
__mergeSort2(arr, l, mid);
__mergeSort2(arr, mid+1, r);
// 优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if( arr[mid] > arr[mid+1] )
__merge(arr, l, mid, r);
}
只开辟一次空间的归并排序
// 比较Merge Sort和Merge Sort 2的性能效率
// Merge Sort 2 只开辟了一次辅助空间, 之后将这个辅助空间以参数形式传递给完成归并排序的其他子函数
// 可以看出 Merge Sort 2的性能优于 Merge Sort
template<typename T>
void __merge2(T arr[], T aux[], int l, int mid, int r){
// 由于aux的大小和arr一样, 所以我们也不需要处理aux索引的偏移量
// 进一步节省了计算量:)
for( int i = l ; i <= r; i ++ )
aux[i] = arr[i];
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i]; i ++;
}
else if( aux[i] < aux[j] ) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j]; j ++;
}
}
}
// 使用优化的归并排序算法, 对arr[l...r]的范围进行排序
// 其中aux为完成merge过程所需要的辅助空间
template<typename T>
void __mergeSort2(T arr[], T aux[], int l, int r){
// 对于小规模数组, 使用插入排序
if( r - l <= 15 ){
insertionSort(arr, l, r);
return;
}
int mid = (l+r)/2;
__mergeSort2(arr, aux, l, mid);
__mergeSort2(arr, aux, mid+1, r);
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if( arr[mid] > arr[mid+1] )
__merge2(arr, aux, l, mid, r);
}
template<typename T>
void mergeSort2(T arr[], int n){
// 在 mergeSort2中, 我们一次性申请aux空间,
// 并将这个辅助空间以参数形式传递给完成归并排序的各个子函数
T *aux = new T[n];
__mergeSort2( arr , aux, 0 , n-1 );
delete[] aux; // 使用C++, new出来的空间不要忘记释放掉:)
}
自底向上的归并排序
利用迭代
图片来自于https://www.cnblogs.com/nullzx/p/5968170.html
// 使用自底向上的归并排序算法
template <typename T>
void mergeSortBU(T arr[], int n){
// Merge Sort Bottom Up 无优化版本
// for( int sz = 1; sz < n ; sz += sz )
// for( int i = 0 ; i < n - sz ; i += sz+sz )
// // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
// __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );
// Merge Sort Bottom Up 优化
// 对于小数组, 使用插入排序优化
for( int i = 0 ; i < n ; i += 16 )
insertionSort(arr,i,min(i+15,n-1));
for( int sz = 16; sz < n ; sz += sz )
for( int i = 0 ; i < n - sz ; i += sz+sz )
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
if( arr[i+sz-1] > arr[i+sz] )
__merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );
// Merge Sort BU 也是一个O(nlogn)复杂度的算法，虽然只使用两重for循环
// 所以，Merge Sort BU也可以在1秒之内轻松处理100万数量级的数据
// 注意：不要轻易根据循环层数来判断算法的复杂度，Merge Sort BU就是一个反例
}
自底向上的归并排序因为没有应用到数组随机存取的特性，所以可以用来排序链表。
总体来说, Merge Sort BU 比 Merge Sort 快一些。但优化后, 二者的性能差距不明显
快速排序
在一个随机生成的数组，快排明显比归并排序快。
但基本有序的数组效率就不如归并好。
在几乎有序的数组（或者含大量重复键值）使用快排会使时间复杂度到O(n*n)。
在随机数组中效率：二路快排>快排>三路快排
在几乎有序数组中的效率：二路快排>快排>三路快排
在含有大量重复键值的数组中的效率：三路快排>二路快排>快排
// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int _partition(T arr[], int l, int r){
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr[l] , arr[rand()%(r-l+1)+l] );
T v = arr[l];
int j = l;
for( int i = l + 1 ; i <= r ; i ++ )
if( arr[i] < v ){
j ++;
swap( arr[j] , arr[i] );
}
swap( arr[l] , arr[j]);
return j;
}
// 对arr[l...r]部分进行快速排序
template <typename T>
void _quickSort(T arr[], int l, int r){
// 对于小规模数组, 使用插入排序进行优化
if( r - l <= 15 ){
insertionSort(arr,l,r);
return;
}
int p = _partition(arr, l, r);
_quickSort(arr, l, p-1 );
_quickSort(arr, p+1, r);
}
template <typename T>
void quickSort(T arr[], int n){
srand(time(NULL));
_quickSort(arr, 0, n-1);
}
随机化快速排序
可以避免几乎有序的数组进行快速排序时间复杂度退化成O(n*n)
template <typename T>
int _partition(T arr[], int l, int r){
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr[l] , arr[rand()%(r-l+1)+l] ); //关键句
T v = arr[l];
int j = l;
for( int i = l + 1 ; i <= r ; i ++ )
if( arr[i] < v ){
j ++;
swap( arr[j] , arr[i] );
}
swap( arr[l] , arr[j]);
return j;
}
二路快速排序
二路快速排序对含有大量重复键值的数组排序可以有效避免时间复杂度退化成O(n*n)
// 双路快速排序的partition
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int _partition2Ways(T arr[], int l, int r){
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr[l] , arr[rand()%(r-l+1)+l] );
T v = arr[l];
// arr[l+1...i) <= v; arr(j...r] >= v
int i = l+1, j = r;
while( true ){
// 注意这里的边界, arr[i] < v, 不能是arr[i] <= v
while( i <= r && arr[i] < v )
i ++;
// 注意这里的边界, arr[j] > v, 不能是arr[j] >= v
while( j >= l+1 && arr[j] > v )
j --;
/* 对于上面的两个边界的设定
a. 对于arr[i]<v和arr[j]>v的方式，第一次partition得到的分点是数组中间；
b. 对于arr[i]<=v和arr[j]>=v的方式，第一次partition得到的分点是数组的倒数第二个。
这是因为对于连续出现相等的情况，a方式会交换i和j的值；而b方式则会将连续出现的这些值归为其中一方，使得两棵子树不平衡
*/
if( i > j )
break;
swap( arr[i] , arr[j] );
i ++;
j --;
}
swap( arr[l] , arr[j]);
return j;
}
// 对arr[l...r]部分进行快速排序
template <typename T>
void _quickSort2Ways(T arr[], int l, int r){
// 对于小规模数组, 使用插入排序进行优化
if( r - l <= 15 ){
insertionSort(arr,l,r);
return;
}
// 调用双路快速排序的partition
int p = _partition2Ways(arr, l, r);
_quickSort2Ways(arr, l, p-1 );
_quickSort2Ways(arr, p+1, r);
}
template <typename T>
void quickSort2Ways(T arr[], int n){
srand(time(NULL));
_quickSort2Ways(arr, 0, n-1);
}
三路快速排序
三路快速排序对重复键值多的数组进行排序效率更高
template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
// 对于小规模数组, 使用插入排序进行优化
if( r - l <= 15 ){
insertionSort(arr,l,r);
return;
}
//partition
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr[l], arr[rand()%(r-l+1)+l ] );
T v = arr[l];
int lt = l; // arr[l+1...lt] < v
int gt = r + 1; // arr[gt...r] > v
int i = l+1; // arr[lt+1...i) == v
while( i < gt ){
if( arr[i] < v ){
swap( arr[i], arr[lt+1]);
i ++;
lt ++;
}
else if( arr[i] > v ){
swap( arr[i], arr[gt-1]);
gt --;
}
else{ // arr[i] == v
i ++;
}
}
swap( arr[l] , arr[lt] );
__quickSort3Ways(arr, l, lt-1);
__quickSort3Ways(arr, gt, r);
}
template <typename T>
void quickSort3Ways(T arr[], int n){
srand(time(NULL));
__quickSort3Ways( arr, 0, n-1);
}
归并排序和快速排序的衍生问题
在求解逆序对（如4、2就是）可以用归并排序的思想解决时间复杂度是nlogn
在求解一个数组的第n大的数可以用快排的思想解决，时间复杂度是n
另外关于希尔排序与nlogn排序算法的比较：
Shell Sort虽然慢于高级的排序方式, 但仍然是非常有竞争力的一种排序算法
其所花费的时间完全在可以容忍的范围内, 远不像O(n^2)的排序算法, 在数据量较大的时候无法忍受
同时, Shell Sort实现简单, 只使用循环的方式解决排序问题, 不需要实现递归, 不占用系统占空间, 也不依赖随机数
所以, 如果算法实现所使用的环境不利于实现复杂的排序算法, 或者在项目工程的测试阶段, 完全可以暂时使用Shell Sort来进行排序任务
