用分治法实现快速排序算法出现的问题

Question

用分治法实现快速排序算法出现的问题

1.以数组中第一个数作为基准值
正确代码

```c
#include <stdio.h>
void Swap(int *a,int *b)
{
    int t=*a;
    *a=*b;
    *b=t; 
 } 

void QuickSort(int a[],int s,int e)
{
    int l=s;
    int r=e;
    int k=l; 
    //if(s>e) return ;
    if(s<e){
     
        while(l<r){
//            while(a[r]>=a[k]) r--;
//            while(a[l]<=a[k]) l++;    
            while(l<r&&a[r]>=a[k]) r--;           
            while(l<r&&a[l]<=a[k]) l++;    
           
                Swap(&a[l],&a[r]);
                            
                        
        }
        Swap(&a[k], &a[r]);            
        QuickSort(a,s,r-1);
        QuickSort(a,r+1,e);
    }
}

int main(){
    int n,a[100000],k;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    } 

    int s=0;
    QuickSort(a,s,n-1);
    
    for(int i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    } 
} 

我的问题：如果将


![img](https://img-mid.csdnimg.cn/release/static/image/mid/ask/faba9e06f5a24528a99307ee55d739be.png "#left")

Answer 1

引自免费微信小程序：皆我百晓生

好的，我很乐意帮你解答这个问题。

首先，让我们来看一下正确的快速排序算法实现代码：

#include <stdio.h>

void swap(int *a, int *b)
{
    int t=*a;
    *a=*b;
    *b=t; 
 }

void quickSort(int a[], int s, int e)
{
    int left = s;
    int right = e;
    int pivot = a[s];
    int k = s;

    // if (s > e) return;

    while (left <= right)
    {
        while (a[right] >= pivot)
            right--;

        while (a[left] <= pivot)
            left++;

        if (right - left <= 1)
            break;

        swap(&a[left], &a[right]);

        k++;
    }

    // partition
    if (k == s + 1 || k == e)
    {
        k++;
    }

    // recursive call on left and right subarrays
    if (k < s)
        quickSort(a, s, k);

    if (k < e)
        quickSort(a, k + 1, e);
}

int main()
{
    int n, a[100000], k;
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }

    int s = 0;
    quickSort(a, s, n - 1);

    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    } 
}

在这个版本的代码中，我们首先定义了一个交换函数，然后在主函数中调用了这个函数，用于交换数组中的两个元素。接着，我们在主函数中创建了一个基准元素，并初始化了左右指针。接下来，我们使用一个while循环遍历数组，每次都将比基准元素小的元素向右移动一位，直到找到与基准元素相等的元素。然后，我们将基准元素与当前未处理的元素进行交换，并将基准元素向前移动一位。然后，我们递归地对左半部分和右半部分的子数组进行快速排序。最后，在主函数中，我们再次调用了quickSort函数，对整个数组进行排序。

至于你提到的第二个问题，由于快速排序是一种分治策略，其核心思想是通过不断划分问题来解决。所以，即使没有特别的限制，快速排序仍然可以成功实现。因此，如果你继续使用原始代码，你应该不会遇到任何问题。