内容

默认划分法
非递归形式
随机划分法
三位取中法
单向划分法
单链表快排（单向划分法）

原始代码

//划分函数
void Partition(int * ar, int left, int right)
{
    int tmp = ar[left];
    while(left < right)
    {
        while(left<right && ar[right]>tmp)--right;
        if(left < right) ar[left] = ar[right];
        while(left<right) && ar[left]<=tmp)++left;
        if(left < right) ar[right] = ar[left];
    }
    ar[left] = tmp;//left == right
    return left;
}
void PassQuick(int * ar, int left, int right)
{
    if(left < right)
    {
        int pos = Partition(ar, left, right);
        PassQuick(ar, left, pos-1);
        PassQuick(ar, pos+1, right);
    }
}
void QuickSort(int * ar, int n)
{
    if(ar==NULL || n<=1)return;
    PassQuick(ar, 0, n-1);
}

让函数不再任性-非递归

void Partition(int* ar, int left, int right)
{
    int tmp = ar[left];
    while(left < right)
    {
        while(left<right && br[right]>tmp)--right;
        if(left < right) br[left] = br[right];
        while(left<right) && br[left]<=tmp)++left;
        if(left < right) br[right] = br[left];
    }
    br[left] = tmp;//left == right
    return left;
}
void QuickSort(int* ar, int n)
{
    if(ar==NULL || n<=1)return;
    queue<int> qu;
    qu.push(0);
    qu.push(n - 1);
    while(!qu.empty())
    {
        int left = qu.front(); qu.pop();
        int right = qu.front();qu.pop();
        int pos = Partition(ar, left, right);
        if(left < pos-1)
        {
            qu.push(left);
            qu.push(pos-1);
        }
        if(pos+1 < right)
        {
            qu.push(pos+1);
            qu.push(right);
        }
    }
}

使用别名之后, 程序更为简洁;

void QuickSort(int * ar, int n)
{
    if(ar==NULL || n<=1)return;
    using Pair = std::pair<int,int>;
    queue<Pair> qu;
    qu.push(Pair(0, n-1));
    while(!qu.empty())
    {
        Pair pos = qu.front();qu.pop();
        int mid = Partition(ar, pos.first, pos.second);
        if(pos.first < mid-1)
            qu.push(Pair(pos.first, mid-1));
        if(mid+1 > pos.second)
            qu.push(Pair(mid+1, pos.second));
    }
}

从“选取划分基准”入手优化

随机划分

这样做是为了让划分点无序, 以模拟数据的无序性, 防止数据有序情况下快排性能的退化;

实现方法: 在Partition之外再封装一层随机选取一个位置, 把这个位置与ar[left]值交换, 然后再调用Partition; 这样的好处就是, 不用修改Partition函数;

int RandPartition(int * ar, int left, int right)
{
    srand(time(NULL));
    int pos = rand() % (right-left+1) + left;//记得取模后+left，不加left是相对位置。
    std::swap(ar[left], ar[pos]);		//偷梁换柱
    return Partiton(ar, left, right);
}

三位取中法

int MidPartition(int* ar, int left, int right)
{
    int midpos = (right - left)/2 + left;
    struct IndexNode
    {
        int key;
        int index;
        operator int() const {return key;}
    };
    struct IndexNode kL = {ar[left], left};
    struct IndexNode kM = {ar[midpos], midpos};
    struct IndexNode kR = {ar[right],right};
	std::priority_queue<IndexNode> hp;
    //kL,kM,kR入堆时，由于IndexNode类型重载了int()强转运算符，所以入堆按其key大小排序。则堆中第二个元素为key第二小的。
    hp.push(kL); hp.push(kM); hp.push(kR);
    hp.pop();
    struct IndexNode pos = hp.top();
    std::swap(ar[kL.index], ar[pos.index]);	//偷梁换柱
    return Partition(ar, left, right);
}

应对特殊数据结构-单向划分

可以处理单链表场景下的快排。

先拿数组练。

int ForwardPartition(int * ar, int left, int right)
{
    int j = left - 1;//慢指针
    int i = left;    //快指针
    int tmp = ar[i];
    while(i <= right)
    {
        if(ar[i] <= tmp)
        {
            ++j;
            swap(ar[j],ar[i]);
        }
        ++i;
    }
    swap(ar[left], ar[j]);  //单向划分，以left为基准，过程中要保证left值不会变化。最后，找到j的位置(划分之后的中间位置)后，替换，返回。
    return j;
}

单链表的划分（带头节点）

typedef int ElemType;
typedef struct ListNode
{
    ElemType data;
    struct ListNode* next;
}ListNode, *LinkList;
//head表示这个划分区间的第一个有效节点的前一个；end表示这个划分区间最后一个有效节点的后一个（有可能为NULL）。
void ForwoadListPartition(ListNode* head,ListNode *end)
{
    ListNode* j = head;
    ListNode* i = head->next;
    ElemType tmp = i->data;
    while(i != end)
    {
        if(i->data <= tmp)
        {
            j = j->next;
            swap(j->data, i->data);
        }
        i = i->next;
    }
    swap(head->next->data, j->data);
    //不再像数组那样，不用对中间位置进行mid-1,mid+1。因为此时的head,end已代表不同意义，j正好可以充当-1和+1。
    ForwoadListPartition(head, j);
    ForwoadListPartition(j, end);
}

适用分治策略-“划分”思想的场景

找到第K小/大数

不能有重复值。

int FindK(int * ar, int left, int right, int k)//k是相对位置
{
    if(left==right && k==1)return ar[left];
    int pos = Partition(ar, left, right);	//返回的pos是绝对下标
    int j = pos - left + 1;					//j和k一样，是相对left的位置
    if(k<=j)return FindK(ar, left, pos, k);	 //当k还在j之左时，在left~pos继续划分寻找第k小
    else return Findk(ar, pos+1, right, k-j);//当k在j之右时，在pos+1~right寻找第k-j小，因为换到右边时，"k"的值发生变化。
}
int FindK_Min(int * ar, int n, int k)//第k小
{
    if(ar==NULL || k<0 || k>n)return -1;
    return FindK(ar, 0, n-1, k);
}

无序数组中找两个差值最小

非负数。

即找最接近点对，以一维为例。

int FindK_Min(int * ar, int n, int k)
{
    if(ar==NULL || k<0 || k>n)return -1;
    return FindK(ar, 0, n-1, k);
}
int MaxS1(const int* ar, int left, int right)
{
    return ar[right];
}
int MinS2(const int* ar, int left, int right)
{
    int min = ar[left];
    for(int i = left + 1; i<=right; ++i)
    {
        if(min > ar[i])
        {
            min = ar[i];
        }
    }
    return min;
}
int Min(int a, int b)
{
    return a < b ? a : b;
}
int Min(int a, int b, int c)
{
    return Min(a, Min(b, c));
}
int Cpair(int * ar, int left, int right)
{
    if((right-left) <= 0) return INT_MAX;
    int mid = (right-left+1)/2;
    FindK(ar, left, right, mid);//mid为相对位置，正好是s1中最大的。
    int pos = left + mid - 1;//pos为绝对下标。
    int d1 = Cpair(ar, left, pos);	//在左部分找到点对的最小差值
    int d2 = Cpair(ar, pos+1,right);//在右部分找到点对的最小差值
    int maxs = MaxS1(ar, left, pos);
    int mins = MinS2(ar, pos+1, right);
    return Min(d1, d2, mins-maxs);
}
int Cpair_Ar(int * ar, int n)
{
    if(ar==NULL || n<1)return INT_MAX;
    else return Cpair(ar, 0, n-1);
}

不同场景下的对策

数组相对有序：随机划分法。在每次划分之前在left和right之前rand计算一个pos，使该值与left对应的值交换，进而以其为基准进行划分。