算法-排序算法

剑指offer 第二章-面试需要的基础知识

冒泡排序

遍历数组,将最大的移到最后。逐渐缩小数组范围。

具体步骤: 1. 第一个 for 循环 P=N-1:将最大的数放到最后面 第一趟冒泡,从第一个数开始逐个向后比较,将最大的数向后移动。 2. 第二个 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
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; // 如果flag 没有发生变化,证明上一次的遍历没有发生交换,说明剩余的数组已经排序好了,就不需要缩小数组范围,继续比较了。
}
}

插入排序

插入排序是增加增大比较范围。

从数组中先取一个数;
再取第二个数,与前面的进行比较,如果比前面的小,则交换位置。
再取第三个数,与前面的进行比较,直到找到比它大的数,插入。
依次循环。。

最好情况,本身就是个正序,外循环还是会执行完 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
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; // 这里的 flag 是放在第二个循环里面的,因为找到了位置,就停下来了,后面的排好序的肯定比他大,就不用比较了
}
}
}

对比冒泡排序和插入排序

  • 冒泡排序是从数组末尾到头逐渐有序,插入排序是从头到尾逐渐有序。
  • flag的位置不同。冒泡排序的外循环不一定能执行完,但内循环都会执行对应的次数。插入排序外循环一定会执行完,但内循环不一定。

堆排序

通过选择排序引入堆排序
选择排序:遍历选择最小的元素,放入数组里面。然后在无序序列里面再遍历选择最小元素,循环。。。可见时间复杂度最坏情况: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
//堆排序
/*因为堆排序是完全二叉树,用数组表示的,所以可以把原始序列看成树,然后进行调整*/
void HeapSort(int num[], int N) {
/*build max heap*/
int i,temp;
for (i = 1; i < N; i++) { //从数组下标为1的元素开始,类似于最大堆的插入一样,依次与父节点比较
temp = num[i];// 因为i一直在变化,因此把他保存
for (; num[i] > num[(i-1)/2]; i = (i - 1) / 2)
num[i] = num[(i - 1) / 2]; //把比num[i]小的父节点往下一层移
num[i] = temp;
}
/*delete max and swaps the max with the last one of the unoder sequence*/
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++) { //从数组下标为1的元素开始,类似于最大堆的插入一样,依次与父节点比较
tempp = num[k];// 因为i一直在变化,因此把他保存
for (; num[k] > num[(k - 1) / 2]; k = (k - 1) / 2)
num[k] = num[(k - 1) / 2]; //把比num[i]小的父节点往下一层移
num[k] = tempp;
}
}
}

快速排序

算法概述:分而治之(递归)
快速排序的细节很重要:
- 选主元:中分显然是最好的
- 怎么分成两个独立子集

最好情况: 每次选择的主元位置正好在中分位置, T(N) = O(NlogN)

选主元

随机选主元:随机函数也很浪费时间。。
选头中尾三个数的中位数

这里主元是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 主元所在的位置
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]);

// 再耍个小聪明, 将 pivot 藏在最右边
Swap (&A[Center], &A[Right-1]);

// 只需考虑 A[Left+1]...A[Right-2]
return A[Right-1]; // 返回 pivot

子集划分

调用过上面的 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
#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); //num+left这种写法??
}

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);
//int pivot = Median3(num, 0, N - 1);
//printf("%d ", pivot);
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
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); //num+left这种写法??
}

出现bug,在Linux系统下使用gdb进行调试: 分析出现bug原因: 快速排序,递归的最后会出现 left = right-1 = 0,此时num[]中只有一个元素num[0],因此进入while (num[++i]0就好了,当元素较少的时候采用插入排序~