快速排序的实现与优化代码,C代码库,德仔网

代码语言

代码分类

【C】快速排序的实现与优化

作者:夕阳红树林 / 发布于2012/6/12/ 681

快速排序的时间复杂度达到O(nlgn)，被公认为最快的排序方法之一。在所有同数量级（O(nlgn)）的排序当中，其平均性能最好。它其实是冒泡排序的改进，当一列数据基本有序的时候，快速排序将为蜕化为冒泡排序，时间复杂度为O(n平方）。基本思想是取一个数作为中间数，比它小的都排左边，比它大的都排右边（如果是从大到小排序的话，就反过来），再对每一边用同样的思路进行递归求解。

#include <stdio.h>
#include <stdlib.h>
#include <string.h></div>
<div>/*
* @function randindex
* @remark 产生区间[low,high]上的随机数
*/
int randindex ( int low, int high )
{
return rand () % ( high - low ) + low;
}
<div>/*
* @function swap
* @remark 交换 a 和 b
*/
void swap ( int *pa, int *pb )
{
int tmp = *pa;
*pa = *pb;
*pb = tmp;
}
<div>void quicksort ( int * array_to_sort, int low, int high )
{
if ( low >= high ) return;</div>
<div>/* 
 * 在 [l + 1,h] 区间选取一个随机位置 index，
 * 把本次排序的第一个位置的元素跟 index位置上的元素交换，
 * 避免每次排序 pivot 取的是最大值或最小值，即避免待排数值基本有序
 */
int index = randindex ( low + 1, low );
swap ( array_to_sort + low, array_to_sort + index );</div>
<div>int l = low, h = high;
int pivot = array_to_sort[l];</div>
<div>while ( l < h )
{
while ( l < h && array_to_sort[h] >= pivot ) h--;
array_to_sort[l] = array_to_sort[h];
while ( l < h && array_to_sort[l] <= pivot ) l++;
array_to_sort[h] = array_to_sort[l];
}
array_to_sort[l] = pivot;</div>
<div>quicksort ( array_to_sort, low, l - 1 );
quicksort ( array_to_sort, l + 1, high );
}
<div>int main ()
{
int src[] = {49,38,65,97,76,13,27,49}; 
 
 int i,cnt = sizeof(src)/4; 
 
 quicksort( src, 0, cnt - 1 ); 
 
 //输出 
 for( i = 0; i < cnt; i++ ) printf ( "%d ", src[i] );

printf ( "\n" );
 return 0; 
}

试试其它关键字

　快速排序　

同语言下

可能有用的

夕阳红树林贡献的其它代码(1)

.快速排序的实现与优化