如何写出一个较好的快速排序程序

首先要写正确。通常使用递归实现。其递归相当于二叉树展开，因此如果要用迭代实现的话需要使用一个队列来保存后续遍历信息。

快速排序需要找到一个pivot值，如果顺序选择pivot则易造成N^2的复杂度，如果使用随机数则效果最好，但开销又太大，采取三数中值法比较合适。三数中值法指的是选取第一个值，最后一个值，数组中间的值的中值。有文献表明可以提升5%的运行时间。

当数组长度较小时，如10个元素以下，最好使用插入排序或者选择排序完成，以防止复杂度常数因子过大或多次函数调用带来的开销。而递归到底层数组长度总是会变小的，因此这么做非常有必要。

在合并前后两部分数组时，采用两边夹方法，在前后两部分各找到一个大于和小于的值再交换。相比通常情况下找到比pivot小的值就进行交换，能提高运行效率。

第一遍 【12】 31 54 65 32 34 45 68 75 85 43 77 98第二遍 12 【31】 54 65 32 34 45 68 75 85 43 77 98第三遍 12 31 32 34 45 43 【54】 98 77 85 75 68 65第四遍 12 31 【32】 34 45 43 54 98 77 85 75 68 65第五遍 12 31 32 【34】 45 43 54 98 77 85 75 68 65第六遍 12 31 32 34 43 【45】 54 98 77 85 75 68 65第七遍 12 31 32 34 【43】 45 54 98 77 85 75 68 65 （左边区间所有递归完成，开始右边区间逐一递归）第八遍 12 31 32 34 43 45 54 65 68 75 85 77 【98】 第九遍 12 31 32 34 43 45 54 【65】 68 75 85 77 98第十遍 12 31 32 34 43 45 54 65 【68】 75 85 77 98第十一遍 12 31 32 34 43 45 54 65 68 【75】 85 77 98第十二遍 12 31 32 34 43 45 54 65 68 75 77 【85】 98第十三遍12 31 32 34 43 45 54 65 68 75 【77】 85 98快速算法每次取当前无序区的第一个记录为基准，首先取12作为tep量，起始位置i=0，终止位置j=12.最外层循环，只要i 不等于 j 就扫描，内层循环，首先从右向左扫描，找到第一个小于tep的值，再交换这个值和tep，这样tep的左边都是比他小的数，再从左向右扫描，找到第1个大于tep的值，与tep交换，这样右边都是比tep大的数。接下来，递归此程序，用同样方法快速排序那个tep值的左区间和右区间。可以看做是，先得出无序区第一个在此序列里应有的位置，再依此位置为轴，排序左右区间，又分别得出左右无序区间的第一个值在序列里的应有位置。

冒泡

int i,j,f1=0,f2=0

int a[N],b[N],t

for(i=1i<N,i++) //冒泡

for(j=i+1,j<N,j++)

{

if(a[i]<a[j])

{

t=a[i]

a[i]=a[j]

a[j]=t

}

f1++

}

void QuickSort(int e[], int first, int end) //快速排序，是递归函数

{

int i=first,j=end,temp=e[first]

while(i<j)

{

while(i<j &&e[j]>=temp)

j--

e[i]=e[j]

while(i<j &&e[i]<=temp)

i++

e[j]=e[i]

}

e[i]=temp

if(first<i-1)

QuickSort(e,first,i-1)

if(end>i+1)

QuickSort(e,i+1,end)

}

---