/**
 * @brief: 快速排序
    * @version: 1.0
    * @author: @Shiel
    * @date: 2023-11-27 08:40:26
    **/
# include <stdio.h>

void Sort_Quick( int* a, int low, int high );   // 快排
int FindPos( int* a, int low, int high);    // 查找并返回 L=H 的位置

int main(void)
{
    int a[7] = {5, 2, 6, 8, 4, 3 ,7};
    
    Sort_Quick(a, 0, 6);    // 第二个元素表示第一个元素的下标，第三个参数表示最后一个元素的下标
    
    for( int i=0; i<7; i++ )
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    
    return 0;
}

void Sort_Quick( int* a, int low, int high )
{
    int pos;    // 中间点 L=H 时的位置
    
    if( low < high )    // 只有 low<high 时才继续进行
    {
        pos = FindPos(a, low, high);    // 获取中间点 L=H 的位置
        Sort_Quick(a, low, pos - 1);    // 中间点左半部递归
        Sort_Quick(a, pos + 1, high);   // 中间点右半部递归
    }
}

int FindPos( int* a, int low, int high )
{
    int val = a[low];
    
    while( low < high )
    {
        // 首先从右边 high 开始向左进行查找
        while( low < high && a[high] > val )    // high 指向的元素大于val，high左移
        {
            high--;	    // a[high]>val，不需要赋值，则high左移
        }
        a[low] = a[high];   // 即a[high]<val的情况，此时将a[high]赋给a[low]
        
        // 再从左边 low 开始向右进行查找
        while( low < high && a[low] < val )     // low指向的元素小于val，low右移
        {
            low++;      // a[low]<val，不需要赋值，则low右移
        }
        a[high] = a[low];   // 即a[low]>val的情况，此时将a[low]赋值给a[high]
    } //终止循环之后 L和H 一定是相等的
    
    a[low] = val;   // L=H，此时将val的值赋给 a[low]和a[high] 是一样的
    
    return high;    // 返回下标，等价于 return low;
}

typedef struct _Range {
    int start, end;
} Range;

Range new_Range(int s, int e) {
    Range r;
    r.start = s;
    r.end = e;
    return r;
}

void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}

void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return; // 避免len等于负值时引发段錯誤（Segment Fault）
    // r[]模板列表,p为數量,r[p++]为push,r[--p]为pop且取得元素
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[(range.start + range.end) / 2]; // 选取中间点为基准点
        int left = range.start, right = range.end;
        do {
            while (arr[left] < mid) ++left;   // 检测基准点左侧是否符合要求
            while (arr[right] > mid) --right; //检测基准点右侧是否符合要求
            if (left <= right) {
                swap(&arr[left], &arr[right]);
                left++;
                right--;               // 移动指针以继续
            }
        } while (left <= right);
        if (range.start < right) r[p++] = new_Range(range.start, right);
        if (range.end > left) r[p++] = new_Range(left, range.end);
    }
}

void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}

void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}

void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}