1 时间表示法O
- 通过O来表示算法的时间复杂度和空间复杂度
2 排序算法
- 常见的排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 计数排序(counting sort)
- 基数排序(radix sort)
- 希尔排序
- 快速排序
- 堆排序
- 桶排序
- 简单排序:冒泡/选择/插入
- 高级排序:快速排序/希尔排序
2.1 冒泡排序
- 运行效率低,最简单
- O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// 1.冒泡排序
ArrayList.prototype.bubbleSort = function () {
for (var i = this.array.length - 1; i >= 0; i--) {
// 根据i的次数比较循环到i位
for (var j = 0; j < i; j++) {
if (this.array[j] > this.array[j + 1]) {
// 交换元素
this.swap(j, j + 1);
}
}
}
}
ArrayList.prototype.swap = function (m, n) {
var temp = this.array[m];
this.array[m] = this.array[n];
this.array[n] = temp;
}2.2 选择排序
- O(N)
- 实现思路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16ArrayList.prototype.selectSort = function () {
/*
寻找最小元素的下标,和当前最小的元素放置的位置进行交换,把最小的元素始终放在最左侧
*/
for (var i = 0; i < this.array.length - 1; i++) {
var min = i;
// 查找最小元素的下标值
for (var j = min + 1; j < this.array.length; j++) {
if (this.array[min] > this.array[j]) {
min = j;
}
}
// 将最小的元素依次放在最左侧
this.swap(min, j);
}
} - 复杂度
2.3 插入排序
- O(N^2)
- 局部有序,从后面的元素中依次取出插入局部有序的序列中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// 3.插入排序
ArrayList.prototype.insertSort = function () {
// 外层循环获取待插入节点
for (var i = 1; i < this.array.length; i++) {
var temp = this.array[i];
//内层循环插入局部有序列表中( 不确定循环的次数,采用while循环)
var j = i;
while (temp < this.array[j - 1] && j > 0) {
//元素向后移动操作
this.array[j] = this.array[j - 1];
j--;
}
this.array[j] = temp;
}
} - 效率
2.4 希尔排序
- 希尔排序是插入排序的一种高效的改进版本,并且效率比插入排序更快
- 每次按照间隔进行分组,排序后的结果重新给新的间隔,直到间隔为1排序结束
- 思路
- 增量的设置
- 实现思路
- 算法的实现对照插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21ArrayList.prototype.shellSort = function () {
//根据长度计算增量
var gap = Math.floor(this.array.length / 2);
// 增量不断减小,大于0就继续排序
while (gap > 0) {
for (var i = gap; i < this.array.length; i++) {
// 保存临时变量
var j = i;
temp = this.array[i];
// 插入排序内部循环(不确定循环的次数采用while)
while (temp < this.array[j - gap] && j > gap - 1) {
this.array[j] = this.array[j - gap];
j -= gap;
}
// 将选出的j位置值设置为temp
this.array[j] = temp;
}
// 重新计算gap的值
gap = Math.floor(gap / 2);
}
} - 希尔排序的总结
- 快速排序在目前所有的排序算法中,最快的一种排序算法
- 当然没有任何一种算法咋任意情况下都是最优的
- 比如希尔排序在某些合适增量和合适N的情况下确实是高于快速排序的
- 在大多数情况下,快排是最好的选择
- 冒泡排序的思想是分而治之,一次性将某个元素放在正确的位置
- 快速排序的特点以及冒泡排序的比较
- 如何选择正确的枢纽(pivot)
- 选择靠近中间的元素,效率是最高的
- 1.选取第一个元素作为枢纽,效率不高
- 2.使用随机数,函数本身就是一个耗性能的过程
- 3.取头中尾的中位数(将最大的放在最后,将倒数第二的放在倒数第二位,前面的按照快排的方式进行排序)
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// 快排,选择枢纽并放在倒数第二的位置
/*
left:第一个元素的下标
right:最后一个元素的下标
- 取出中间下标位置的元素
- 将三个元素进行比较并交换位置
- 将中间位置的元素放在right-1的位置
*/
ArrayList.prototype.midpiovt = function (left, right) {
//取出中间元素的位置
var mid = Math.floor((left + right) / 2)
// 比较三者的大小并交换位置
if (this.array
[left] > this.array[mid]) {
this.swap(left, mid);
}
if (this.array[mid] > this.array[right]) {
this.swap(mid, right);
}
if (this.array[left] > this.array[right]) {
// 交换完成之后最大的元素已经放在最后面
this.swap(left, right);
}
// 将中间的值放在倒数第二的为
this.swap(right - 1, mid);
// 返回枢纽
return this.array[right - 1];
}
// 通过递归的方式实现快排
ArrayList.prototype.quickSort = function () {
this.quick(0, this.array.length - 1);
}
// 递归调用实现
ArrayList.prototype.quick = function (left, right) {
// 结束条件
if (left >= right) {
return;
}
// 获取枢纽
var pivot = this.midpiovt(left, right);
//设置变量保存移动的指针
var i = left;
var j = right - 1;
// 移动位置并进行交换,这里设置死循环
while (true) {
while (this.array[++i] < pivot) { }
while (this.array[--j] > pivot) { }
// i<j则交换
if (i < j) {
this.swap(i, j);
} else {
break;//跳出循环,此时i指向的位置就是需要和枢纽交换的位置
}
}
// 交换位置
this.swap(i, right - 1);
// 分而治之
this.quick(left, i - 1);
this.quick(i + 1, right);
}
- 快速排序的效率
- 快速排序在最坏的情况下,就是每次枢纽的选择都是最左边或者最右边的值,此时的效率等同于冒泡排序
- 最坏情况一般不会出现,我们选择枢纽是选的是中位数
- 快速排序的平均效率
- 平均效率O(N*logN)
- 虽然其他算法也可以达到O(N*logN),但是快排是最好的
本文作者:
SparkParis
本文链接: https://sparkparis.github.io/2020/04/17/%E7%AE%97%E6%B3%951/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!
本文链接: https://sparkparis.github.io/2020/04/17/%E7%AE%97%E6%B3%951/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!