0.x 10.快速排序

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

优化快速排序（递归到底使用插入排序）

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <typeinfo>
#include <numeric>
#include <memory>
#include <stdexcept>
#include <fstream> 
#include <sstream>
using namespace std;
//win+<-/-> 切换窗口位置
//ctrl+win+<-/->切换桌面 
//ctrl+alt+上/下 改变显示器方向 
template <typename T>
int __partition(T arr[], int l, int r){
    T v = arr[l];
    int j = l + 1; // arr[l+1...j) < v ; arr[j...i) >= v
    for( int i = l + 1 ; i != r ; i ++ )
        if( arr[i] < v ){
            swap( arr[j++] , arr[i] );
        }
    swap( arr[l] , arr[--j]);//轴值要与j左边的那个<v的元素交换
    //返回轴值的位置
    return j;
}
// 对arr[l...r]部分进行快速排序
template <typename T>
void __quickSort(T arr[], int l, int r){
    if( l >= r-1 )  //这里递归到底可以使用直接插入排序
        return;
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p );
    __quickSort(arr, p+1, r);
}
template <typename T>
void quickSort(T arr[], int n){
    __quickSort(arr, 0, n);
}
int main() {
    int a[20] = {120,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,4,3,2,1};
    quickSort(a,20);
    for( int i = 0 ; i < 20 ; ++i )
        cout<<a[i]<<ends;
    cout<<endl;
    return 0;
}

随机化快速排序（正序或者逆序）

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <typeinfo>
#include <numeric>
#include <memory>
#include <stdexcept>
#include <fstream> 
#include <sstream>
#include <random>
using namespace std;
//win+<-/-> 切换窗口位置
//ctrl+win+<-/->切换桌面 
//ctrl+alt+上/下 改变显示器方向 
template <typename T>
int __partition(T arr[], int l, int r){
    static default_random_engine e;
    //分布类型不能用static，因为每次调用的时候都需要修改l和r-1
    uniform_int_distribution<unsigned> u(l,r-1);//C++的随机数引擎
    swap(arr[l], arr[u(e)]);
    T v = arr[l];
    int j = l + 1; // arr[l+1...j) < v ; arr[j...i) >= v
    for( int i = l + 1 ; i != r ; ++i )
        if( arr[i] < v ){
            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( l >= r-1 )
        return;
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p );
    __quickSort(arr, p+1, r);
}
template <typename T>
void quickSort(T arr[], int n){
    __quickSort(arr, 0, n);
}
int main() {
    int a[20] = {120,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,4,3,2,1};
    quickSort(a,20);
    for( int i = 0 ; i < 20 ; ++i)
        cout<<a[i]<<ends;
    cout<<endl;
    return 0;
}

二路快排（大量重复元素）

略，意义不大，性能不及三路。

三路快排（大量重复，比二路更强）

template <typename T>
pair<int,int> __partition(T arr[], int l, int r)
{
    T v = arr[l];
    int lt = l + 1;     // arr[l+1...lt) < v
    int gt = r; // 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++]);
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[--gt]);
        }
        else{ // arr[i] == v
            ++i;
        }
    }
    swap( arr[l] , arr[--lt] );
    return {lt,gt};
}
// 递归的三路快速排序算法
template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
    if( l >= r-1 ) //一定要考虑到r==l的情况也可能发生，直接return
        return;
    auto p = __partition(arr, l, r);
    __quickSort3Ways(arr, l, p.first);
    __quickSort3Ways(arr, p.second, r);
}
template <typename T>
void quickSort3Ways(T arr[], int n){
    __quickSort3Ways( arr, 0, n);
}
int main() {
    int a[20] = {120,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,4,3,2,1};
    quickSort3Ways(a,20);
    for( int i = 0 ; i < 20 ; ++i )
        cout<<a[i]<<ends;
    cout<<endl;
    return 0;
}

终极版本（优化的三路随机快排）

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>
#include <typeinfo>
#include <numeric>
#include <memory>
#include <stdexcept>
#include <fstream> 
#include <utility>
#include <sstream>
#include <random>
using namespace std;
//win+<-/-> 切换窗口位置
//ctrl+win+<-/->切换桌面 
//ctrl+alt+上/下 改变显示器方向 
template <typename T>
pair<int,int> __partition(T arr[], int l, int r)
{
    static default_random_engine e;
    uniform_int_distribution<unsigned> u(l,r-1);//C++的随机数引擎
    swap(arr[l], arr[u(e)]);
    T v = arr[l];
    int lt = l + 1;     // arr[l+1...lt) < v
    int gt = r; // 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++]);
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[--gt]);
        }
        else{ // arr[i] == v
            ++i;
        }
    }
    swap( arr[l] , arr[--lt] );
    return {lt,gt};
}
// 递归的三路快速排序算法
template <typename T>
void __quickSort3Ways(T arr[], int l, int r){
    // 对于小规模数组, 可以使用插入排序进行优化
    //if( r-l <= 1) return;
    if(r - l <= 10)//少于10个数
    {
        if(l == r) return;//0个元素 
        for(int i = l + 1; i != r; ++i)
        {
            int temp = arr[i];
            int j = 0;//初始化 
            for(j = i; j != l && temp < arr[j - 1]; --j)
            {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
        return;
    }
    auto p = __partition(arr, l, r);
    __quickSort3Ways(arr, l, p.first);
    __quickSort3Ways(arr, p.second, r);
}
template <typename T>
void quickSort3Ways(T arr[], int n){
    __quickSort3Ways( arr, 0, n);
}
int main() {
    int a[40] = {120,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,4,3,2,1,120,9,8,7,6,5,4,3,2,1,10,9,8,7,6,5,4,3,2,1};
    quickSort3Ways(a,40);
    for( int i = 0 ; i < 40 ; ++i )
        cout<<a[i]<<ends;
    cout<<endl;
    return 0;
}