基本思想

快速排序是不稳定的排序算法。
假设最终结果是递增有序的。快速排序的基本思想是选取一个记录作为枢轴，经过一趟排序，将整段序列分为两个部分，其中左半部分的值都小于枢轴，右半部分都大于枢轴。然后对这两部分继续进行递归排序，从而使整个序列达到有序。
左右指针法（输入为数组,又叫挖坑法）:

选取一个关键字作为枢轴，一般取整组记录的第一个数/最后一个，这里两种方式都实现了。
设置两个变量left = 0;right = N - 1;
从left一直向后走，直到找到一个大于key的值，right从后至前，直至找到一个小于key的值，然后交换这两个数。
重复第三步，一直往后找，直到left和right相遇，这时将key放置left的位置即可。
C/C++实现
左右指针法:
`cpp
include
include

using namespace std;

class Solution {
public:
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}

int partition(vector<int> &nums, int left, int right) {
    int key_value = nums[left];
    int i = left, j = right;
    while (i < j) {
        //取左边第一个值作枢轴时请让j先行,这样最后i==j时i正好在枢轴最后的正确位置上,返回的i就是枢轴的最终位置
        //两个while中判断必须是>=和<=,否则如果枢轴在数组中有一样的值时结果不正确
        while (i < j && nums[j] >= key_value)
            j--;
        while (i < j && nums[i] <= key_value)
            i++;
        if (i < j)
            swap(nums[i], nums[j]);
    }
    swap(nums[left], nums[i]);
    return i;
}

// int partition(vector &nums, int left, int right) {
// int key_value = nums[right];
// int i = left, j = right;
// while (i < j) {
// //取右边最后一个值作枢轴时请让i先行,这样最后i==j时j正好在枢轴最后的正确位置上,返回的j就是枢轴的最终位置
// //两个while中判断必须是>=和<=,否则如果枢轴在数组中有一样的值时结果不正确
// while (i < j && nums[i] <= key_value)
// i++;
// while (i < j && nums[j] >= key_value)
// j–;
// if (i < j)
// swap(nums[i], nums[j]);
// }
// swap(nums[right], nums[j]);
// return j;
// }

void quick_sort(vector<int> &nums, int left, int right) {
    if (left >= right)
        return;
    int pos = partition(nums, left, right);
    quick_sort(nums, left, pos - 1);
    quick_sort(nums, pos + 1, right);
}

};

int main() {
vector a = {5, 2, 3, 4, 7, 5, 1, 6};
Solution s;
s.quick_sort(a, 0, a.size() - 1);
for (int i : a)
cout << i << “ “;
cout << endl;
return 0;
}

# Python3实现
**左右指针法:**
```python
class Solution(object):
    def partition(self, nums, left, right):
        key_value = nums[left]
        i, j = left, right
        while i < j:
            # 取左边第一个值作枢轴时请让j先行,这样最后i==j时i正好在枢轴最后的正确位置上,返回的i就是枢轴的最终位置
            # 两个while中判断必须是>=和<=,否则如果枢轴在数组中有一样的值时结果不正确
            while i < j and nums[j] >= key_value:
                j -= 1
            while i < j and nums[i] <= key_value:
                i += 1
            if i < j:
                nums[i], nums[j] = nums[j], nums[i]
        nums[left], nums[i] = nums[i], nums[left]
        return i

    # def partition(self, nums, left, right):
    #     key_value = nums[right]
    #     i, j = left, right
    #     while i < j:
    #         # 取右边最后一个值作枢轴时请让i先行,这样最后i==j时j正好在枢轴最后的正确位置上,返回的j就是枢轴的最终位置
    #         # 两个while中判断必须是>=和<=,否则如果枢轴在数组中有一样的值时结果不正确
    #         while i < j and nums[i] <= key_value:
    #             i += 1
    #         while i < j and nums[j] >= key_value:
    #             j -= 1
    #         if i < j:
    #             nums[i], nums[j] = nums[j], nums[i]
    #     nums[right], nums[j] = nums[j], nums[right]
    #     return j

    def quick_sort(self, nums, left, right):
        if left >= right:
            return
        pos = self.partition(nums, left, right)
        self.quick_sort(nums, left, pos - 1)
        self.quick_sort(nums, pos + 1, right)


a = [5, 2, 3, 4, 7, 5, 1, 6]
s = Solution()
s.quick_sort(a, 0, len(a)-1)
print(a)

赏