CPP

#include <iostream>

using namespace std;

//快速排序
void quickSort(int arr[], int low, int high);
void quickSort_another(int *arr, int left, int right);
//划分函数
int partition(int arr[], int low, int high);

int main()
{
    int arr[] = {5, 2, 4, 6, 1, 3};
    quickSort(arr, 0, 5);
    for(auto cur:arr)
        cout << cur << " ";
    cout << endl;
    quickSort_another(arr, 0, 5);
    for(auto cur:arr)
        cout << cur << " ";
    return 0;
}

int partition(int arr[], int low, int high)
{
    int pivot = arr[low];   //第一个元素作为基准
    while(low < high)   //low == high时结束
    {
        while(low < high && arr[high] >= pivot)
            --high;
        arr[low] = arr[high];   //此时arr[high]小于基准元素
        while (low < high && arr[low] <= pivot)
            ++low;
        arr[high] = arr[low];   //此时arr[low]大于基准元素
    }
    arr[low] = pivot;   //此时low == high
    return low;     //返回基准元素的下标
}
void quickSort(int arr[], int low, int high)
{
    if(low < high)
    {
        int pivot_pos = partition(arr, low, high);
        quickSort(arr, low, pivot_pos - 1);     //对基准元素左边的数组进行快速排序
        quickSort(arr, pivot_pos + 1, high);    //对基准元素右边的数组进行快速排序
    }
}

//写法二
void quickSort_another(int *arr, int left, int right)
{
    if (left >= right)
        return;
    int pivot = arr[left];
    int i = left + 1, j = right;
    while (i <= j)
    {
        while (i <= right && arr[i] < pivot)
            i++;
        while (j >= left && arr[j] > pivot)
            j--;
        if (i <= j)
        {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    arr[left] = arr[j];
    arr[j] = pivot;
    quickSort_another(arr, left, j - 1);
    quickSort_another(arr, j + 1, right);
}