首页 > 代码库 > 快速排序
快速排序
算法描述 分而治之
过程1：以65为主元，将小于65的为一组放在65左边。大于65的为一组放在65右边。 排序后： {左边} 主元(65) {右边}
递归的进行。在左边这一组选一个主元，重复上过程1。右边这一组选一个主，重复过程1。
直到左边右边都只有一个元素。
对于小规模数据，用递归并不划算，小规模数据我们用简单排序。
设定阈值，当数据规模小于阈值时，简单排序。大于阈值，分而治之。
1 int Median3(ElementType A[],int Left,int Right)// 选主元。 2 { 3 int center; 4 center=(Left+Right)/2; 5 if(A[Left]>A[center]) 6 Swap(A+Left,A+center); 7 if(A[Left]>A[Right]) 8 Swap(A+Left,A+Right); 9 if(A[center]>A[Right])10 Swap(A+center,A+Right);11 Swap(A+center,A+Right-1);12 return A[Right-1];//把主y元放在r-1的位置，这样left，r-1，right都是有序的，排序的时候只需从l+1,到r-2。13 14 }15 void Quicksort(ElementType A[] ,int Left,int Right)16 {17 int pivot,k,i,j,cutoff;18 cutoff=50;19 20 if(Right-Left>cutoff) //小于阈值，快速排序，小规模排序，递归21 {22 pivot=Median3(A,Left,Right);23 i=Left; //排序的时候只需从l+1,到r-2。24 j=Right-1;25 while(1)26 {27 while(A[++i]<pivot);28 while(A[--j]>pivot); //超级错误29 if (i<j)30 Swap(A+j,A+i);31 else break;32 33 }34 Swap(A+i,A+Right-1);35 Quicksort(A,Left,i-1);36 Quicksort(A,i+1,Right);37 38 }39 else40 {41 //简单排序42 Insertion_sort( A, Right-Left);43 }44 }45 void Quick_Sort(ElementType A[],int N)46 {47 Quicksort(A,0,N-1);48 }
错误分析：
1. 28行 --j不要写成++j,j是高位，从右往左移动
2. 22行 pivot 不要写在if的外面，只有快速排序的时候才会用pivot
快速排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。