<code>生活的本质是什么呢? 无非就是你要什么就不给你什么. 而生活的智慧是什么呢? 是给你什么就用好什么. ---马斯克

索引

一. 前言二. 快速排序的概念三. 快速排序的实现1. hoare2. 挖坑法3. 前后指针法

总结

正文开始

一. 前言

接上文, 前面我们了解了插入排序, 与优化版本希尔排序, 那么本篇博客将详细介绍另外一种排序, 快速排序.

博客主页: 酷酷学!!!

感谢关注~

二. 快速排序的概念

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，

其基本思想为：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

三. 快速排序的实现

将区间按照基准值划分为左右两半部分的常见方式有三种版本

1. hoare

如图所示, 排序的思想为

第一步:

两个下标, 一个从后往前走, 一个从前往后走, 然后定义一个基准值key, 下表为keyi,这里要注意要保证end先走, 才能让最后相遇的位置小于keyi的位置, 因为end先走无非就两种情况, 第一种, end找到了比key小的值, 停下来, 最后一次begin相遇end,交换相遇结点与key结点, 第二种情况, end相遇begin, 此时end没有找到比keyi小的值, 然后最后一次与begin相遇, 此时begin的值为上一次交换后的值, 所以比keyi小.然后相遇与keyi交换位置, 此时6这个位置就排好了

第二步:

因为6这个位置排好了, 所以进行下一次的排序,以6划分为两个区域,然后再次递归调用函数, 如果最后的区间不存在或者只有一个值那么就结束函数.当left==right时此时区间只有一个值就不需要排序, 区间不存在也不需要排序.

<code>void QuickSort(int* a, int left, int right)

{

if (left >= right)

{

return;

}

int keyi = left;

int begin = left,end = right;

while (begin < end)

{

while (begin < end && a[end] >= a[keyi])

{

end--;

}

while (begin < end && a[begin] <= a[keyi])

{

begin++;

}

Swap(&a[begin], &a[end]);

}

Swap(&a[begin], &a[keyi]);

keyi = begin;

QuickSort(a, left, keyi - 1);

QuickSort(a, keyi + 1, right);

}

我们来分析一下快速排序的时间复杂度, 目前来看, 每一层的时间复杂度为O(N), 高度为logn, 所以时间复杂度为O(NlogN), 但是这是在较好的情况下, 也就是相当于二叉树, 左右区间差不多大, 那么如果是有序的一系列数字, 那么这个排序就很不友好, 很容易栈溢出,递归层次很深, 就不是logn, 那么如何进行优化呢, 就需要我们修改它的key值, 不大不小为最好的情况, 为了避免有序情况下，效率退化, 可以选择 随机选key法 或者 三数取中法

这里我们来介绍一下三数取中法的优化.

<code>int GetMidi(int* a, int left, int right)

{

int midi = (right - left) / 2;

if (a[left] < a[midi])

{

if (a[midi] < a[right])

{

return midi;

}

else if(a[left] < a[right])

{

return right;

}

else

{

return left;

}

}

else//a[left] > a[midi]

{

if (a[left] < a[right])

{

return left;

}

else if (a[midi] > a[right])

{

return midi;

}

else

{

return right;

}

}

}

我们可以定义一个函数, 然后选取区间内最左边的值, 最右边的值, 中间的值,那个不大又不小的值作为key, 利用上述函数, 我们的代码可以改写为

void QuickSort(int* a, int left, int right)

{

if (left >= right)

{

return;

}

//三数取中

int midi = GetMidi(a, left, right);

Swap(&a[left], &a[midi]);

int keyi = left;

int begin = left,end = right;

while (begin < end)

{

while (begin < end && a[end] >= a[keyi])

{

end--;

}

while (begin < end && a[begin] <= a[keyi])

{

begin++;

}

Swap(&a[begin], &a[end]);

}

Swap(&a[begin], &a[keyi]);

keyi = begin;

QuickSort(a, left, keyi - 1);

QuickSort(a, keyi + 1, right);

}

有了上述的优化, 我们的代码效率就算在有序的情况下也能大大的提升效率, 但是还有一个问题, 我们知道, 二叉树中递归调用, 最后一层递归调用的次数占据了总调用次数的一半, 我们可以把最后几层的递归调用优化掉, 如果区间为十个数那么我们选择其他的排序方法, 如果选堆排序, 十个数还需要建堆比较麻烦, 如果使用希尔排序, 那么就是多此一举, 数据量不大选择希尔排序属实有点浪费了, 那我们就在时间复杂度为O(N^2)的排序中选择一个相对来说效率比较高的插入排序.优化后的代码如下:

void QuickSort(int* a, int left, int right)

{

if (left >= right)

{

return;

}

if ((right - left + 1) < 10)

{

InsertSort(a + left, right - left + 1);

}

else

{

//三数取中

int midi = GetMidi(a, left, right);

Swap(&a[left], &a[midi]);

int keyi = left;

int begin = left, end = right;

while (begin < end)

{

while (begin < end && a[end] >= a[keyi])

{

end--;

}

while (begin < end && a[begin] <= a[keyi])

{

begin++;

}

Swap(&a[begin], &a[end]);

}

Swap(&a[begin], &a[keyi]);

keyi = begin;

QuickSort(a, left, keyi - 1);

QuickSort(a, keyi + 1, right);

}

}

此优化在release版本下较为突出.

2. 挖坑法

前面单趟排序的方法由hoare发明之后又有另外的一种排序方法, 挖坑法, 它的思路比hoare排序的思想更容易理解

<code>//挖坑法

int PartSort3(int* a, int left, int right)

{

//三数取中

int midi = GetMidi(a, left, right);

Swap(&a[left], &a[midi]);

int keyi = left;

int begin = left, end = right;

int tmp = a[keyi];

while (begin < end)

{

while (begin < end && a[end] >= a[keyi])

{

end--;

}

a[keyi] = a[end];

keyi = end;

while (begin < end && a[begin] <= a[end])

{

begin++;

}

a[keyi] = a[begin];

keyi = begin;

}

a[keyi] = tmp;

return keyi;

}

void QuickSort(int* a, int left, int right)

{

if (left >= right)

{

return;

}

if (right - left + 1 < 10)

{

InsertSort(a + left, right - left + 1);

}

int keyi = PartSort3(a,left,right);

QuickSort(a, left, keyi - 1);

QuickSort(a, keyi + 1, right);

}

我们可以直接把单趟排序的算法拿出来封装成一个函数, 如图所示挖坑法特别好理解, 先让keyi的值存放在一个临时变量中, 挖一个坑,先让对面的先走, 如果遇到比end小的就把它拿出来填入坑中, 然后begin在开始走, 遇到大的填入坑中, 这样依次轮换,相遇时将keyi的值填入坑中.

3. 前后指针法

如图所示, 初始时, prev指针指向序列开头, cur指针指向prev指针的后一个位置, 然后判断cur指针指向的数据是否小于key, 则prev指针后移一位, 并于cur指针指向的内容交换, 然后cur++,cur指针指向的数据仍然小于key,步骤相同, 如果cur指针指向的数据大于key, 则继续++,最后如果cur指针已经越界, 这时我们将prev指向的内容与key进行交换.

可以看到也就是一个不断轮换的过程, 将大的数依次往后翻转, 小的数往前挪动, 这种方法代码写起来简洁, 当然我们也可以优化一下, 让cur和prev相等时就没必要进行交换

<code>//前后指针版

int PartSort2(int* a, int left, int right)

{

//三数取中

int midi = GetMidi(a, left, right);

Swap(&a[left], &a[midi]);

int keyi = left;

int prev = left;

int cur = prev + 1;

while (cur <= right)

{

if (a[cur] < a[keyi] && prev++ != cur)

{

Swap(&a[cur], &a[prev]);

}

cur++;

}

Swap(&a[prev], &a[keyi]);

return prev;

}

void QuickSort(int* a, int left, int right)

{

if (left >= right)

{

return;

}

if (right - left + 1 < 10)

{

InsertSort(a + left, right - left + 1);

}

int keyi = PartSort2(a,left,right);

QuickSort(a, left, keyi - 1);

QuickSort(a, keyi + 1, right);

}

以上是递归版本的实现, 那么我们知道, 递归层次太深会容易栈溢出, 那么能不能采用非递归的实现呢, 答案肯定是可以的, 我们可以使用栈这个数据结果, 然后将区间入栈中, 栈不为空循环对区间进行排序, 一般linux系统下函数栈帧的空间的大小为8M, 而堆空间大小为2G, 所以这个空间是非常大的, 而且栈也是动态开辟的空间, 在堆区申请, 所以几乎不需要考虑空间不够, 我们可以将区间压栈, 先压入右区间, 在压入左区间, 然后排序的时候先排完左区间再排右区间, 这是一种深度优先算法(DFS), 当然也可以创建队列, 那么走的就是一层一层的排序, 每一层的左右区间都排序, 是一种广度优先算法(BFS).

代码实现:

这里可以创建一个结构体变量存放区间, 也可以直接压入两次, 分别把左值和右值压入

//非递归版

#include"stack.h"

void QuickSortNonR(int* a, int left, int right)

{

ST st;

STInit(&st);

STPush(&st, right);

STPush(&st, left);

while (!STEmpty(&st))

{

int begin = STTop(&st);

STPop(&st);

int end = STTop(&st);

STPop(&st);

int keyi = PartSort1(a, begin, end);

//[begin,keyi-1] keyi [keyi+1,end]

//先压入右区间

if (keyi + 1 < end)

{

STPush(&st, end);

STPush(&st, keyi + 1);

}

if (begin < keyi - 1)

{

STPush(&st, keyi - 1);

STPush(&st, begin);

}

}

Destroy(&st);

}

总结

快速排序是一种常用的排序算法，其时间复杂度为O(nlogn)。它的基本思想是通过一趟排序将待排序序列分割成独立的两部分，其中一部分的所有元素都比另一部分的所有元素小，然后再对这两部分分别进行排序，最终得到一个有序序列。

完

期待支持, 感谢关注~