快速排序是交换排序的一种，这是因为快速排序的核心还是交换两个合适的元素。快排有很多实现方法，类似更新迭代，但是核心思想都一样。Hoare法，挖坑法，前后指针法，非递归法（栈实现，队列实现）  下面一一介绍。

目录

快速排序，Hoare版本：

快速排序，挖坑法：

快速排序，前后指针法，带三数取中等优化：

快速排序非递归（栈实现）

快速排序非递归（队列实现）

---

快速排序，Hoare版本：

Hoare 左闭右闭

void QuickSort(int* arr, int begin, int end) {  // [begin, end]    int left = begin;    int right = end;    int keyi = begin;  // 设置下标是因为后面要交换数据    while(left < right) {        // 右边找小        while(left < right && arr[right] >= arr[keyi]) {            right--;        }        // 左边找大        while(left < right && arr[left] <= arr[keyi]) {            left++;        }        // 这里不管是否left<right都交换，等于也无妨。        swap(arr[left], arr[right]);    }    // 这里出循环之后，一定符合left == right。    swap(arr[keyi],arr[left]);    // [begin, left-1] left [left+1, end]    if(left-1>begin)        QuickSort(arr,begin,left-1);    if(left+1<end)        QuickSort(arr,left+1,end);}

单趟排序目的：找一个key下标的值，单趟排序结束后key的左边比它小，右边比它大，这样为一次单趟排序。

这里暂时先不使用三数取中的优化，先找一个key值（一般为最左边或最右边），这里默认为left下标处的值。然后定义left，right。右边找小于key的值，左边找大于key的值，且必须是right先走。（这里有原因，后序解答）。当右边找到小，左边找到大，交换左右下标的值，使得大值去右边，小值去左边。当left和right相遇之后循环退出，再交换key下标的值，和相遇处的值（这里取left和right都可以） 至此，单趟排序结束。

细节1：右边一定要找小于key的值，左边一定要找大于key的值，也就是while循环中必须为arr[right]>=arr[key]。不可以为arr[right] > arr[key]  为了防止如下情况：5 5 1 2 3 4 5 这样就会陷入死循环。

细节2：每个循环都要写left<right这个条件。而不管在任何一个循环处达到了left=right  都可以正常停下，while里的swap也只是没有意义的交换，然后退出大的while。

为什么key在左边必须右边先走？举例所有情况，你会发现，只有右边先走才可以达成相遇处的值<= arr[key]  情况1：右边去遇到左边：此时left或者为初始的key下标。或者是上一次left right交换之后的left。初始的key说明key右边的所有值都大于等于key下标的值，相遇之后相当于自己交换。而上一次交换之后的left一定小于key。   所以综上情况1的两种可能，都可以达到相遇处的值小于等于arr[key]（事实上可能性1的概率很小）  这样交换之后才可以保证key左边的值小于它，右边的值大于他。（左边做key右边先走，右边做key左边先走）

单趟排序结束后，进行递归，这里类似于二叉树的前序遍历：对根节点进行处理，然后递归左子树，左子树递归完递归右子树。而这里是递归左区间，然后递归右区间。当左右区间都有序了，整体也就有序了。

不过要注意，这里是递归左区间，然后左区间的左区间，无限递归下去，当某一次左区间的元素个数<=1 时，停止递归，再递归右区间。可以想象二叉树的前序遍历。

注意QuickSort的left和right  是左闭右闭形式的。也就使得，单趟排序之后，整个区间被划分为了        [begin, left-1] left [left+1, end]  也就得出了递归的条件： left-1 > begin   left+1 < end。左闭右开的话情况类似，需要改变右递归条件为 left+1 < end-1 注意这里的left的值是交换之后的最初的key的值。你也可以把left赋值给key  key = left  然后用key去划分这个区间。

讲的有点过于详细了。。。。。 

快速排序性能总结：

时间复杂度：O(N*LogN)

空间复杂度：O(LogN)

稳定性：不稳定。

Hoare 左闭右开：

void QuickSort(int* arr, int begin, int end) {  // [begin, end)    // 对数组arr的begin到end下标的元素进行排序    // 先进行单趟排序    int left = begin;;    int right = end-1;    int keyIndex = left;    while(left < right) {        while(left < right && arr[right] <= arr[keyIndex]) {            right--;        }        while(left < right && arr[left] >= arr[keyIndex]) {            left++;        }        // 这里可能相遇了，可能没相遇。即使相遇了交换也不影响        swap(arr[left], arr[right]);    }    swap(arr[keyIndex], arr[left]);    keyIndex = left;    // 保证左面至少有两个元素才进行递归。    if(keyIndex-1 > begin)        QuickSort(arr,begin,keyIndex);    // 保证右面至少有两个元素才进行递归。    if(left+1<end-1)        QuickSort(arr,keyIndex+1,end);}

改变的仅仅是right的取值还有右递归的条件。 

快速排序，挖坑法：

void QuickSort(int* arr,int begin, int end) { // [begin, end]    int left = begin, right = end;  // left和right为范围，因为最后还要使用begin和end进行递归。    int key = arr[left];  // arr[begin] 保存元素值而不是下标是因为left下标的值会被改变。单趟排序的最后要把这个元素值放入最后一个坑中。    while(left < right) {        // 右边找小，填入坑中        while(left < right && arr[right] >= key) {            right--;        }        // 这里left right是否相遇都无所谓。相遇就是自赋值，不相遇正和目的。        arr[left] = arr[right];        // 左边找大， 填入坑中        while(left < right && arr[left] <= key) {            left++;        }        // 这里left right是否相遇都无所谓。相遇就是自赋值，不相遇正和目的。        arr[right] = arr[left];    }    arr[left] = key; // 这个时候其实left right都是一样的。    // 下面的left就是最终的key值所在位置。    if(left-1>begin)        QuickSort(arr,begin,left-1);    if(left+1<end)        QuickSort(arr,left+1,end);}

这里的key是左下标的值，而不是左下标。因为这里的值会被覆盖。

总结：右边找小，填入左边，左边找大，填入右边。相遇之后，将相遇点的值改为key。然后递归

快速排序，前后指针法，带三数取中等优化：

int GetMiddleIndex(int* arr, int begin, int end) { // 注意，写的是左闭右闭的版本 [begin,end]    int mid = (begin+end)/2;    if(arr[begin] < arr[end]) {        if(arr[mid] < arr[begin]) {            return begin;        }else if(arr[end] < arr[mid]) {            return end;        }else {            return mid;        }    }else {        if(arr[begin] < arr[mid]) {            return begin;        }else if(arr[end] > arr[mid]) {            return end;        }else {            return mid;        }    }}// 前后指针法void QuickSort(int* arr, int begin, int end) {  // [begin, end]    if(end - begin > 12) {        int prev = begin;        int cur = begin + 1;        // 三数取中        int mid = GetMiddleIndex(arr, begin, end);        swap(arr[mid], arr[begin]);        // 三数取中结束        int keyIndex = begin; // 这里保存下标而不是元素值，是因为最后要进行一次交换操作。        while (cur <= end) {            // 前方为真才++prev。//            if (arr[cur] < arr[keyIndex] && ++prev != cur) {//                swap(arr[prev], arr[cur]);//            }            if(arr[cur] < arr[keyIndex]) {                ++prev;                swap(arr[cur], arr[prev]);            }            // 小于key值，就处理。处理完移动cur            // 不小于key值，直接移动cur。            ++cur;        }        swap(arr[keyIndex], arr[prev]);        // 此时prev就是那个分割线，并且这是一种前闭后开的形式        if (prev - 1 > begin) {            QuickSort(arr, begin, prev-1);        }        if (prev + 1 < end) {            QuickSort(arr, prev + 1, end);        }    }else {        InsertSort(arr+begin, end-begin+1);    }}

 直接看if条件里面的即可。

cur一直往前走，遇到小于keyIndex下标的值，则停下处理。循环结束后交换prev和keyIndex下标处的值。

上方为单趟排序，之后进行前序递归即可。

快速排序非递归（栈实现）

// 快排改非递归用循环很难，可以在堆上创建数据结构：栈 来模拟递归过程。(因为堆很大void QuickSortNoRecursionStack(int* arr, int begin, int end)  // recursion  [begin, end]{    stack<int> st;    st.push(end);    st.push(begin);    while(!st.empty()) {        int left = st.top();        st.pop();        int right = st.top();        st.pop();        // 这里就是一个全新的范围，进行单趟排序即可。        int prev = left;        int cur = left+1;        int mid = GetMiddleIndex(arr,left,right);        swap(arr[left], arr[mid]);        int keyIndex = left;        while(cur <= right) {            if(arr[cur] < arr[keyIndex] && ++prev != cur) {                swap(arr[prev], arr[cur]);            }            cur++;        }        swap(arr[keyIndex], arr[prev]);        // 单趟排序结束        // [begin, prev-1] prev [prev+1, end]        if(prev+1 < right) {            st.push(right);            st.push(prev+1);        }        if(prev-1 > left) {            st.push(prev-1);            st.push(left);        }    }}

其实非常简单，只需要每次确定好left和right的范围即可。确定好之后进行单趟排序。

之后按顺序压栈right prev+1  prev-1 left  然后出栈时，即可完全模拟递归的前序递归。其实先压左边的范围，后压右边也可以。只是递归的顺序改变了。此处的单趟排序用Hoare 挖坑 快慢指针方法之一即可，都可以。  

注意后面压栈时，使用的是left right  而不是begin end。因为每次单趟排序之后，整体的范围是left right 而不是 begin end

快速排序非递归（队列实现）

void QuickSortNoRecursionQueue(int* arr, int begin, int end) {    queue<int> q;    q.push(begin);    q.push(end);    while(!q.empty()) {        int left = q.front();        q.pop();        int right = q.front();        q.pop();        int prev = left;        int cur = left+1;        int mid = GetMiddleIndex(arr,left,right);        swap(arr[left], arr[mid]);        int keyIndex = left;        while(cur <= right) {            if(arr[cur] < arr[keyIndex] && ++prev != cur) {                swap(arr[prev], arr[cur]);            }            ++cur;        }        swap(arr[keyIndex], arr[prev]);        // 单趟完成        // [left, prev-1] prev [prev+1, right]        if(prev-1 > left) {            q.push(left);            q.push(prev-1);        }        if(prev+1 < right) {            q.push(prev+1);            q.push(right);        }    }}

使用队列实现快排，这里类似二叉树的层序遍历，而不是前序遍历了。

因为一次单趟之后，有左右两个区间（可能），而这里调用front 和 pop时，出左范围，入左范围的两个子区间，再出右范围，入右范围的两个子区间。之后是四个区间依次排序，依次入区间，最终变为8个区间（可能）。