快速排序的基本思想与代码实现-蒲公英云

快速排序的基本思想与代码实现

一、思想

1，先选一个“标尺”，我们通常选左边第一个
2，用它把整个队列过一遍筛子，
3，以保证：其左边的元素都不大于它，其右边的元素都不小于它。
4，这样，排序问题就被分割为两个子区间。

5，再分别对子区间排序就可以了。

二、代码

C++ Code

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

#include <stdio.h>

void swap(
int a[],
int i,
int j)

{


int t = a[i];

    a[i] = a[j];

    a[j] = t;

}

int partition(
int a[],
int p,
int r)

{


int i = p;


int j = r +
1;


int x = a[p];


while(
1)

    {


while(i < r && a[++i] < x);
///从左边找比标尺大的数

while(a[—j] > x);
///从右边找比标尺小的数

if(i >= j)
///当两个位置相等，表示已经全部找完

break;

        swap(a, i, j);

    }


///扫描完成，枢轴到位
    swap(a, p, j);


return j;

}

///递归过程

void quicksort(
int a[],
int p,
int r)

{


if(p < r)

    {


int q = partition(a, p, r);

        quicksort(a, p, q -
1);

        quicksort(a, q +
1, r);

    }

}

int main()

{


int i;


int a[] = {
5,
13,
6,
24,
2,
8,
19,
27,
6,
12,
1,
17};


int N =
12;

    quicksort(a,
0, N -
1);


for(i =
0; i < N; i++)

        printf(
“%d ”, a[i]);

    printf(
“\n”);


return
0;

}