Aaron学习笔记

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

快速排序算法的基本思想是：在待排序的n个记录中任取一个记录（通常先取第一个）为分区标准，把所有小于该排序码的记录移动到左边，把所有大于该排序码的记录移动到右边，中间放所选记录，称之为一趟排序；然后，对两个子序列分别重复上述过程
快速排序(QuickSort)的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)，平均时间复杂度为O(nlgn)。快速排序(QuickSort)在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。

#include "stdio.h"

void qsort(int s[], int l, int r);

int main(){
    int array[10] = {2,4,6,1,8,7,9,10,0,3};
    int i;
    qsort(array,0,9);
    for(i = 0; i < 10; i++)
        printf("%d ",array[i]);
    return 0;
}
void qsort(int s[], int l, int r)  //l,r已经是数组的下标了，即最初的r = n-1
{
    int i, j, x;
    if (l < r)
    {
        i = l; //i代表从数组最左面开始的下标号
        j = r;  //j代表从数组最右开始的下标
        x = s[i]; /**//* 中间变量*/
        while (i != j)
        {
            while(i < j && s[j] > x)
                j--; /**//* 从右向左找第一个小于x的数 */
            if(i < j)
                s[i++] = s[j];
            while(i < j && s[i] < x)
                i++; /**//* 从左向右找第一个大于x的数 */
            if(i < j)
                s[j--] = s[i];
        }
        s[i] = x;
        qsort(s, l, i-1); /**//* 递归调用 */
        qsort(s, i+1, r);
    }
}