快速排序的一种优化算法（三向切分）

1万 · 2018-6-4 15:33

快速排序：

时间复杂度O(N*logN)，最坏情况为O(N^2)

空间复杂度O(1)

但是堆栈深度一般情况为O(logN)，最坏情况为O(N)

快速排序实现：

partition划分算法：

int Partition(SeqList R，int i，int j)

{

    //调用Partition(R，low，high)时，对R[low..high]做划分，

    //并返回基准记录的位置

    ReceType pivot=R[i]； //用区间的第1个记录作为基准 '

    while(i<j){ //从区间两端交替向中间扫描，直至i=j为止

        while(i<j&&R[j].key>=pivot.key) //pivot相当于在位置i上

            j--； //从右向左扫描，查找第1个关键字小于pivot.key的记录R[j]

        if(i<j) //表示找到的R[j]的关键字<pivot.key

            R[i++]=R[j]； //相当于交换R[i]和R[j]，交换后i指针加1

        while(i<j&&R[i].key<=pivot.key) //pivot相当于在位置j上

            i++； //从左向右扫描，查找第1个关键字大于pivot.key的记录R[i]

        if(i<j) //表示找到了R[i]，使R[i].key>pivot.key

            R[j--]=R[i]; //相当于交换R[i]和R[j]，交换后j指针减1

    } //endwhile

    R[i]=pivot； //基准记录已被最后定位

    return i；

} //partition

1万 · 2018-6-4 15:34

然后，对整个数组进行递归排序：

复制

QUICKSORT(A, p, r)

    if p < r

        then q ← PARTITION(A, p, r)   //关键

    QUICKSORT(A, p, q - 1)

    QUICKSORT(A, q + 1, r)

算法导论中提到的快速排序的优化版本：就地重排

复制

PARTITION(A, p, r)

    x ← A[r]         //以最后一个元素，A[r]为主元

    i ← p - 1

    for j ← p to r - 1    //注，j从p指向的是r-1，不是r。

        do if A[j] ≤ x

            then i ← i + 1

            exchange A[i] <-> A[j]

    exchange A[i + 1] <-> A[r]

    return i + 1

1万 · 2018-6-4 15:34

本文重点：三向切分

快速排序什么时候不适用？元素重复率特别高的时候。
如何优化？三向切分。前后各俩指针，总共四个指针。俩额外的指针指向跟待选元素相同的元素，最后全部置换到中间。
三向切分的好处？重复率高的时候，避免相同元素来回交换，节省交换次数。对于包含大量重复元素的数组，这个算法将排序时间从线性对数级降到了线性级别。

1万 · 2018-6-4 15:35

代码：

复制

#include <iostream>  

using namespace std;  

template <typename T>  

void sawp(T a[],int first,int second){  

    T temp;  

    temp = a[first];  

    a[first] = a[second];  

    a[second] = temp;  

}  

template <typename T>  

int sort(T a[],int low,int high){  

    if(low < high){  

        int lt = low,i=low+1,gt = high;  

        int temp = a[low];  

        while(i <= gt){  

            if(a[i] < temp){  

                sawp(a,lt++,i++);  

            }else if(a[i] > temp){  

                sawp(a,i,gt--);  

            }else{  

                i++;  

            }  

        }  

        sort(a,low,lt-1);  

        sort(a,gt+1,high);  

    }   

}  

int main() {  

    int a[] = {2,2,2,2,2,0,0,0,0,0,0,1,5};  

    //int a[] = {2,0,1,5};  

    int len = sizeof(a)/sizeof(int);  

    sort(a,0,len-1);  

    for (int i = 0; i < len; ++i)  

        cout << a[i] << " ";  

    cout << endl;  

}

1万 · 2018-6-4 15:35

代码：

复制

#include <iostream>  

using namespace std;  

template <typename T>  

void sawp(T a[],int first,int second){  

    T temp;  

    temp = a[first];  

    a[first] = a[second];  

    a[second] = temp;  

}  

template <typename T>  

int sort(T a[],int low,int high){  

    if(low < high){  

        int lt = low,i=low+1,gt = high;  

        int temp = a[low];  

        while(i <= gt){  

            if(a[i] < temp){  

                sawp(a,lt++,i++);  

            }else if(a[i] > temp){  

                sawp(a,i,gt--);  

            }else{  

                i++;  

            }  

        }  

        sort(a,low,lt-1);  

        sort(a,gt+1,high);  

    }   

}  

int main() {  

    int a[] = {2,2,2,2,2,0,0,0,0,0,0,1,5};  

    //int a[] = {2,0,1,5};  

    int len = sizeof(a)/sizeof(int);  

    sort(a,0,len-1);  

    for (int i = 0; i < len; ++i)  

        cout << a[i] << " ";  

    cout << endl;  

}

1万 · 2018-6-4 15:35

代码：

复制

#include <iostream>  

using namespace std;  

template <typename T>  

void sawp(T a[],int first,int second){  

    T temp;  

    temp = a[first];  

    a[first] = a[second];  

    a[second] = temp;  

}  

template <typename T>  

int sort(T a[],int low,int high){  

    if(low < high){  

        int lt = low,i=low+1,gt = high;  

        int temp = a[low];  

        while(i <= gt){  

            if(a[i] < temp){  

                sawp(a,lt++,i++);  

            }else if(a[i] > temp){  

                sawp(a,i,gt--);  

            }else{  

                i++;  

            }  

        }  

        sort(a,low,lt-1);  

        sort(a,gt+1,high);  

    }   

}  

int main() {  

    int a[] = {2,2,2,2,2,0,0,0,0,0,0,1,5};  

    //int a[] = {2,0,1,5};  

    int len = sizeof(a)/sizeof(int);  

    sort(a,0,len-1);  

    for (int i = 0; i < len; ++i)  

        cout << a[i] << " ";  

    cout << endl;  

}

1万 · 2018-6-4 15:35

代码：

复制

#include <iostream>  

using namespace std;  

template <typename T>  

void sawp(T a[],int first,int second){  

    T temp;  

    temp = a[first];  

    a[first] = a[second];  

    a[second] = temp;  

}  

template <typename T>  

int sort(T a[],int low,int high){  

    if(low < high){  

        int lt = low,i=low+1,gt = high;  

        int temp = a[low];  

        while(i <= gt){  

            if(a[i] < temp){  

                sawp(a,lt++,i++);  

            }else if(a[i] > temp){  

                sawp(a,i,gt--);  

            }else{  

                i++;  

            }  

        }  

        sort(a,low,lt-1);  

        sort(a,gt+1,high);  

    }   

}  

int main() {  

    int a[] = {2,2,2,2,2,0,0,0,0,0,0,1,5};  

    //int a[] = {2,0,1,5};  

    int len = sizeof(a)/sizeof(int);  

    sort(a,0,len-1);  

    for (int i = 0; i < len; ++i)  

        cout << a[i] << " ";  

    cout << endl;  

}

只看该作者 · 2018-6-4 19:48

多谢分享，这个以前没有好好学习，学习下这个思想。