算法导论 7

算法导论

快速排序是一种使用分治思想的排序，平均的事件复杂度是O（n lg n），最坏的情况是O（n^2）.

7.1

快速排序分为三个部分：
第一部分，将数组分为比某个选定的数大的部分和比他小的部分。
第二部分，将这两个部分进行排序。
第三部分，合并，其实没什么要做的了。
其中的一个重要子循环，将一个数组分成两个部分，一部分比这个数要小，一部分比这个数要大。
首先有一个数组A，长度为r，第一个元素记为P，第一部分的最后一个数记为q-1，第二部分的第一个数记为q+1，中间那个数是q。

void quicksort(int array[],int p,int r){
    int q=0;
    if(p<r){
        q=partition(array,r);
        quicksort(array,p,q);//这里是q不是q-1，q才能拿到分组的最后一个元素，因为partition里面有-1了
        quicksort(array,q+1,r);
    }
}
int partition(int array[],int len){
    int x=array[len-1];
    int i=-1;
    for(int j=0;j<len-1;j++){//最后一个数内定了
        if(array[j]<=x){
            exchange(&array[i],&array[j]);
            i+=1;
        }
    }
    exchange(&array[i+1],&array[len-1]);
    i++;
    return i;
}
void exchange(int *p,int *q){
    int t=*p;
    *p=*q;
    *q=t;
    return;
}

11.21
接下来讲了在不同下标范围，A[i]与x的关系（在任何一次迭代里都成立）
根据以上代码（还是没有gdb.....）如果这个数比x大，就不进行交换，但是j照常加一。如果这个数比x小，就
先交换，然后i加一，i加一以后发现前面的边界往前挪了一位，刚好包括了那个交换过去的比x小的元素。做完这些进行下一次迭代。（十分巧妙了，想起我以前写的......）

按百度网盘的下载速度看算法导论......