[关闭]
@chawuciren 2018-12-04T13:02:59.000000Z 字数 843 阅读 716

算法导论 7

算法导论


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

7.1

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

  1. void quicksort(int array[],int p,int r){
  2. int q=0;
  3. if(p<r){
  4. q=partition(array,r);
  5. quicksort(array,p,q);//这里是q不是q-1,q才能拿到分组的最后一个元素,因为partition里面有-1了
  6. quicksort(array,q+1,r);
  7. }
  8. }
  9. int partition(int array[],int len){
  10. int x=array[len-1];
  11. int i=-1;
  12. for(int j=0;j<len-1;j++){//最后一个数内定了
  13. if(array[j]<=x){
  14. exchange(&array[i],&array[j]);
  15. i+=1;
  16. }
  17. }
  18. exchange(&array[i+1],&array[len-1]);
  19. i++;
  20. return i;
  21. }
  22. void exchange(int *p,int *q){
  23. int t=*p;
  24. *p=*q;
  25. *q=t;
  26. return;
  27. }

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


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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注