快速排序
2012-12-28 22:30:12 最后更新: 2015-08-06 16:49:04 访问数量：891
概述
快速排序算是最常用的排序算法了，过程有些复杂，不过只要记住这个排序算法的思路是：每次循环结束的时候，基准元素左侧的所有元素值都小于他，右侧的所有元素值都大于他，之后对左右两个子序列分别进行递归，这样就很好理解了
这个算法的最差时间复杂度为O(n*n)，平均时间复杂度为O(nlogn)，因为只有在完全逆序的情况下才会出现最差的情况，所以这个时间复杂度是完全可以接受的，并且也由此衍生出随机化的改进算法
而快速排序的空间复杂度为O(1)，因此，即使在慢速的存储器中运行，性能依然优秀
其具体过程，我在面试中多次被问到，以我的一次交谈内容为例，即可说明：
"那你用快速排序排一下3 1 5 2 4 ,可以吧?"
我立即一笑:"好的,没有问题!首先i为0,j为1,基准是3,j位置上的1比基准3小,所以++i,++j,i为1指向1,j为2指向5"
"你这和刚才有什么区别?"
我一看对方不耐烦了,马上说"马上就可以看出区别了,现在j指向5,5比基准3大,于是++j,i不加"
"为什么不加?"
"因为i指向的是比基准小的最后一个元素,而j是寻找右面比基准大的元素,这之后,j指向2,这个时候,发现2比基准3小,于是要把i+1,然后i和j换,因为i是比基准小的最后一个元素,所以i+1以后指向的是第一个比基准大的元素,这个比基准大的元素和j指向的比基准小的元素交换以后i还是指向比基准小的最后一个元素,现在序列变成了3 1 2 5 4,然后j++以后指向4,4比基准3大,i不动,j++,超出范围,过程结束,基准和i换,就变成了1 2 3 5 4,现在,基准3左侧的元素都比他小,右侧的元素都比他大,之后对他左侧的1 2 右侧的 5 4分别进行递归运算,完成上述操作即可"
代码
/*
* file: main.c
* author: 龙泉居士
* date: 2012-12-28 22:29
*/
#include <stdio.h>
#include "function/function.h"
int quick_sort (int *array, int beg, int end)
{
if (beg >= end) return 0;
int i=beg, j;
for (j=i+1; j<=end; ++j)
if (array[j] <= array[beg])
{
++i;
exch(array, i, j);
}
exch(array, beg, i);
quick_sort (array, beg, i-1);
quick_sort (array, i+1, end);
return 0;
}
int main ()
{
int i, n=0;
int array[256];
printf ("Please input numbers, end by 9999:\n");
while (1)
{
scanf ("%d", &array[n]);
if (array[n] == 9999)
break;
++n;
}
if (quick_sort(array, 0, n-1))
return -1;
for (i=0; i!=n; ++i)
printf ("%d ", array[i]);
printf ("\n");
return 0;
}
/*
* file: function.h
* author: 龙泉居士
* date: 2012-12-28 22:30
*/
#ifndef FUNCTION_H_20121228
#define FUNCTION_H_20121228
int exch (int *array, int a, int b);
#endif
/*
* file: function.c
* author: 龙泉居士
* date: 2012-12-28 22:31
*/
#include <stdio.h>
#include "function.h"
int exch (int *array, int a, int b)
{
if (array[a]!=array[b])
{
if (array == NULL)
{
printf ("build_heap param error");
return -1;
}
array[a] = array[a]^array[b];
array[b] = array[a]^array[b];
array[a] = array[a]^array[b];
}
return 0;
}