久违的更新!

最近忙着学习去了,就没怎么更新了~

刷了刷算法题,感觉以前学的东西都快忘光了,于是花了半天时间撸了一篇练习文,顺带练习了一点实现——记得某个函数式语言实现快排只用了一行代码来着。。。以前好玩还印了纹身贴贴身上哈哈哈哈哈哈

好了好了,下面开始讲讲常见的排序算法~

(代码都是自己手工敲的!都调试过,所以应该问题不大!如果有问题可以联系 A@Thoxvi.com 交流!)

冒泡排序

  1. 从第一个开始,前面一个比后面一个大(小)则交换,直到结尾,则最后一个是最大(小)的元素
  2. 继续第二趟——忽略最后一个最大的
  3. 继续第三趟。。。
  4. 直到指向未排序的 index 等于 0,即排序结束

——这玩意儿叫「沉底排序」也是 o98k 的,毕竟最大的一直在向下沉嘛~

算法实现

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

#include <stdio.h>
#include <stdlib.h>

void print(int *data, int n) {
printf("[");
for (int i = 0; i < n; ++i) {
if (i == n - 1) {
printf("%d", data[i]);
} else {
printf("%d,", data[i]);
}
}
printf("]\n");
}

int main() {
int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 2, 1, 0, 4, 5, 6, 7, 8};
int n = sizeof(data) / sizeof(int);

print(data, n);

for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - i-1; ++j) {
if (data[j] > data[j + 1]) {
int tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}
}
}
print(data, n);
return EXIT_SUCCESS;
}

选择排序

  1. 寻找数组中最小的元素,放到第一位
  2. 寻找剩余数组中最小的元素,放到第二位
  3. 寻找剩余数组中最小的元素,放到第三位
  4. 以此类推

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13

data = [5, 4, 2, 6, 7, 13, 5, 62, 34, 62, 1, 7]

print(len(data))
print(data)

for i in range(0, len(data)):
for j in range(i, len(data)):
if data[i] > data[j]:
data[i], data[j] = data[j], data[i]

print(len(data))
print(data)

插入排序

插入排序的左边依然是有序的,但是却不一定是最终位置——因为后面可能还有更小的,导致全部向后移动,一般实现来说,是从 i 向前遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

data = [5, 4, 2, 6, 7, 13, 5, 62, 34, 62, 1, 7]

print(len(data))
print(data)

for i in range(0, len(data)):
i_t = i
for j in range(i, -1, -1): # 从 i 向 0 遍历
if data[i_t] < data[j]:
data[i_t], data[j] = data[j], data[i_t]
i_t -= 1

print(len(data))
print(data)

希尔排序

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。

快速理解(Wikipedia)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

data = [5, 4, 2, 6, 7, 13, 5, 62, 34, 62, 1, 7]

print(len(data))
print(data)

n = len(data)
step = n // 2
while step >= 1:
for j in range(step, n):
i = j
while (i - step) >= 0:
if data[i] < data[i - step]:
data[i], data[i - step] = data[i - step], data[i]
i -= step
else:
break
step //= 2

print(len(data))
print(data)

归并排序

所有的「排序相关」的操作,事实上都是在「merge」的时候完成,而「sort」只是一个拆分的操作

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

data = [5, 4, 2, 6, 7, 13, 5, 62, 34, 62, 1, 7]

print(len(data))
print(data)

def merge(a, b):
l = []

while (len(a) != 0 and len(b) != 0):
if a[0] < b[0]:
l.append(a[0])
a = a[1:]
else:
l.append(b[0])
b = b[1:]

if len(a) != 0:
l += a
else:
l += b

return l

def sort(a):
print(a)
b = a[int(len(a) / 2):]
a = a[:int(len(a) / 2)]

if len(a) == 0 and len(b) == 1: return b

a = sort(a)
b = sort(b)

return merge(a, b)

data = sort(data)

print(len(data))
print(data)

快速排序

随机选取一个数(这里直接选第一个元素了),把数组里大于它的放前面,等于它的放中间(防止去重),小于它的放后面。重复进行直到为空或者长度为1

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

function print(info) {
console.log(info)
}

function sort(data) {
if (data.length === 1) return data;
if (data.length === 0) return data;

tmpList = sort(data.filter(x => x < data[0]));
tmpList = tmpList.concat(data.filter(x => x === data[0]));
tmpList = tmpList.concat(sort(data.filter(x => x > data[0])));

return tmpList;
}

let data = [5, 4, 2, 6, 7, 13, 5, 62, 34, 62, 1, 7];

print(data.length);
print(data);

data = sort(data);

print(data.length);
print(data);

module.exports = sort;

二叉堆结构

概念性的东西

  • 堆的定义:父节点都大于子节点的二叉树,被成为有序堆
  • 有序化:当添加元素,使得不满足堆定义的时候,进行的「使二叉树满足堆定义」的操作
  • 有序化的两种情况
    • 优先级上升:子节点变大,则向上移动
    • 优先级下降:父节点变小,则向下移动
  • 不使用第一个位置——原因是计算简单一点。。。
  • 当 N 到达 2 的幂时,树的高度会 +1
  • 优点
    • 插入元素和删除最大元素的用时仅和队列的大小成对数关系(log n)
  • 多叉堆,修改 N 即可

堆排序

流程

  1. 不断插入数据进入堆,并进行相应的上升下降
  2. 插入完成之后,不断读取最小(大)值,并把它从堆里删除
  3. 最小值组成的数组即排序后的数组

一些复杂度的数据

算法 是否稳定 是否原地排序 时间复杂度 空间复杂度 备注
选择排序 N^2 1 取决于输入的排序状况
插入排序 N 和 N^2 之间 1 取决于输入的排序状况
希尔排序 NlogN?N6/5? 1 取决于输入的排序状况
快速排序 NlogN lgN 运行效率由概率保证
三向快速排序 N 和 NlogN 之间 lgN 运行效率由概率保证,同时也取决于输入的排序情况
归并排序 NlogN N
堆排序 NlogN 1

所以,性能比较好的是时间复杂度为 NlogN 的算法——快排、堆排序、归并等等。