朝阳市做网站的公司,各大网站收录入口,win2012 iis 新建网站,铁道部建设司网站/*快速排序(QuickSort)2013年10月3日by --- acton算法思想 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。（1） 分治法的基本思想 分治法的基本思想是&#x…
/*
快速排序(QuickSort)
2013年10月3日
by --- acton
算法思想
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
（2）快速排序的基本思想
设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解：
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
注意：
划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③组合：
因为当 "求解 "步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言， "组合 "步骤无须做什么，可看作是空操作。
快速排序的复杂度是O(nlgn),其递归树的表示形式应该为T(n) = 2T(n/2) + O(n)
(比较理想的情况是刚好一分为2，然后问题的规模变小)，但是也不排除会出现 T(n) = T(n-1) + O(n)也就是一边
有n-1个元素一边的这种情况，此时的复杂度达到了O(n2)了，蜕化跟InsertSort一样,所以关键是那个划分的元素的选取，
如果没有选取一个比较恰当的pivotkey的话，可能会造成O(n2)的复杂度，但是快速排序在大多的情况下表现的还是比较的优秀的，
例如当划分为一边为1/10,另一边为9/10, 即为 T(n) = T((1/10)*n) + T((9/10)*n) + O(n)的情况时候，解递归树采用渐进的方法
快速排序的随机化版本：
如上已经说过，快速排序的key在于partition，而partition的关键在于对pivotkey的选取，如果没有适当的选取，可能会到最坏的复杂度，
所以此处采用随机化选取那个pivotkey
如下伪算法的实现：
Randomized_Partition(A,p,r){
i = RANDOM(p,r);
Exchange(A[i],A[r]);
return Partition(A,p,r);
}
其他的算法都基本没有改变主要是pivotkey的选取，算法导论中P157中用指示器随机 变量证明了该算法的平均复杂度为O(nlgn)
*/
/*
快速排序(QuickSort)
2013年10月3日
by --- acton
算法思想
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
（2）快速排序的基本思想
设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解：
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
注意：
划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③组合：
因为当 "求解 "步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言， "组合 "步骤无须做什么，可看作是空操作。
快速排序的复杂度是O(nlgn),其递归树的表示形式应该为T(n) = 2T(n/2) + O(n)
(比较理想的情况是刚好一分为2，然后问题的规模变小)，但是也不排除会出现 T(n) = T(n-1) + O(n)也就是一边
有n-1个元素一边的这种情况，此时的复杂度达到了O(n2)了，蜕化跟InsertSort一样,所以关键是那个划分的元素的选取，
如果没有选取一个比较恰当的pivotkey的话，可能会造成O(n2)的复杂度，但是快速排序在大多的情况下表现的还是比较的优秀的，
例如当划分为一边为1/10,另一边为9/10, 即为 T(n) = T((1/10)*n) + T((9/10)*n) + O(n)的情况时候，解递归树采用渐进的方法
可以得到其复杂度近似为O(nlgn),（见算法导论中文版 P151），所以快速排序还是比较优秀的一个排序的算法，而且它是在对元素进行原地的排序，
快速排序的随机化版本：
如上已经说过，快速排序的key在于partition，而partition的关键在于对pivotkey的选取，如果没有适当的选取，可能会到最坏的复杂度，
所以此处采用随机化选取那个pivotkey
如下伪算法的实现：
Randomized_Partition(A,p,r){
i = RANDOM(p,r);
Exchange(A[i],A[r]);
return Partition(A,p,r);
}
其他的算法都基本没有改变主要是pivotkey的选取，算法导论中P157中用指示器随机 变量证明了该算法的平均复杂度为O(nlgn)
*/
# include <stdio.h>
# define N 10void Exchange(int * p, int * q){int temp = *p;*p = *q ;*q = temp;
}int Partition(int A[], int p , int r){int pivot = A[r]; //pivot 应该是随机选取的int i = p -1 ;for (int j = p ; j < r ; j ++){if(A[j] <= pivot){i ++ ;Exchange(&A[i],&A[j]);}}Exchange(&A[i+1],&A[r]);return i + 1 ;
}void QuickSort(int A[] ,int p ,int r){if (p < r){int q = Partition(A,p,r);QuickSort(A,p,q-1);QuickSort(A,q+1,r);}
}int main(void){int a [N] = {9,2,10,11,2,8,7,4,3};QuickSort(a,3,8);for (int i = 3 ; i < 9 ; i ++ ){printf("%5d ",a[i]);}return 0;
}