剑指offer 第二章-面试需要的基础知识
冒泡排序
遍历数组，将最大的移到最后。逐渐缩小数组范围。
具体步骤：
- 第一个 for 循环 P=N-1：将最大的数放到最后面
第一趟冒泡，从第一个数开始逐个向后比较，将最大的数向后移动。
- 第二个 for 循环 P=N-2：将次大的书放到倒数第二个位置上
第二趟冒泡，从第一个数开始逐个向后比较，比较到第二个位置为止
复杂度分析：
最好情况,数组本身是顺序的，那么外循环只需要执行一次就会发现 flag 标识没变 T=O(N),
最差情况，数组本身是倒序的，那么外循环会执行 N-1 次，总的计算量是 (N-1 + N-2 +…+ 1), 则时间复杂度是 T=O(N^2)
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
|
void Bubble_sort(int num[], int N)
{
for ( int P=N-1; P>0; P--)
{
int flag = 0;
for (int i=0; i<P; i++)
{
if(num[i] > num[i+1])
{
int temp = num[i];
num[i] = num[i+1];
num[i+1] = temp;
flag = 1;
}
}
if (flag == 0) break;
}
}
|
插入排序
插入排序是增加增大比较范围。
从数组中先取一个数;
再取第二个数，与前面的进行比较，如果比前面的小，则交换位置。
再取第三个数，与前面的进行比较，直到找到比它大的数，插入。
依次循环。。
最好情况，本身就是个正序，外循环还是会执行完 N-1 次，但是内循环对应的只需要只执行一次，就会发现增加的数位置正确。所以总的复杂度还是 O(N)
最差情况，本身是个倒序的, 外循环会执行 N-1次， 内循环对应次数，所以总的是 O(N^2).
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
|
void InsertOrder(int num[], int N)
{
for(int i=1; i<N; i++)
{
for(int j=i; j>0; j--)
{
int flag = 0;
if (num[j] < num[j-1])
{
int temp = num[j];
num[j] = num[j-1];
num[j-1] = temp;
flag = 1;
}
if(flag == 0) break;
}
}
}
|
对比冒泡排序和插入排序
堆排序
通过选择排序引入堆排序
选择排序：遍历选择最小的元素，放入数组里面。然后在无序序列里面再遍历选择最小元素，循环。。。可见时间复杂度最坏情况：O(N2)
上图可以看出 for 循环要执行 N 次，总的复杂度取决于寻找最小元。看到最小元，自然想到最小堆。最小堆的根节点就是最小值。
堆排序算法1：
针对选择排序的改进，怎么样找到最小元？可以将原序列调整成最小堆(时间复杂度是线性的 O(N))，然后依次弹出根结点 O(NlogN)。再将弹出的序列复制到原序列里面 O(N)。可见时间复杂度为：T(N)=O(N)+O(Nlog(N))+O(N)=O(Nlog(N))
但是原数组占有O(N)内存，调整成最小堆后弹出的序列存储也需要O(N)内存，因此，空间复杂度上需要额外的O(N)
堆排序算法2
先调整成最大堆O(N),再将根结点与最后一个元素交换位置O(logN)，然后再将前N-1个元素调整成最大堆，依次循环。。最后直接就是排序的结果，而不用重新占用内存空间。时间复杂度：O(N)+O(Nlog(N))…但陈姥姥给的是下面这样…so？
代码实现
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
|
void HeapSort(int num[], int N) {
int i,temp;
for (i = 1; i < N; i++) {
temp = num[i];
for (; num[i] > num[(i-1)/2]; i = (i - 1) / 2)
num[i] = num[(i - 1) / 2];
num[i] = temp;
}
int j,k, tempp;
for (j = N - 1; j > 0; j--) {
tempp = num[0];
num[0] = num[j];
num[j] = tempp;
for (k = 1; k < j; k++) {
tempp = num[k];
for (; num[k] > num[(k - 1) / 2]; k = (k - 1) / 2)
num[k] = num[(k - 1) / 2];
num[k] = tempp;
}
}
}
|
快速排序
算法概述：分而治之（递归）
快速排序的细节很重要：
最好情况： 每次选择的主元位置正好在中分位置， T(N) = O(NlogN)
选主元
随机选主元：随机函数也很浪费时间。。
选头中尾三个数的中位数
这里主元是
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
|
int Center = (Left + Right) / 2;
if (A[Left] > A[Center])
Swap (&A[Left], &A[Center]);
if (A[Left] > A[Right])
Swap (&A[Left], &A[Right]);
if (A[Center] > A[Right])
Swap (&A[Center], &A[Right]);
Swap (&A[Center], &A[Right-1]);
return A[Right-1];
|
子集划分
调用过上面的 Median3 函数之后得到的数组是： {8, 1, 4, 9, 0, 3, 5, 2, 7, 6}， Left 和 Right 不用考虑了，已经在正确的子集了，pivot 也放在了剩下部分的最右边。
这里 i j 是两个指针，其实就是元素下标。当两边指针i遇到比pivot大式，停止。转去考虑右边的指针j，当j遇到小于pivot的数时也停止。此时两边都发出红色警告（也就是左边大于pivot， 右边小于pivot），则交换两边的数。
递归：对左子集重复上面的操作，对右子集重复上面的操作。
快速排序为什么快？
因为选择了一个主元，然后划分完子集后，这个主元就处于它最终所在的位置上。
比如插入排序的数的位置都是临时的，插入排序新增加一个数，从后往前逐渐对比，发现比前面的小的话，相当于把前面的数都往后挪。
如果有两元素正好等于 pivot 怎么办？
停下来交换，这样的目的是让 pivot 最终的位置更靠近数组中分的位置。之前做过时间复杂度分析时，我们知道这样的时间复杂度是最小的。
小规模数据的处理
当递归的数据规模较小时，则停止递归，使用插入排序。
代码实现
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
|
#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
void InsertSort(int num[], int N) {
int i, j, temp;
for (i = 1; i < N; i++) {
for (j = i; j > 0; j--) {
int flag = 0;
if (num[j] < num[j - 1]) {
temp = num[j];
num[j] = num[j - 1];
num[j - 1] = temp;
flag = 1;
}
if (flag == 0) break;
}
}
}
void swap(int num[],int m, int n) {
int temp;
temp = num[m];
num[m] = num[n];
num[n] = temp;;
}
int Median3(int num[], int left,int right) {
int median = (left + right) / 2;
if (num[left] > num[median])
swap(num,left,median);
if (num[left] > num[right])
swap(num, left, right);
if (num[median] > num[right])
swap(num, right, median);
swap(num,median,right-1);
return num[right - 1];
}
void Quick_sort(int num[],int left,int right) {
int Cutoff = 10;
if (Cutoff <= right - left) {
int pivot;
pivot = Median3(num, left, right);
int i = left, j = right - 1;
for (;;) {
while (num[i++]<pivot) {}
while (num[j--]>pivot) {}
if (i < j)
swap(num,i,j);
else break;
}
swap(num,i,right-1);
Quick_sort(num, left, i - 1);
Quick_sort(num, i + 1, right);
}
else
InsertSort(num + left, right - left + 1);
}
void QuickSort(int num[], int N)
{
Quick_sort(num, 0, N - 1);
}
int main() {
int N, i, j;
scanf_s("%d", &N);
int *num = (int*)malloc(N * sizeof(int));
for (i = 0; i < N; i++) {
scanf_s("%d", &num[i]);
}
QuickSort(num, N);
printf("%d", num[0]);
for (j = 1; j < N; j++)
printf(" %d", num[j]);
}
|
在此过程中出现的问题：
在快速排序的C代码出现了“段错误”Segmentation fault (core dumped)
错误代码：
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
|
void Quick_sort(int num[],int left,int right) {
int Cutoff = 0;
if (Cutoff <= right - left) {
int pivot;
pivot = Median3(num, left, right);
int i = left, j = right - 1;
for (;;) {
while (num[++i]<pivot) {}
while (num[--j]>pivot) {}
if (i < j)
swap(num,i,j);
else break;
}
swap(num,i,right-1);
Quick_sort(num, left, i - 1);
Quick_sort(num, i + 1, right);
}
else
InsertSort(num + left, right - left + 1);
}
|
出现bug，在Linux系统下使用gdb进行调试：
分析出现bug原因：
快速排序，递归的最后会出现 left = right-1 = 0,此时num[]中只有一个元素num[0],因此进入while (num[++i]<pivot)循环时，++i会导致内存越界。
解决办法是cutoff>0就好了，当元素较少的时候采用插入排序~