快速排序对C语言的初学者来说应该是不陌生的，在我们初学C语言时，大概率都用过一个库函数叫qsort，这个就是快排的库函数，而快排到底是如何实现的呢？本篇我会详细介绍一下快排的原理与实现。
首先，快速排序算法属于交换排序，
交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，
交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
交换排序中我们比较熟悉的就是冒泡排序，选取数组头两个值进行比较，将大的元素放在后面，然后继续向后比较，比到最后那么就一定把最大的元素放在了最后一个，因为这个把最大值通过比较向上挪动的过程就像泡泡从水底冒出的过程，所有称这种排序算法叫做冒泡排序。
而我们的重点不是冒泡排序而是快速排序，所以下面我们着重说明一下快速排序。
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
将区间按照基准值划分为左右两半部分的常见方式有：
- hoare版本
- 挖坑法
- 前后指针版本
下面我们逐个介绍这三种方法
以上的两种情况都是符合的，那么如果我们比较时让left先走，right后走，这时候就出现问题了。当right遇到left时，因为left是找大于keyi的，所以这时的left是比keyi大的，就不符合要求，所以比较时left和right的先后顺序是不可以调换的。
以上两部分就是hoare版本快速排序的全部过程，下面是整体的代码
前后指针法的基本思想是用一前一后两个指针，从左向右遍历数组，当发现有大于key值的元素时，后面的指针就停在原地，然后前面的指针继续向前遍历寻找小于key值的元素，找到以后让后面的指针向前走一步，然后交换两个指针指向的值，交换完成后前面的指针向前挪动一位，然后后面的指针就不动了，前面的指针继续向后寻找小于key值的元素，找到就交换，以此类推。
我们发现，出现这两种情况的原因是因为我们的key值选的不好，当key值是数组的中间值时，快排的效率是最高的，当我们选到最大或最小值时，导致我们进行了一次排序以后只排出来一个数，大量的增加了我们排序的次数，为了防止这种情况，我们可以使用三数取中法，即我们不再使用数组的第一个元素作为我们的key值，而是选择数组头，尾，中三个地方的三个值进行比较，去他们中间的中间值作为key，再把这个新key与第一个元素调换位置。
这样选取key值的方式虽然不能让我们一定能够选出数组的中间值作key，但是它一定避免了我们选择最大或者最小的值做key，直接就避免了最坏的情况发生。
使用三数取中优化，我们可以先写一个三数取中的函数
然后在每次排序的前面通过加上这两段代码，使得每次都使用三数取中的方法选取key值
上面的三种排序都是一直递归，然后把数组不断的分割，递归的层数太多可能就会影响效率，那么当递归到底层的时候，我们就可以通过使用别的排序方式，不使用快排来减少快排导致的递归次数。
在上面对快排的优化中我们直到，递归对排序效率的影响并没有那么大了，所以递归最致命的问题不在时间上，而在于空间。
我们每次递归都会在栈上建立栈帧，而当我们递归调用的层数太深时，有可能栈的空间不足，造成栈溢出，这时我们就只能使用一种非递归的方法进行排序了，就是循环的方法。
栈的实现我在前面的文章数据结构-栈和队列详解中有详细的介绍，并且对栈进行了实现，下面我也会直接使用这里实现的栈，有需要的同志可以去这里找到栈的实现代码。