归并排序相关
最近在总结排序算法相关知识,发现归并排序有很多实现方式,自上而下的归并,自底向上的归并,自然归并。这里简单总结一下。
# 归并排序
必须使额外的O(n)空间来完成排序,时间的效率比空间的效率重要太多,绝大多数情况下都是时间优先。
# 递归归并
# 算法思路
我们使用分治的思想,将待排数组分成两组,每一组排序完成后再合并,我们可以将分组再分组,一直分到每一组只有一项为止,这个时候每组都只有一个元素,那么他们每组都是有序的,分半->分半->再分半->分到每组只剩下一个元素的时候就回溯 需要分半的次数:log(n)
归并是:先复制数组arr的一份副本,然后拿这个副本数组aux中的i和j来比较,谁小谁先进真正的arr
对于子组向上合并的时候的,不要再原数组上进行交换操作,这里要将其复制一份。进行比较后赋值。具体流程可以看下图。
我们可以看到,我们进行每一次的合并操作的时候,我们都要对三个位置进行标记。维护合并时的这三个标记变量,是实现归并排序的关键。
// 入口函数
function mergeSort (arr) {
__mergeSort(arr,0,arr.length-1)
return arr
}
// 递归使用归并排序,对arr[l...r]的范围进行排序
function __mergeSort(arr,l,r) {
// 递归出口
if (l >= r) {
return
}
let mid = Math.floor((l + r) / 2)
__mergeSort(arr, l, mid) // T(N/2)
__mergeSort(arr, mid+1, r) // T(N/2)
__merge(arr,l,mid,r) // O(N)
// T(N) = 2T(N/2) + O(N) = O(NlogN)
}
function __merge(arr,l,mid,r) {
let aux = new Array(r-l+1)
let i = 0
let p1 = l
let p2 = mid + 1
// 谁小往临时数组里就添谁的过程
while (p1 <=mid && p2 <=r) {
aux[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]
}
// 临界过程
while(p1<=mid) {
aux[i++] = arr[p1++]
}
while (p2<=r) {
aux[i++] = arr[p2++]
}
for (let i = 0;i<aux.length;i++) {
arr[l+i] = aux[i]
}
}
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
# 性能测试
let arr = util.randomArray(50000,0,1000)
let arr1 = arr.slice()
let arr2 = arr.slice()
util.testSort('归并', mergeSort, arr1)
util.testSort('插入', insertionSort, arr2)
// 归并: 15.462ms
// 插入: 686.056ms
let arr = util.generateNearlyOrderedArray(50000, 10)
let arr1 = arr.slice()
let arr2 = arr.slice()
util.testSort('归并', mergeSort, arr1)
util.testSort('插入', insertionSort, arr2)
// 归并: 18.331ms
// 插入: 4.117ms
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
可以看到,当处理无序用例的时候,归并排序比插入排序的效率高很多,但是当处理近乎有序的数组的时候,又是相反的结果。
# 优化
# 一,控制__merge条件
// 改进 增加merge条件
function __mergeSort(arr, l, r) {
if (l >= r) {
return
}
let mid = Math.floor((l + r) / 2)
__mergeSort(arr, l, mid)
__mergeSort(arr, mid + 1, r)
// 因为两块都是有序的,如果我们的前者的最大值比后者的最小值还要小,说明此时已经有序
if (arr[mid]>arr[mid+1])
__merge(arr, l, mid, r)
}
2
3
4
5
6
7
8
9
10
11
12
我们给__merge
函数的执行加上一个条件,这样一个简单的控制,就是的我们的归并排序在处理近乎有序的情况下,比之前的快了非常多。
使用时酌情考虑,以为加了一个条件就代表着多了一次判断,对性能有损耗,但是如果我们知道我们要处理的数据有很多有序的情况下,还是建议加上这一判断条件比较合适。
# 二,递归到底情况
现在我们的归并排序是递归到只有一个元素的时候返回,事实上,当我们的递归到元素量很小的时候,我们可以转而使用插入排序。
- 元素量比较小的时候,元素近乎有序的概率就会增加。此时插入排序有优势。
- 插入排序最坏时间复杂度是n^2级别的,归并是nlogn的。但是这两这前面都是有一个常数项的,对于这个系数而言,插入排序是比归并排序要小的,也就是说,当n小到一定程度的时候,插入排序会比归并排序要快。
// 改进递归到底使用插入排序
function __mergeSort(arr, l, r) {
// if (l >= r) {
// return
// }
if (r-l<=15) {
insertionSort(arr,l,r)
return
}
let mid = Math.floor((l + r) / 2)
__mergeSort(arr, l, mid)
__mergeSort(arr, mid + 1, r)
// 因为两块都是有序的,如果我们的前者的最大值比后者的最小值还要小,说明此时已经有序
if (arr[mid] > arr[mid + 1])
__merge(arr, l, mid, r)
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
测试:当我们的随机数样本量为50w的时候,改进后的算法提升了10%--20%左右,但是时间复杂度在本质上没有变化。
# 自底向上
我们上面的归并排序是自顶向下的使用递归实现的排序,我们可以换个思维,使用自底向上的思想来完成排序,在这个过程中,我们就不用使用递归,而是直接迭代,就能够完成排序
function mergeSortBottomToUp (arr) {
var len = arr.length
// 第一轮循环控制有几次向上的过程 1 - 2 - 4 - 8 。。。 这样的过程
for (let size = 1; size <= len; size+=size) {
// 对arr[i...i+size-1],和 arr[i+size....i+size*2-1] 进行归并
// for (let i = 0; i< len; i += size*2) {
// i+size也至少是小于n的 保证 i+size-1 是不会越界的
for (let i = 0; i + size < len; i += size * 2) {
// __merge(arr, i, i+size-1, i+size*2 - 1)
// i+size*2 -1 可能会比n大 所以
__merge(arr, i, i+size-1, Math.min((i+size*2-1),len-1))
}
}
}
function __merge(arr, l, mid, r) {
let aux = new Array(r - l + 1)
let i = 0
let p1 = l
let p2 = mid + 1
// 谁小往临时数组里就添谁的过程
while (p1 <= mid && p2 <= r) {
aux[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]
}
// 临界过程
while (p1 <= mid) {
aux[i++] = arr[p1++]
}
while (p2 <= r) {
aux[i++] = arr[p2++]
}
for (let i = 0; i < aux.length; i++) {
arr[l + i] = aux[i]
}
}
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
这个排序我们可以发现一个很重要的特性,我们在排序的过程中没有使用使用数组的索引来获取数组的某一项,这一特性可以使得自底向上的归并排序可以很好的操作链表。
# 自然归并排序
我们知道归并排序是将多个有序的数组合并成一个数组
一个无序的数组(除了完全逆序的数组 ),总有一传递。。部分数组是有序的
我们可以获取有序数组的标记,从而将多个有序数组合并成一个数组,这是自然归并排序的关键
原理很简单,但是代码实现有点绕
// 自然分组
function fenzu (arr,getPosArr) {
let j = 0
getPosArr[j++] = 0 // 第一个分组一定是从下标0开始的
// 循环到后面的时候,k前的元素已经排序完成 就不要再扫描k前的了
k = getPosArr[2] ? getPosArr[2] - 1 : 0
for(i= k ;i < arr.length -1;i++) {
if (arr[i] > arr[i+1]) {
getPosArr[j++] = i
}
}
getPosArr[j++] = arr.length-1
// let arr = [1, 5, 2, 3, 6, 0, 7, 4, 8]
// numOfNatureGroupings为自然分组的个数, 此次值为4,
// 即分为四组,{1, 5}, {2, 3, 6}, {0, 7}, {4, 8}
return j
}
// 两组的归并操作
function __merge(arr, l, mid, r) {
let aux = new Array(r - l + 1)
let i = 0
let p1 = l
let p2 = mid + 1
// 谁小往临时数组里就添谁的过程
while (p1 <= mid && p2 <= r) {
aux[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++]
}
// 临界过程
while (p1 <= mid) {
aux[i++] = arr[p1++]
}
while (p2 <= r) {
aux[i++] = arr[p2++]
}
for (let i = 0; i < aux.length; i++) {
arr[l + i] = aux[i]
}
}
function naturallyMergeSort (arr) {
let getPosArr = []
let groupsNum = fenzu(arr,getPosArr)
while(groupsNum>2) {
for(i=0;i<groupsNum-2;i+=2) {
__merge(arr,getPosArr[i],getPosArr[i+1],getPosArr[i+2])
}
groupsNum = fenzu(arr,getPosArr)
}
return arr
}
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
通过建立一个数组,扫描我们的待排数组,比较前后的位置,将我们的数组分成 groupsNum
个有序数组,然后在进行merge操作即可。
# StrandSort归并
这种归并排序算法的思想是,需要一个空的数组用来存放最终的输出结果,给它取个名字叫"有序数组"然后每次遍历待排数组,得到一个"子有序数组",然后将"子有序数组"与"有序数组"合并排序重复上述操作直到待排数组为空结束。
看例子吧
待排数组[ 6 2 4 1 5 9 ]
第一趟遍历得到"子有序数组"[ 6 9],并将其归并排序到有序数组里
待排数组[ 2 4 1 5]
有序数组[ 6 9 ]
第二趟遍历再次得到"子有序数组"[2 4 5],将其归并排序到有序数组里
待排数组[ 1 ]
有序数组[ 2 4 5 6 9 ]
第三趟遍历再次得到"子有序数组"[ 1 ],将其归并排序到有序数组里
待排数组[ ... ]
有序数组[ 1 2 4 5 6 9 ]
// 归并算法 中的 StrandSort
function StrandSort (arr) {
let aux = [[arr[0]]]
let times = 0
let arr2 = []
let flag = 0
while(flag === 0) {
let temp = arr[0]
aux[times] = [arr[0]]
// flag = 1
for(var i=1;i<arr.length;i++) {
if(arr[i] >= temp) {
// flag = arr[i] === temp ? 1 : 0
temp = arr[i]
aux[times].push(arr[i])
} else {
arr2.push(arr[i])
}
}
if (arr2.length) {
arr = arr2.slice()
} else {
flag = 1
}
arr2 = []
if (times === 1) {
aux[0] = __merge2(aux[0],aux[1])
times--
}
times++
}
return aux[0]
}
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
函数的代码文件在源文件里,很难理解,了解实现即可吧。
我在实验的过程中,这种算法的性能远不如普通的归并排序,也不晓得具体原因。