排序算法之快速排序

68 阅读 0 评论 45 点赞

我是靠谱客的博主尊敬大白，这篇文章主要介绍排序算法之快速排序，现在分享给大家，希望可以做个参考。

之前写过了快速排序的算法（快速排序），这里写的与之前的稍有不同，目的主要是为了归纳《算法设计技巧与分析》这本书中的所有算法的代码实现，所以不遗余力的再次总结一下。

伪代码和算法的效率分析直接贴图

划分伪代码（找出快速排序的w位置，使得w左边所有的数小于它，w右边所有的数大于它）

排序伪代码（调用SPLIT划分算法）

效率分析（还是十分可观的）

实现代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#define M 8
void swap(int *a,int *b);
int Split(int *num,int low,int high);
void QuickSort(int *num,int low,int high);
int main(void)
{
	int num[M]={24,33,24,45,12,12,24,12};
	int i=0;
	QuickSort(num,0,M-1);
	for(i=0;i<M;i++)
		printf("%d ",num[i]);
	return 0;
}
//快速排序
void QuickSort(int *num,int low,int high)
{
	if(low<high)
	{
		int w = Split(num,low,high);
		QuickSort(num,low,w-1);
		QuickSort(num,w+1,high);
	}
}
//划分函数
int Split(int *num,int low,int high)
{
	int i = low,x = num[low],j=0;
	for(j = low+1;j<=high;j++)
	{
		if(num[j]<=x)
		{
			i++;   //low~i的数都是小于x的数
			if(i!=j) swap(num+i,num+j);  //i！=j时，说明i~j之间存在数大于x，i已经++，此时num[i]>x，num[j]<=x,所以交换这两个数的值
		}
	}
	swap(num+low,num+i);
	return i; //返回i值，low~i的数小于num[i],i~high的数大于num[i];
}

void swap(int *a,int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}