简单算法(三)

发表于 | 分类于 | 阅读次数 |

快速排序

思路:对一组数据找到一个基准数，用这个基准数做参考，小于它的放右边(左边)，大于它的放左边(右边),然后左右两边同样实现这样的排序,直到都符合规则

直接上原书的图《坐在马桶上学算法》

算法难点:

  1. 使用左右两边的数据
  2. 以左边的数作为基准数
  3. 先从右边开始找比基准数小的点(从大到小排序)
  4. 当右边找到比基准数小的点，左边找到比基准数大的点时，交换两个位置的值，然后继续
  5. 当左右两点位置相等时，将该位置点与左边 1 位置交换
  6. 左右两边分别重复上面的步骤，直到一边没有数据只剩下一个结束这样的循环

这是具体的一个交换流程

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
47
48
49
50
51
52
53
54
55
#include <stdio.h>
int a[101],n; // 定义全局变量
void quicksort(int left,int right)
{
	int i,j,t,temp;
	if(left>right)
	{
		return;
	}
	temp=a[left];//temp 中存的就是基准数
	i=left;
	j=right;
	while(i!=j)  //两边不想交就一直循环
	{
		while(a[j]>=temp&&i<j)  //顺序很重要 先从右边找
		{
			j--;
			//在找左边
		}
		while(a[i]<=temp && i<j)
		{
			i++;
		}
		if(i<j)
		{
			t=a[i];
			a[i]=a[j];
			a[j]=t;
		}
	}
	// i等于j
	a[left]=a[i];   //最左边为停止的数字
	a[i]=temp;    //停止的为基准数
	quicksort(left,i-1);   //左边的继续
	quicksort(i+1,right); //右边的继续
}
int main(void)
{
	int x;
	printf("请输入需要排序的个数:");
	scanf("%d",&n);
	for(x=1;x<=n;x++)
	{
		scanf("%d",&a[x]);
	}
	quicksort(1,n); //快速排序调用
	for(x=1;x<=n;x++)
	{
		printf("%d ",a[x]);
	}
	getchar();
	return 0;
}

运行结果:

(*^▽^*)