快速排序

阿秀自己刷过的算法部分经过整理后是按照不同基础、不同人群分类的，如果你不知道自己该看哪个部分的算法题，可以先看一下这里，戳我直达。

以下是本部分正文：

这里简单为大家讲解一下一些算法基础知识与十大排序，在面试考察中十大排序出现的频率是非常高的，特别是冒泡排序、快速排序、归并排序等，具体可点击这里

快速排序不太好记住

算法思想

1、选取第一个数为基准

2、将比基准小的数交换到前面，比基准大的数交换到后面

3、对左右区间重复第二步，直到各区间只有一个数

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

为方便理解我还准备了动图：

C++
void quickSort(vector<int>& a, int low, int high) {
    if (low >= high)        // 结束标志
        return;
    int first = low;        // 低位下标
    int last = high;        // 高位下标
    int key = a[first];     // 设第一个为基准

    while (first < last)
    {
        // 从后往前走，将比第一个小的移到前面
        while (first < last && a[last] > key)
            last--;
        if (first < last)
            a[first++] = a[last];

        //从前往后走， 将比第一个大的移到后面
        while (first < last && a[first] <= key)
            first++;
        if (first < last)
            a[last--] = a[first];
    }

    a[first] = key;
    // 前半递归
    quickSort(a, low, first - 1);
    // 后半递归
    quickSort(a, first + 1, high);

}


quickSort(A, 0,A.size()-1);
    for (auto a : A) {
        cout << a << endl;
    }

自己复写一遍，加强了理解

C++
void quickSort(vector<int>&numbers, int low, int high) {
    //  numbers = {10,8,4,6,9,10,123,6,2,14,3,8,5};
    if (low >= high) return;
    int first = low, last = high, key = numbers[low];
    cout << low << " " << high << " "<<key << endl;
    for (int i = 0; i < numbers.size(); ++i) {
        cout << numbers[i] << " ";
    }
    cout << endl;

    while (first < last) {
        //从后往前找比他小的放前面,从前往后找比他大的放在后面，
        //以第一个数为基准，必须先从后往前走，再从前往后走

        while (first < last && numbers[last] >= key)
            last--;
        if (first < last) numbers[first++] = numbers[last];


        while (first < last && numbers[first] <= key)
            first++;
        if (first < last) numbers[last--] = numbers[first];

    }
    numbers[first] = key;

    cout << "the index " << first << "  value " << key << endl;

    quickSort(numbers, low, first - 1);
    quickSort(numbers, first + 1, high);
}

再一次复写

C++
void quickSort2(vector<int>& nums, int begin, int end) {
    if (begin >= end) return;//4,10,3,0,5,1,2
    int first = begin, last = end;
    int key = nums[first];
    while (first < last) {
        while (first < last && nums[last] >= key)
            last--;
        if (first < last)
            nums[first++] = nums[last];

        while (first < last && nums[first] <= key)
            first++;
        if (first < last)
            nums[last--] = nums[first];
    }

    nums[first] = key;
    cout << begin << " " << end << " " << key << endl;
    for (auto a : nums)
        cout << a << " ";
    cout << endl << endl;


    quickSort2(nums, begin, first-1);
    quickSort2(nums, first+1, end);

}

再次复写

C++
void print(vector<int>& nums) {
    for (auto a : nums)
        cout << a << " ";
    cout << endl;

}
void quickSort(vector<int>& nums, int begin, int end) {
    if (begin >= end) return;
    int low = begin, high = end, key = nums[begin];
    while (low < high) {
        while (low < high && nums[high] >= key) {
            high--;

        }
        if (low < high)  nums[low++] = nums[high];

        while (low < high && nums[low] <= key) {
            low++;

        }
        if (low < high)  nums[high--] = nums[low];
    }

    nums[low] = key;
    print(nums);

    quickSort(nums, begin, low - 1);
    quickSort(nums, low + 1, end);

}

快速排序

快速排序 不太好记住

快速排序不太好记住