偶看新闻ga 164 pdf:算法六：快速排序（O(nlogn)）
来源：百度文库 编辑：偶看新闻 时间：2024/05/12 15:39:23
1. 快速排序
思想：在当前无序区R[0..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[0..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[0..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[0..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。
适用范围：有大量数据的文件，它是目前内部排序算法中的最快。
复杂度：平均：
最坏：O(n^2)
稳定性：不稳定
程序：
template
void QuickSort(T *A, int n)
{
QSort(A,0,n-1);
}
template
void QSort(T *A, int left, int right)
{
int i,j;
if(left
{
i=left;
j=right+1;
do
{
do i++;
while(A[i]
do j--;
while(A[j]>A[left]);
if(i
swap(A[i],A[j]);
}
while(i
swap(A[j],A[left]);
QSort(A,left,j-1);
QSort(A,j+1,right);
}
}