快速排序的基本实现(完整源代码)
以下是快速排序的完整源代码。基本原理是:先将待排序列一分为二,通过逐个比较,将某一元素设置为枢轴pivot,然后将比pivot小的数据换到左边,比pivot大的元素换到右边。一组完成后,将排好的较小部分和较大部分,继续做递归排序。将排好的较小部分再一分为二,同样把较大的部分一分为二,递归到low=high,也就是只有一个元素的时候,结束递归
·
优化版的快速排序算法,请看这里:
http://blog.csdn.net/fengyanglian/article/details/49757629
以下是经典快速排序的完整源代码。
基本原理是:
先将待排序列一分为二,将某一元素设置为枢轴pivot,通过逐个比较,然后将比pivot小的数据换到左边,比pivot大的元素换到右边。
一组完成后,将排好的较小部分和较大部分,继续做递归排序。
也就是,将排好的较小部分再一分为二,同样把较大的部分一分为二,然后将较小部分排序后得到的较较小部分再一分为二······一直递归到low=high,也就是只有一个元素的时候,结束递归。
//快速排序
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10
typedef struct
{
int r[MAXSIZE+1];
int length;
}SqList;
//交换函数
void swap(SqList *L,int i,int j)
{
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}
//将比枢轴pivotkey小的元素放到左边,大的放到右面,然后将pivotkey放入合适的位置
int Partition(SqList *L,int low,int high)
{
int pivotkey;
pivotkey=L->r[low]; //将第一个元素作为枢轴pivotkey
while(low<high) //从表的两端交替向中间扫描
{
while(low<high && L->r[high]>=pivotkey) //从右边起,将比pivotkey小的换到左边
high--;
swap(L,low,high);
while(low<high && L->r[low]<=pivotkey) //从左边起,将比pivotkey大的换到右边
low++;
swap(L,low,high);
}
return low; //low与high相等时,即为枢轴位置
}
//递归函数
void QSort(SqList *L,int low,int high)
{
int pivot;
if(low<high)
{
pivot=Partition(L,low,high); //将表一分为二
QSort(L,low,pivot-1); //低子表继续递归
QSort(L,pivot+1,high); //高子表继续递归
}
}
//初始化函数
int Init(SqList ** L)
{
*L=NULL;
*L=(SqList *)malloc(sizeof(SqList));
if(*L==NULL)
{
return 0;
}
(*L)->length=0;
return 1;
}
//插入函数
void Insert(SqList **L,int data)
{
if(data)
{
(*L)->length++;
(*L)->r[(*L)->length]=data;
}
}
//输出函数
void Printf(SqList *L)
{
int i;
for(i=1;i<=L->length;i++)
{
printf("%d ",L->r[i]);
}
}
//主函数
void main()
{
SqList *L;
int i;
Init(&L);
int a[]={55,44,11,22,33,77,45,68,95,61};
for(i=0;i<10;i++)
{
Insert(&L,a[i]);
}
QSort(L,1,L->length);
Printf(L);
}
以上是最基本的代码,是看《大话数据结构》时根据书上代码编写的,适合最基础的人看,有问题可以评论,同是菜鸟,我们一起讨论嘛~
更多推荐
已为社区贡献1条内容
所有评论(0)