《啊哈！算法》——快速排序

109 阅读 0 评论 72 点赞

我是靠谱客的博主清新咖啡豆，这篇文章主要介绍《啊哈！算法》——快速排序，现在分享给大家，希望可以做个参考。

假设我们对“6，1，2，7，9，3，4，5，10，8”这十个数进行排序（从小到大进行排序）。

首先我们需要随便找一个基准数（一个用来参照的数），一般情况下选取第一个数作为基准数，接下来，需要把这个序列中所有比基准数大的数放在它的右边，比基准数小的数放在它的左边。

初始状态下，数字6在序列的第一位，我们要做的第一步就是把6挪到序列中间的某个位置，假设这个位置是k，以k为分界点，左边的数都小于等于6，右边的书都大于等于6.

类似于冒泡排序，快排也是通过交换的方式把数放到它应该在的位置。

方法很简单，分别从序列“6，1，2，7，9，3，4，5，10，8”两端开始探测。

先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。

这里可以用两个变量i，j，左边的为“哨兵i”，右边的为“哨兵j”。

刚开始时让“哨兵i”站在序列最左边一个数的位置，指向数字6，让“哨兵j”站在序列最左边一个数的位置，指向数字8，如图所示。

此时基数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
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>

void quicksort(int left,int right,int* a)
{

    int i,j,t,temp;
    if(left>right)
    return;


    temp = a[left]; //temp中存放基准数
    i = left;
    j = right;

    while(i != j)
    {
        // 先从右往左找
        while(a[j]>=temp && j>i)
        {
            j--;
        }
        while(a[i]<=temp && i<j)
        {
            i++;
        }
        
        //交换
        if(i<j)
        {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    //将基准数归位
    a[left] = a[i];
    a[i] = temp;
    
    quicksort(left, i-1,a); // 递归 继续处理左边序列
    quicksort(i+1, right,a);// 递归 继续处理右边序列
    
}

int main()
{
    int i =0;
    int n= 0;
    int a[101]={0};
    scanf("%d",&n);
    
    for( i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    
    quicksort(0,n-1,a);

    for( i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
    
    return 0;
}