快速排序 quicksort

基本思想

• 选定Pivot中心轴
• 将大于Pivot的数字放在Pivot的右边
• 将小于Pivot的数字放在Pivot的左边
• 分别对左右子序列重复前三部操作

参考视频：

快速排序算法_哔哩哔哩_bilibili

#include 
 
void QuickSort(int *arr,int L,int R);
int main()
{
    int arr[3] = {1000,2,3};
    QuickSort(arr,0,2);
    for(int i = 0 ; i < 3 ; i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}
void QuickSort(int *arr,int L,int R)
{
    if(L>=R)
    {
        return;
    }
    int left = L;
    int right = R;
    int pivot = arr[left];
 
    while(left < right)
    {
        while(left < right && arr[right] >= pivot)
        {
            right--;
        }
        if(left < right)
        {
            arr[left] = arr[right];
        }
        while(left < right && arr[left] <= pivot)
        {
            left++;
        }
        if(left < right)
        {
            arr[right] = arr[left];
        }
        if(left >= right)
        {
            arr[left] = pivot;
        }
    }
    QuickSort(arr,L,right-1);
    QuickSort(arr,right+1,R);
}

right指针像左移动，直至扫出比目标小的值，使其指针所指的值放入左指针所指的位置。然后进行左指针的移动。

left指针向右移动，直至扫出比目标大的值，使其指针所指的值放入右指针所指的位置。然后进行右指针的移动。

在C语言中，"pivot"这个词本身并没有一个特定的缩写。它是一个英语单词，用于描述在算法中选择基准元素的操作。"pivot"一词表示一个固定点或轴，用于分割或旋转其他元素。

或者：

#include 
 
void QuickSort(int *arr,int L,int R);
int main()
{
    int arr[3] = {1000,2,3};
    QuickSort(arr,0,2);
    for(int i = 0 ; i < 3 ; i++)
    {
        printf("%d ",arr[i]);
    }
    return 0;
}
void QuickSort(int *arr,int L,int R)
{
    if(L>=R)
    {
        return;
    }
    int left = L;
    int right = R;
    int pivot = arr[left];
 
    while(left < right)
    {
        while(left < right && arr[right] >= pivot)
        {
            right--;
        }
        if(left < right)
        {
            arr[left] = arr[right];
        }
        while(left < right && arr[left] <= pivot)
        {
            left++;
        }
        if(left < right)
        {
            arr[right] = arr[left];
        }
        // if(left >= right)
        // {
        //     arr[left] = pivot;
        // }
    }
    arr[left] = pivot;
    QuickSort(arr,L,right-1);
    QuickSort(arr,right+1,R);
}