排序算法

排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

冒泡排序

时间复杂的：O(n²)

原理

比较任何两个相邻的项，如果第一个比第二个大则交换它们。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubbleSort(arr) {
  var length = arr.length
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        swap(arr, j, j + 1)
      }
    }
  }
}

function swap(arr, index1, index2) {
  var aux = arr[index1]
  arr[index1] = arr[index2]
  arr[index2] = aux
}

选择排序

时间复杂的：O(n²)

原理

找到最小值放到第一位，再找到第二小的值并将其放在第二位，以此类推。

实现

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

插入排序

时间复杂度：最好O(n)，一般O(n²)，最坏O(n²)

原理

假定第一项已经排序了，接着它和第二项比较，大就待在原位，小则插到第一项之前，接着第三项又和第一、第二项比较，以此类推。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insertionSort(arr) {
  var len = arr.length,
    j,
    temp
  for (var i = 1; i < len; i++) {
    j = i
    temp = arr[i]
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[i]
      j--
    }
    arr[j] = temp
  }
}

归并排序

时间复杂度：最好O(nlog(n))，一般O(nlog(n))，最坏O(nlog(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
function mergeSort(arr) {
  var arrSort = mergeSortRec(arr)
  return arrSort
}

//切分大数组为小数组
function mergeSortRec(arr) {
  var len = arr.length
  if (len === 1) {
    return arr
  }
  var mid = Math.floor(len / 2),
    left = arr.slice(0, mid),
    right = arr.slice(mid, len)

  return merge(mergeSortRec(left), mergeSortRec(right))
}

//排序并归并为一个大数组
function merge(left, right) {
  var result = [],
    il = 0,
    ir = 0
  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++])
    } else {
      result.push(right[ir++])
    }
  }

  while (il < left.length) {
    result.push(left[il++])
  }

  while (ir < right.length) {
    result.push(right[ir++])
  }

  return result
}

快速排序

时间复杂度：最好O(nlog(n))，一般O(nlog(n))，最坏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
function quickSort(arr) {
  quick(arr, 0, arr.length - 1)
}

function quick(arr, left, right) {
  var index

  if (arr.length > 1) {
    index = position(arr, left, right)

    if (left < index - 1) {
      quick(arr, left, index - 1)
    }

    if (right > index) {
      quick(arr, index, right)
    }
  }
}

//划分过程
function position(arr, left, right) {
  var pivot = arr[Math.floor((right + left) / 2)],
    i = left,
    j = right

  while (i <= j) {
    while (arr[i] < pivot) {
      i++
    }
    while (arr[j] > pivot) {
      j--
    }
    if (i <= j) {
      swap(arr, i, j)
      i++
      j--
    }
  }
  return i
}
0%