算法搬运之快速排序

快速排序

快速排序是对冒泡排序的改进，主要思想是通过一次排序将序列分成两部分，左边的部分全部小于基准值，右边的部分大于基准值。在这一思想下，有不同的几种实现方式。

1. 比较好理解的版本

/*
 *quickSort
 *这个版本是比较好理解的版本(效率不是最高的)
 *quickSort函数第二个参数是要排序的数组起始下标，第三个参数是结束下标
 *过程：
 *1. 将最左边的数设为val(也即关键字)
 *2. 从i开始向右找比val大的数，找到后停下
 *3. 从j开始向左找比val小的数，找到后停下
 *4. 如果i>=j则离开循环
 *5. 否则：交换当前的两个数
 *6. 对左边递归
 *7. 对右边递归
 */

#include <stdio.h>
#include <time.h>

#define MAX 10
#define SWAP(x, y) {int t=x; x=y; y=t;}

void quickSort(int *a, int left, int right);

int main(void)
{
    int a[MAX] = {0};
    int i;

    srand(time(NULL));

    printf("排序前:\n");
    for (i=0; i<MAX; i++)
    {
        a[i] = rand()%100;
        printf("%d ", a[i]);
    }

    quickSort(a, 0, MAX-1);

    printf("\n排序后:\n");
    for (i=0; i<MAX; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

void quickSort(int *a, int left, int right)
{
    if (left < right)
    {
        int i = left;
        int j = right+1;

        while (1)
        {
            while (i+1<MAX && a[++i]<a[left]);
            while (j-1>-1 && a[--j]>a[left]);

            if (i >= j)
            {
                break;
            }
            SWAP(a[i], a[j]);
        }

        SWAP(a[left], a[j]);

        quickSort(a, left, j-1);
        quickSort(a, j+1, right);
    }
}
  

 

  
 
 

  
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
  
68
  
69
  
70
  
71
  
72
  
73
 

1. 对于上述方法进行改进，将基准值设定为序列中间的数，从中间向两边寻找

/*
 *从中间向两边查找，具体过程类似于容易理解的版本
 */

#include <stdio.h>
#include <time.h>

#define MAX 10
#define SWAP(x, y) {int t=x; x=y; y=t;}

void quickSort(int *a, int left, int right);

int main(void)
{
    int a[MAX] = {0};
    int i;

    srand(time(NULL));

    printf("排序前:\n");
    for (i=0; i<MAX; i++)
    {
        a[i] = rand()%100;
        printf("%d ", a[i]);
    }

    quickSort(a, 0, MAX-1);

    printf("\n排序后:\n");
    for (i=0; i<MAX; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

void quickSort(int *a, int left, int right)
{
    if (left < right)
    {
        int t = a[(left+right)/2];
        int i = left - 1;
        int j = right + 1;

        while (1)
        {
            while (a[++i] < t);
            while (a[--j] > t);

            if (i >= j)
            {
                break;
            }
            SWAP(a[i], a[j]);

        }

        quickSort(a, left, i-1);
        quickSort(a, j+1, right);
    }
}
  

 

  
 
 

  
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
 

1. 再次改进算法。

   有指针left和right，对于right，如果其所指的元素的值大于或者等于基准值，那么指针往左移一位，如果小于基准值，则和基准值交换；同理，对于left，如果left所指元素的值小于或者等于基准值，那么指针往右移一位，如果大于基准值，则和基准值交换。从right开始执行，重复这两步骤，直至left == right为止。

   　　对于基准的选取会影响算法的性能，这里取第一个元素为pivot。

/*
 *效率较高的实现
 */

#include <stdio.h>
#include <time.h>

#define MAX 10
#define SWAP(x, y) {int t=x; x=y; y=t;}

void quickSort(int *a, int left, int right);
int Partition(int *a, int left, int right);

int main(void)
{
    int a[MAX] = {0};
    int i;

    srand(time(NULL));

    printf("排序前:\n");
    for (i=0; i<MAX; i++)
    {
        a[i] = rand()%100;
        printf("%d ", a[i]);
    }

    quickSort(a, 0, MAX-1);

    printf("\n排序后:\n");
    for (i=0; i<MAX; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

int Partition(int *a, int left, int right)
{
    int pivot = a[left];
    while (left < right)
    {
        while (left < right && a[right] >= pivot)
        {
            --right;
        }
        a[left] = a[right];
        while (left < right && a[left] <= pivot)
        {
            ++left;
        }
        a[right] = a[left];
    }

    return left;
}

void quickSort(int *a, int left, int right)
{
    int pivot;

    if (left < right)
    {
        pivot = Partition(a, left, right);
        quickSort(a, left, pivot-1);
        quickSort(a, pivot+1, right);
    }

}
  

 

  
 
 

  
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
  
68
  
69
  
70
  
71
 

来源：http://www.cnblogs.com/RootJie/archive/2012/02/13/2349649.html

文章来源: dreamlife.blog.csdn.net，作者：DreamLife.，版权归原作者所有，如需转载，请联系作者。

原文链接：dreamlife.blog.csdn.net/article/details/50969554