秒懂快速排序
浏览数：21 /
时间：2015年06月08日
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来
快速排序核心："基准"（pivot），分区（partition），交换（swap），递归（recursive）。
快速排序实现：
/*
*author: booirror(at)163(dot)com
*date: 2015/4/28
*/
#include <stdio.h>
void swap(int a[], int n, int m)
{
if (n == m) return;
int tmp = a[n];
a[n] = a[m];
a[m] = tmp;
}
void qsort(int a[], int n)
{
int i, j;
int last = 0;
if (n < 2) return;
swap(a, 0, n/2);
for (i = 1; i < n; i++) {
if (a[i] < a[0]) {
swap(a, ++last, i);
}
}
swap(a, 0, last);
qsort(a, last);
qsort(a+last+1, n-last-1);
}
int main()
{
int i = 0;
int ra[10] = {12, 23, 55, 33, 1, 25, 32, 99, 77, 11};
qsort(ra, 10);
while (i < 10)
printf(" %d", ra[i++]);
puts("\n");
int ar[6] = {4, 22, 11, 77, 33, 41};
qsort(ar, 6);
for (i=0; i < 6; i++) {
printf("%d ", ar[i]);
}
puts("\n");
return 0;
}快速排序的过程动画：
（完）
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
