快速排序(Quick-Sort)
快速排序的主要思想是根据一个基准数(一般是待排序集中第一个元素)将一个待排序集分成左右两部分，其中左半部分数据集比右半部分数据集均要小或大，接下来，对左和右半部分按照相同的方法分别再划分成左右两部分，一直到左右两部分只剩下一个元素时，递归结束。
分析：快速排序的时间复杂度为o(nlogn)，空间复杂度为o(1)，该算法是一个不稳定的排序算法(当基准元素与相同值进行交换时会破坏稳定性)。
附源程序代码：
#include “stdio.h”
#include “stdlib.h”
void print(int data[],int len)
{
for(int i=0;i<len;i++)
printf(“%d “,data[i]);
printf(“\n”);
}
void quick_sort(int data[],int left,int right)
{
if(left
{
while(i
j—;
if(i<j)
data[i++]=data[j];
while(i<j&&data[i]<=base)
i++;
if(i<j)
data[j—]=data[i];
}
data[i]=base;
quick_sort(data,left,i-1);
quick_sort(data,i+1,right);
}
}
int main(void)
{
int len=10;
int data[10]={72,6,57,88,60,42,83,73,48,85};
print(data,len);
quick_sort(data,0,len-1);
print(data,len);
return 0;
}
亦凉
蔚落
还没有评论，来说两句吧...