交换排序——冒泡排序、快速排序

Published on:
Tags: 数据结构 排序

算法思想#

两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

两种交换排序方法#

  1. 冒泡排序
  2. 快速排序

冒泡排序#

基本思想

把待排序记录在逻辑上分成有序区和无序区，一开始有序区没有记录，无序区有 $n$ 个记录。

通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录如气泡一般逐渐往上漂浮 直至 水面。
$n$ 个元素排序，需要 $n-1$ 趟冒泡，有序区逐渐扩大到全局有序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//  冒泡排序
void BubbleSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    //  n个记录，外层循环需要遍历n-1次，最后一个记录自然有序
    for (i = 0; i < n-1; i++)
    {
        for (j = n-1; j > i; j--)
        {
            if (R[j-1].key > R[j].key)
            {
                tmp = R[j-1];
                R[j-1] = R[j];
                R[j] = tmp;
            }
        }
        printf("%d \n",i);
    }
}

性能评价

时间复杂度：$O(n^2)$

稳定性：稳定

冒泡排序 优化版#

基本思想

无序区中记录 冒泡 的过程，会逐渐把无序区里的记录变得有序，所以假如有 $n$ 个无序记录，一般情况下不需要 $n-1$ 趟冒泡就可以使全局达到有序。

普通冒泡排序，需要9趟冒泡排序：

1
2
3
4
5
6
7
8
9
10
11
12
排序前：1 4 6 8 0 2 5 7 9 3 
冒泡排序 ... 
0 
1 
2 
3 
4 
5 
6 
7 
8 
排序后：0 1 2 3 4 5 6 7 8 9

优化版冒泡排序，需要6趟冒泡排序就可以使全局记录有序：

1
2
3
4
5
6
7
8
9
排序前：1 4 6 8 0 2 5 7 9 3 
冒泡排序 改进版 ... 
0 
1 
2 
3 
4 
5 
排序后：0 1 2 3 4 5 6 7 8 9

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//  冒泡排序 改进版
void BubbleSort_v2(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    //  n个记录，外层循环需要遍历n-1次，最后一个记录自然有序
    for (i = 0; i < n-1; i++)
    {
        int flag = 1;
        for (j = n-1; j > i; j--)
        {
            if (R[j-1].key > R[j].key)
            {
                tmp = R[j-1];
                R[j-1] = R[j];
                R[j] = tmp;

                flag = 0;
            }
        }
        printf("%d \n",i);
        if (flag) break;
    }
}

性能评价

时间复杂度：$O(n^2)$

稳定性：稳定

快速排序#

基本思想

在待排序的 $n$ 个记录中任取一个记录（通常取第一个记录）作为基准，把该记录放入适当位置后，数据序列被此记录划分成两部分，分别是比基准小和比基准大的记录。再对基准两边的序列用同样的策略进行操作。

代码

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
//  快速排序 
void QuickSort(RecType R[],int left,int right)
{
    int i = left;
    int j = right;
    RecType tmp;

    //  至少两个元素参与排序
    if (left >= right) return; 
    
    //  第一个元素最为基准元素
    tmp = R[i];
    while (i < j)
    {
        while (i < j && R[j].key >= tmp.key)
            j--;
        R[i] = R[j];
        
        while (i < j && R[i].key <= tmp.key)
            i++;
        R[j] = R[i];
    }

    //  基准元素找到了正确位置
    R[i] = tmp;
    QuickSort(R,left,i-1);
    QuickSort(R,i+1,right);
}

性能评价

时间复杂度：$O(nlog_2n)$

稳定性：不稳定

完整代码#

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <stdio.h>

typedef int KeyType;
typedef char InfoType[10];

typedef struct
{
    KeyType key;
    InfoType data;
} RecType;

void DisRecType(RecType R[],int n);
void BubbleSort(RecType R[],int n);
void BubbleSort_v2(RecType R[],int n);
void QuickSort(RecType R[],int left,int right);

//  交换排序
int main()
{
    int n = 10;
    KeyType a[] = {1,4,6,8,0,2,5,7,9,3};
    RecType R[10];
    for (int i = 0; i < n; i++)
        R[i].key = a[i];

    printf("排序前：");
    DisRecType(R,n);

    printf("冒泡排序 ... \n");
    BubbleSort(R,n);

    printf("冒泡排序 改进版 ... \n");
    BubbleSort_v2(R,n);

    printf("快速排序 ... \n");
    QuickSort(R,0,n-1);

    printf("排序后：");
    DisRecType(R,n);
}

// 输出序列
void DisRecType(RecType R[],int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ",R[i].key);

    printf("\n");
}

//  冒泡排序
void BubbleSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    //  n个记录，外层循环需要遍历n-1次，最后一个记录自然有序
    for (i = 0; i < n-1; i++)
    {
        for (j = n-1; j > i; j--)
        {
            if (R[j-1].key > R[j].key)
            {
                tmp = R[j-1];
                R[j-1] = R[j];
                R[j] = tmp;
            }
        }
        printf("%d \n",i);
    }
}

//  冒泡排序 改进版
void BubbleSort_v2(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    //  n个记录，外层循环需要遍历n-1次，最后一个记录自然有序
    for (i = 0; i < n-1; i++)
    {
        int flag = 1;
        for (j = n-1; j > i; j--)
        {
            if (R[j-1].key > R[j].key)
            {
                tmp = R[j-1];
                R[j-1] = R[j];
                R[j] = tmp;

                flag = 0;
            }
        }
        printf("%d \n",i);
        if (flag) break;
    }
}

//  快速排序 
void QuickSort(RecType R[],int left,int right)
{
    int i = left;
    int j = right;
    RecType tmp;

    //  至少两个元素参与排序
    if (left >= right) return; 
    
    //  第一个元素最为基准元素
    tmp = R[i];
    while (i < j)
    {
        while (i < j && R[j].key >= tmp.key)
            j--;
        R[i] = R[j];
        
        while (i < j && R[i].key <= tmp.key)
            i++;
        R[j] = R[i];
    }

    //  基准元素找到了正确位置
    R[i] = tmp;
    QuickSort(R,left,i-1);
    QuickSort(R,i+1,right);
}