#include <bits/stdc++.h>

using namespace std;

//数组打印
void P(int a[], int n) {
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

/*
快速排序算法
1.从数列中挑出一个元素，称为 “基准”（pivot）；
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
 在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
 */


// 下面的方法其实是用的左右指针
int partition(int *s, int l, int r) {
    //左边第一个默认是基准元素
    int i = l, j = r, x = s[l]; //将最左元素记录到x中,x是一个备份
    //i,j应该是双指针的意思
    while (i < j) {
        // 从右向左找第一个<x的数,注意这里面的i<j,防止j--后j<=i.
        while (i < j && s[j] >= x)
            j--;
        //j还在i的右边的话
        if (i < j)
            s[i++] = s[j]; //直接替换掉最左元素（已在x中存有备份）

        // 从左向右找第一个>x的数
        while (i < j && s[i] <= x)
            i++;
        if (i < j)
            //替换掉最右元素(已在最左元素中有备份）
            //最左元素一定被覆盖过，若没有，则表明右侧所有元素都>x，那么算法将终止
            s[j--] = s[i];
    }
    s[i] = x;  //i的位置放了x，所以其左侧都小于x，右侧y都大于x
    return i;
}

// 图解快速排序quick sort
// https://haokan.baidu.com/v?vid=190736151353458762&pd=bjh&fr=bjhauthor&type=video
// 实现 Partion (升序) 快慢指针
// https://blog.csdn.net/qq_43763344/article/details/89409246?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~sobaiduend~default-2-89409246.nonecase&utm_term=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E5%BF%AB%E6%85%A2%E6%8C%87%E9%92%88&spm=1000.2123.3001.4430
int partition2(int *array, int left, int right) {
    // 最后一个值作为基准值.
    int key = array[right - 1];
    int pre = left - 1;
    for (int cur = left; cur < right; ++cur) {
        if (array[cur] < key && ++pre != cur) {
            swap(array[cur], array[pre]);
        }
    }
    swap(array[++pre], array[right - 1]);
    return pre;
}

//递归的快速排序
void quickSort(int s[], int l, int r) {
    //l,r-->从l到r
    //数组左界<右界才有意义，否则说明都已排好，直接返回即可
    if (l >= r) {
        return;
    }
    // 划分，返回基准点位置
    int mid = partition2(s, l, r);
    // 递归处理左右两部分，mid处为分界点，不用管mid了
    quickSort(s, l, mid - 1);
    quickSort(s, mid + 1, r);
}

int main() {
    int a[] = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
    //输出一维数组
    P(a, 10);
    //快速排序
    quickSort(a, 0, 9);//注意最后一个参数是n-1
    //再次输出一维数组
    P(a, 10);
    return 0;
}