简单算法(三)

快速排序

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

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

算法难点:

  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;
}

运行结果: