[数据结构与算法]2021-09-12

快速排序

题目分析
对一个整数序列进行快速排序：在待排序的整数序列中取第一个数作为基准数，然后根据基准值进行划分，从而将待排序列划分为不大于基准值者（左子序列）和大于基准值者（右子序列），然后再对左右子序分别进行快速排序。
代码实现

#include<stdio.h>

void quicksort(int a[],int n)
{
    int i,j;
    int pivot = a[0];
    i = 0;
    j = n-1;
    while(i < j)
    {
        while(i < j && pivot < a[j])
        j--;
        if(i < j)
        {
            a[i] = a[j];
            i++;
        }
        //使比基准值大者保持在序列后端
        while(i < j && pivot > a[i])
        i++;
        if(i < j)
        {
            a[j] = a[i];
            j--;
        }
        //使得不大于基准值者保持在前端
    }
    a[i] = pivot;
    //基准元素归位
    if(i > 1)
        quicksort(a,i);
    //左子序列排序
    if(n-i-1 > 1)
        quicksort(a+i+1,n-i-1);
    //友子序列排序
}
int main()
{
    int i,arr[] = {23,56,9,75,18,42,11,69};
    int len = sizeof(arr)/sizeof(int);
    quicksort(arr,len);
    for(i = 0;i < len;i++)
        printf("%d\t",arr[i]);
    return 0;
}

对递归子序分析
快速排序算法中的难点，自我感觉是在递归的对左右子序列进行排序。
假设第一次划分排序完成后，基准元素放入a[i]中（代码中注释的基准元素归位）。那么划分出来的左子序列a[0]到a[i-1]这i个元素构成，不要忘了a[0]也是一个元素哦，右子序分由a[i+1]到a[n-1]构成，第n个元素对应a[n-1]哈，别乱了(?_?)。
所以调用左子序列，元素个数为i-1-0+1，quicksort（a，i）。右子序列元素个数为n-1-（i+1)+1，quicksort（a+i+1，n-i-1）。
学习ing，如有错误请指教( ??? ? ??? )