#include"algo.h"
#include<stdlib.h>
#include<math.h>
#include<time.h>
void QuickSort(int* arr, int left, int right)
{
    //直到不合理情况出现结束递归
    if (left >= right) 
    {
        return;
    }
    //找到"left"对应在数组的位置，并将保存位置的序号赋给position
    int position = PartSort(arr, left, right);
    //分别对position左右进行进行快速排序
    QuickSort(arr, left, position - 1);
    QuickSort(arr, position + 1, right);
}


int  PartSort(int* arr, int left, int right)
{
    int key = arr[left];
    //找到"left"的位置，并保证左边比其小，右边比其大
    while (left < right) {
        while (left < right && arr[right] >= key) 
        {
            right--;
        }
        swap(arr, left, right);

        while (left < right && arr[left] <= key) 
        {
            left++;
        }         
        swap(arr, left, right);
    }
    //将找出的最终位置返回
    return left;
}


void swap(int* arr, int left, int right)
{
    int temp = 0;

    temp = arr[right];
    arr[right] = arr[left];
    arr[left] = temp;
}