#include <iostream>
#include "iomanip"

using namespace std;
/*
思想：从第0个元素开始依次扫描整个序列，
工作指针为i，其代表着位置为i的最小元素。
而j指针从末尾依次选出最小值。
即：进行n-1趟，每趟都让最大或最小值在队列的最末端或最前端。
*/
void BubbleSort(int a[], int n)
{
    for(int i = 0; i < n-1; i++)
    {
        bool flag = true;
        //如果出现该趟排序中没有交换元素位置，即有序。
        for(int j = n-1; j > i; j--)
        {
            if(a[j-1] > a[j])
            {
                swap(a[j],a[j-1]); flag = false;
            }
        }
        if(flag) return;
    }
}
/*
思想：1、每次选出基准接着对序列进行划分
（要求左边的元素比他小，右边的元素比他大，由此来确定他的位置）；
2、接着递归的对其左右子序列进行相同的划分操作来确定其子序列中每个基准元素的位置。
*/
int Partition(int a[] , int left , int right)
{
    int pivot = a[left];
    //选取第一个元素作为基准
    while(left < right)
    {
        while(left < right && a[right] >= pivot) right--;
        //从右往左找第一个比pivot基准元素还要小的元素位置
        //因为我们要保证pivot右边元素都是比它还要大的
        a[left] = a[right];//如果left = right即使本身复制本身
        while(left < right && a[left] <= pivot) left++;
        a[right] = a[left];
    }
    a[left] = pivot;//把pivot放在最终的位置上，Left代表的是最后空出来的位置。
    return left;
}

/*
随机快速排序算法改进：
从0到n-1个元素中随机选取基准元素。
在快速排序的基础上添加 随机划分函数。
*/
int RandomPartition(int a[] , int left , int right)
{
    //int r = random(left , right);//(rand() % (b-a+1))+ a;考试用random即可
    //swap(a[left] , a[r]);
    return Partition(a , left , right);
}

void QuickSort(int a[], int left , int right)
{
    //递归出口
    if(left < right)
    {
        int mid = Partition(a , left , right);//改行是RandomPartition和Partition的区别。
        //选取基准元素进行左右划分
        QuickSort(a , left , mid-1);
        QuickSort(a , mid+1 , right);
    }
}


/*
三划分快速排序算法:
*/

void ThreeQuickSort(int a[] , int left , int right)
{
    if(left >= right) return;//递归出口
    //变量描述 L R代表左右两边等于pivot元素的位置。
    //i j为从前后两端向左边扫描（和快速排序一样）
    int L , R , i , j , k;
    int pivot;
    i = L = left-1; j = R = right;
    pivot = a[right];//选右端的元素作为pivot则right位置元素位置空出来。
    while(true)
    {
        while(a[++i] < pivot);//++i对应L定义为left-1
        while(pivot < a[--j])//因为选的pivot是right，那么它自己不用再判断
            if(j == left) break;
        if(i >= j) break;//已经实现左边的元素比pivot小，右边的比pivot大
        swap(a[i] , a[j]);
        if(a[i] == pivot)
        {
            L++; swap(a[L],a[i]);//把i扫到的等于pivot的元素换到左端
        }
        if(a[j] == pivot)
        {
            R--; swap(a[R],a[j]);//把j扫到的等于pivot的元素换到右端
        }
    }
    swap(a[i] , a[right]);
    //该处代表的是a中第i个元素和第right个元素的位置发生交换。
    //而不是a[i]和pivot元素交换，如果是写pivot那么a[i]值放到的是pivot变量
    j = i-1; i = j+1;//j指针继续向左扫描 ， i指针向右扫描
    for(k = left ; k < L ; k++,j--)
    {//以k为左端起点扫描到中间位置向左的第一个位置
        swap(a[k] , a[j]);
    }
    for(k = right-1 ; k > R ; k-- , i++)
    {
        swap(a[k] , a[i]);
    }
    ThreeQuickSort(a , left , j);
    ThreeQuickSort(a , i , right);
}

int main()
{
    int a[10] = {1,9,2,0,12,4,5,3,7,10};
    //BubbleSort(a ,10);
    ThreeQuickSort(a , 0 , 9);
    for(int i = 0 ; i < 10 ; i++)
        printf("%d ",a[i]);
}