快速排序
浏览数：23 /
时间：2015年06月08日
快速排序（Quicksort）是对冒泡排序的一种改进。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
int quickSort(int a[], int low, int high)
{
int nKey=a[low];
while(low<high)
{
while(low<high && nKey<=a[high]) high--;
a[low]=a[high];
while(low<high && nKey>=a[low]) low++;
a[high]=a[low];
}
a[low]=nKey;
return low;
}
void sort(int a[], int low, int high)
{
if(low<high)
{
int nRet=quickSort(a, low, high);
quickSort(a, low, nRet-1);
quickSort(a, nRet+1, high);
}
}
#算法复杂度
#1.如果每次划分，划分出了类似于{a[0]};{a[1]----a[n]};即划分出的两个序列为序列1{1个元素}、序列2{n个元素}；则快速排序将退化为
冒牌排序，最坏的时间复杂度为O(n2);
#2.如果每次划分，划分出的两个序列的元素个数相同；最优时间复杂度为O(nlogn);
#3.nKey的选取，可用数组中的第1个元素，中间的元素，最后1个元素的中间值；来进行选取；选择3个元素中最接近中间值得元素最为nKey.
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
