-1

对于快速排序算法（递归），每次调用自身时，都有条件if(p < r)。如有错误请指正：据我所知，对于每一个递归算法，它都有一个条件作为它进入例程的时间，这个条件是用来获取基本情况的。但我仍然无法理解如何正确设置和测试这个条件？

void quickSort(int* arr, int p, int r)
{
    if(p < r)
    {
        int q = partition(arr,p,r);
        quickSort(arr,p,q-1);
        quickSort(arr,q+1,r);
    }
}

对于我的整个代码，请参考以下内容：

/*
filename   :  main.c
description:  quickSort algorithm
*/

#include<iostream>
using namespace std;


void exchange(int* val1, int* val2)
{
    int temp = *val1;
    *val1 = *val2;
    *val2 = temp;
}


int partition(int* arr, int p, int r)
{
     int x = arr[r];
     int j = p;
     int i = j-1;

     while(j<=r-1)
     {
        if(arr[j] <= x)
        {
            i++;
            // exchange arr[r] with arr[j]
            exchange(&arr[i],&arr[j]);
        }
        j++;
     }
     exchange(&arr[i+1],&arr[r]);
     return i+1;
}

void quickSort(int* arr, int p, int r)
{
    if(p < r)
    {
        int q = partition(arr,p,r);
        quickSort(arr,p,q-1);
        quickSort(arr,q+1,r);
    }
}








// driver program to test the quick sort algorithm
int main(int argc, const char* argv[])
{
    int arr1[] = {13,19,9,5,12,8,7,4,21,2,6,11};
    cout <<"The original array is: ";
    for(int i=0; i<12; i++)
    {
        cout << arr1[i] << " ";
    }
    cout << "\n";

    quickSort(arr1,0,11);

    //print out the sorted array

    cout <<"The sorted array is: ";

    for(int i=0; i<12; i++)
    {
        cout << arr1[i] << " ";
    }
    cout << "\n";

    cin.get();

    return 0;
}
4

1 回答 1

3

你的问题不是很清楚，但我会尽力回答。

快速排序通过对越来越小的数组进行排序来工作。基本情况是一个少于 2 个元素的数组，因为不需要排序。

在每一步，它都会找到一个分区值 ，并确保分区值左侧的所有值都较小，而分区值右侧的所有值都较大。换句话说，它将分区值放在正确的位置。然后它递归地对分区左侧的数组和分区右侧的数组进行排序。

快速排序的基本情况是具有一个元素的数组，因为单元素数组不需要排序。在您的代码中， p 是第一个元素的索引，而 r 是最后一个元素的索引。谓词 p < r 仅适用于大小至少为 2 的数组。换句话说，如果 p >= r 则您有一个大小为 1（或零，或无意义）的数组，并且没有工作要做。

于 2013-09-12T15:53:31.760 回答