快速排序​2013

快速排序
李春宝C语言 P117

int Partition(int R[],int i,int j){ //对R[low...high]做划分，返回基准元素的位置
    int pivot = R[i]; //用区间的第i个元素作为基准
    while(i<j){ //从区间两端交替向中间扫描，直至i=j为止
        while(i<j && R[j]>=pivot) j--;
        R[i++] = R[j];
        while(i<j && R[i] <= pivot) i++;
        R[j--] = R[i];
    }
    R[i] = pivot;
    return i;
}

void QuickSort(int R[],int low,int high){ //对R[low...high]快速排序
    int pivotpos; //划分后的基准元素的位置
    if(low<high){ //仅当区间长度大于1时才需要排序
        pivotpos = Partition(R,low,high); //对R[low...high]划分
        QuickSort(R,low,pivotpos-1); //对左区间递归排序
        QuickSort(R,pivotpos-1,high);//对右区间递归排序
    }

}


















#include <stdio.h>
void quicksort(int array[], int min, int max);
int partition(int array[], int min, int max)
{
    int p;  p = array[min];
    //int len = max;
    while (min < max)
    {
        while (array[max] >= p && min < max)
        {
            max--;
        }
        array[min] = array[max];
        while (array[min] <= p && min < max)
        {
            min++;
        }
        array[max] = array[min];
    }
    array[min] = p;
    //printf("分界：%d\n", min);
    return  min;
}
void quicksort(int array[], int min, int max, int n)
{
    int p;
    p = partition(array, min, max);
    //printf("p = %d\n", p);
    printf("执行结果：");
    for (int i = 0; i <= 11; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");
    if (min < max)
    {
        printf("第%d次前序递归执行:", n);
        printf("quicksort(array, %d, %d)\n", min, p - 1);
        quicksort(array, min, p - 1, n);        n++;
        //partition(array, p+1 , max);
        printf("第%d次后序递归执行:", n);
        printf("quicksort(array, %d, %d)\n", p + 1, max);
        quicksort(array, p + 1, max, n);
    }
}
int main()
{
    int arr[] = { 5, 9, 2, 7, 8, 3,1,4, 11, -10, 10, 0 };
    //printf("%d\n", sizeof(arr) / sizeof(arr[0]));
    int min = 0;
    int max = sizeof(arr) / sizeof(arr[0]) - 1;
    //int p = partition(arr, min, max);
    //printf("min的值为：%d\n", min);
    //partition(arr, min, p);
    printf("进入递归之前执行:");
    printf("quicksort(array, %d, %d)\n", 0, 11);
    quicksort(arr, min, max, 1);
    return 0;
}