js数据结构与算法-排序

发表于 | 分类于 
1
2
3
4
5
function swap(arr, a, b) {
  var temp = arr[a]
  arr[a] = arr[b]
  arr[b] = temp
}

冒泡排序：特点相邻元素交换位置，j循环每遍历一轮，冒泡一个最大值到顶部
时间复杂度：O(n*n)
空间复杂度：O(1)
稳定性：稳定

1
2
3
4
5
6
7
8
9
10
function buddleSort(arr) {
  var len = arr.length;
  for(var i = 0; i < len; i++) {
    for (var j = 0; j < len - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j +1 )
      }
    }
  }
}

选择排序：j循环选择最小的与i交换
时间复杂度：O(n*n)
空间复杂度：O(1)
稳定性：不稳定

1
2
3
4
5
6
7
8
9
10
11
12
function selectSort(arr) {
  var len = arr.length;
  for(var i = 0; i < len; i++) {
    var minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j
      }
    }
    swap(arr, i, minIndex)
  }
}

插入排序：将待排序依次插入已排序序列的合适位置
时间复杂度：O(n*n)
空间复杂度：O(1)
稳定性：稳定

1
2
3
4
5
6
7
8
9
10
11
function insertSort(arr) {
  var len = arr.length;
  for(var i = 0; i < len; i++) {
    var minIndex = i;
    while(j = i && arr[j] < arr[j - 1]) {
      swap(arr, j, j - 1)
      --j
    }
  }
}

希尔排序：插入排序的改善，定义一个间隔序列
时间复杂度：O(nlog2n)
空间复杂度：O(1)
稳定性：不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//间隔序列，分别以间隔序列里面的间隔进行插入排序
var gaps = [5, 3, 1]
function shellSort(arr) {
  var len = arr.length;
  var gapsLen = gaps.length
  for (var g = 0; g < gapsLen; g++) {
    var gap = gaps[g]
    for (var i = gap; i < len; i++) {
      var temp = arr[i];
      for (var j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
        arr[j] = arr[j - gap];
      }
      arr[j] = temp;
    }
  }
}

快速排序：递归将数据依次分为包含较小元素和较大元素不同子序列，分治法
时间复杂度：O(nlog2n)
空间复杂度：O(nlog2n)
稳定性：不稳定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function quickSort(arr) {
  var minArr = []
  var maxArr = []
  var pri = arr[0]
  var len = arr.length
  for (var i = 0; i < len; i++) {
    if (arr[i] < pri) {
      minArr.push(arr[i])
    } else {
      maxArr.push(arr[i])
    }
  }
  return quickSort(minArr).concat(pri, quickSort(maxArr))
}

归并排序：把一系列排好序的子序列合并成一个大的完整有序序列，自顶向下（递归，深度太深，一般不用），自底向上（迭代）
时间复杂度：O(nlog2n)
空间复杂度：O(n)
稳定性：稳定

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
//递归实现
function merge(left, right) {
  var tmp = [];
  while (left.length && right.length) {
    if (left[0] < right[0])
      tmp.push(left.shift());
    else
      tmp.push(right.shift());
  }
  return tmp.concat(left, right);
}
function mergeSort(a) {
  if (a.length === 1)
    return a;
  var mid = ~~(a.length / 2)
    , left = a.slice(0, mid)
    , right = a.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}
// 迭代实现
function merge(left, right) {
  var result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return result.concat(left, right);
}
function mergeSort(arr) {
  if (arr.length === 1)
    return arr;
  var work = [];
  for (var i = 0, len = arr.length; i < len; i++) {
    work.push([arr[i]]);
  }
  work.push([]);
  for (var lim = len; lim > 1; lim = ~~((lim + 1) / 2)) {
    for (var j = 0, k = 0; k < lim; j++, k += 2) {
      work[j] = merge(work[k], work[k + 1]);
    }
    work[j] = [];
  }
  return work[0];
}