@chawuciren
2018-12-04T13:02:59.000000Z
字数 843
阅读 821
算法导论
快速排序是一种使用分治思想的排序,平均的事件复杂度是O(n lg n),最坏的情况是O(n^2).
快速排序分为三个部分:
第一部分,将数组分为比某个选定的数大的部分和比他小的部分。
第二部分,将这两个部分进行排序。
第三部分,合并,其实没什么要做的了。
其中的一个重要子循环,将一个数组分成两个部分,一部分比这个数要小,一部分比这个数要大。
首先有一个数组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小的元素。做完这些进行下一次迭代。(十分巧妙了,想起我以前写的......)
按百度网盘的下载速度看算法导论......