排序算法之快速排序
快速排序基本思想：挖坑填数+分治法
快速排序的分治partition过程有两种方法，一种是上面所述的两个指针索引一前一后逐步向后扫描的方法（算法导论上采用的是这种方法），还有一种方法是两个指针从首位向中间扫描的方法（大多数的人和一般的教材采用的是这第二种首尾向中间扫描法）。本文采用第二种方法。
1，把第一个作为基准，
2，先从后向前找，找到小于的，放在第一个
3，再从前向后找，找到大于的，放在刚刚移过的坑中，然后重复
<pre name="code" class="cpp">#include<stdio.h>
#include<time.h>
#define Length 500
//函数声明
void QuickSort(long*,long,long);
long Partition(long*,long,long);
void Swap(long*,long*);
int main()
{
long L[Length];
long i=0;
printf("请分别输入%d个整数:\n",Length);
for(i=0;i<Length;i++)
{
printf("\n请输入第%d个整数:",i+1);
scanf("%d",&L[i]);
}
printf("\n排序前:");
for(i=0;i<Length;i++)
{
printf("%5d",L[i]);
}
QuickSort(L,0,Length-1);
printf("\n排序后:");
for(i=0;i<Length;i++)
{
printf("%5d",L[i]);
}
printf("\n");
getchar();
getchar();
getchar();
return 0;
}
//算法实现
//快速排序算法是一种递归实现的算法,所以必然要使用额外在堆栈做为辅助空间,堆栈深度与N个结点的
二叉树相同,约为O(logn)
//快速排序算法的时间复杂度为O(nlogn),在平均性能方面目前公认为最好的算法
void QuickSort(long*L,long low,long high)
{
long pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high);
QuickSort(L,low,pivotloc-1);
QuickSort(L,pivotloc+1,high);
}
}
long Partition(long*L,long low,long high)
{
long pivotkey=L[low]; //把第低位做为枢轴位置
while(low<high)
{
//当枢轴右边元素都比枢轴大时,高位左移,直接所
while(low<high&&L[high]>=pivotkey) high--;
Swap(&L[low],&L[high]);
while(low<high&&L[low]<=pivotkey) low++;
Swap(&L[low],&L[high]);
}
return low;
}
//用于交换数据的函数
void Swap(long* a,long* b)
{
long temp;
temp=*a;
*a=*b;
*b=temp;
}
creat by 张飞雪
补充：软件开发 , 其他 ,
