排序
灵感胜于汗水 Lv5
  2022-05-13 22:53:44 2022-05-13 22:53      2.5k 字  

选择排序

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。

以此类推，直到全部待排序的数据元素的个数为零。

算法的时间复杂度为O(n^2)、额外空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function swap(arr, i, j) {
  let num = arr[i]
  arr[i] = arr[j]
  arr[j] = num
}

const arr = [3, 44, 635, 7, 45, 34, 65, 2, 34, 6262, 432, 4]

function selectSort(arr) {
  if (!Array.isArray(arr) || arr.length < 2) return
  let len = arr.length
  for (let i = 0; i < len; i++) {
    let index = i
    for (let j = i + 1; j < len; j++) {
      index = arr[index] > arr[j] ? j : index
    }
    swap(arr, i, index)
  }
}

console.log(arr) //[3, 44, 635, 7, 45, 34, 65, 2, 34, 6262, 432, 4]
selectSort(arr)
console.log(arr) //[2, 3, 4, 7, 34, 34, 44, 45, 65, 432, 635, 6262]

冒泡排序

首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，则交换这两个元素在数组中的位置。这样操作后数组最右端的元素即为该数组中所有元素的最大值。

接着对该数组除最右端的n-1个元素进行同样的操作，再接着对剩下的n-2个元素做同样的操作，直到整个数组有序排列。

算法的时间复杂度为O(n^2)、额外空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr) {
  if (!Array.isArray(arr) || arr.length < 2) return
  const len = arr.length
  for (let i = len - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      arr[j] > arr[j + 1] ? swap(arr, j, j + 1) : null
    }
  }
}

console.log(arr) //[3, 44, 635, 7, 45, 34, 65, 2, 34, 6262, 432, 4]
bubbleSort(arr)
console.log(arr) //[2, 3, 4, 7, 34, 34, 44, 45, 65, 432, 635, 6262]

插入排序

将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。

算法的时间复杂度为O(n^2)、额外空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertSort(arr) {
  if (!Array.isArray(arr) || arr.length < 2) return
  const len = arr.length
  for (let i = 1; i < len; i++) {
    let j = i
    while (j >= 0 && arr[j - 1] > arr[j]) {
      swap(arr, j - 1, j)
      j--
    }
  }
}

console.log(arr) //[3, 44, 635, 7, 45, 34, 65, 2, 34, 6262, 432, 4]
insertSort(arr)
console.log(arr) //[2, 3, 4, 7, 34, 34, 44, 45, 65, 432, 635, 6262]

简化写法

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertSort2(arr) {
  if (!Array.isArray(arr) || arr.length < 2) return
  const len = arr.length
  for (let i = 1; i < len; i++) {
    for (let j = i - 1; j > -1 && arr[j] > arr[j + 1]; j--) {
      swap(arr, j, j + 1)
    }
  }
}

console.log(arr) //[3, 44, 635, 7, 45, 34, 65, 2, 34, 6262, 432, 4]
insertSort2(arr)
console.log(arr) //[2, 3, 4, 7, 34, 34, 44, 45, 65, 432, 635, 6262]

适用于数据量不大，算法稳定性要求高，且数据局部或整体有序的数列排序。

对数器

生成随机长度和随机值的数组，用于测试排序算法是否正确

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
function randomArray(maxLen, maxVal) {
  const arr = []
  const len = Math.floor(Math.random() * maxLen) + 1
  for (let i = 0; i < len; i++) {
    arr.push(Math.floor(Math.random() * maxVal))
  }
  return arr
}

function copy(arr) {
  const newArr = []
  for (let i = 0; i < arr.length; i++) {
    newArr.push(arr[i])
  }
  return newArr
}

//是否升序
function isSorted(arr) {
  if (arr.length < 2) return true
  for (let i = 1; i < arr.length; i++) {
    if (arr[i - 1] > arr[i]) return false
  }
  return true
}

function testSort(sortFun) {
  for (let i = 0; i < 1000; i++) {
    const arr = randomArray(10, 1000)
    const backup = copy(arr)
    sortFun(arr)
    if (!isSorted(arr)) {
      console.log('排序出错')
      console.log('排序前:' + backup)
      console.log('排序后:' + arr)
      return
    }
  }
  console.log('排序成功')
}

testSort(selectSort) //排序成功
testSort(bubbleSort) //排序成功
testSort(insertSort) //排序成功
testSort(insertSort2) //排序成功

归并排序

归并排序（Merge Sort）是建立归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

算法的时间复杂度为O(n*log 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
function merge(arr, l, m, r) {
  const help = []
  let p1 = l
  let p2 = m + 1
  while (p1 <= m && p2 <= r) {
    arr[p1] <= arr[p2] ? help.push(arr[p1++]) : help.push(arr[p2++])
  }
  while (p1 <= m) {
    help.push(arr[p1++])
  }
  while (p2 <= r) {
    help.push(arr[p2++])
  }
  for (let i = 0; i < help.length; i++) {
    arr[l + i] = help[i]
  }
}

function mergeSortProcess(arr, l, r) {
  if (l === r) return
  let mid = l + Math.floor((r - l) / 2)
  mergeSortProcess(arr, l, mid)
  mergeSortProcess(arr, mid + 1, r)
  merge(arr, l, mid, r)
}


function mergeSort(arr) {
  if (!Array.isArray(arr) || arr.length < 2) return
  let l = 0
  let r = arr.length + 1
  mergeSortProcess(arr, l, r)
}

testSort(mergeSort) //排序成功

快速排序

快速排序（Quick Sort）算法是在冒泡排序的基础上进行改进的一种算法，从名字上看就知道该排序算法的特点是快、效率高，是处理大数据最快的排序算法之一。

实现的基本思想是：通过一次排序将整个无序表分成相互独立的两部分，其中一部分中的数据都比另一部分中包含的数据的值小。

然后继续沿用此方法分别对两部分进行同样的操作，直到每一个小部分不可再分，所得到的整个序列就变成有序序列。

荷兰国旗问题

给定一个数组arr，数组的最后一个数为num，将arr划分为三个区域，左边的数都小于num，中间等于num，右边都大于num。

要求额外空间复杂度O(1)，时间复杂度O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function partition(arr, l, r) {
  let num = arr[r]
  let i = l
  while (i <= r) {
    if (arr[i] < num) {
      swap(arr, l++, i++)
    } else if (arr[i] === num) {
      i++
    } else {
      swap(arr, i, r--)
    }
  }
  return [l, r]
}

let arr = [1, 8, 7, 4, 5, 6, 1, 8, 4, 9, 5]
//返回一个长度为二的数组，表示中间区域的左右边界
console.log(partition(arr, 0, 10)) //[4, 5]
console.log(arr) //[1, 4, 4, 1, 5, 5, 8, 6, 9, 7, 8]

实现快速排序

递归调用上面（荷兰国旗问题中）的方法，随机选择一个数作为num，划分为小于、等于、大于三个部分后，对左右两个区域执行相同的操作。

算法的时间复杂度为O(n*log n)、额外空间复杂度为O(log n)。

最坏情况下每一次基准元素都是数组中最小或者最大的元素，则快速排序就是冒泡排序，这种情况时间复杂度就是冒泡排序的时间复杂度：O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function quickSortProcess(arr, l, r) {
  if (l >= r) return
  //在l~r范围中随机取一个数和r位置的数交换
  swap(arr, r, l + Math.floor(Math.random() * (r - l + 1)))
  const part = partition(arr, l, r)
  quickSortProcess(arr, l, part[0] - 1)
  quickSortProcess(arr, part[1] + 1, r)
}

function quickSort(arr) {
  if (!Array.isArray(arr) || arr.length < 2) return
  let l = 0
  let r = arr.length - 1
  quickSortProcess(arr, l, r)
}

testSort(quickSort) //排序成功

是目前基于比较的内部排序中被认为最好的方法，当数据过大且数据杂乱无章时，则适合采用快速排序。

堆排序

是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。（小顶堆或大顶堆，下面代码中使用的是大顶堆）

算法的时间复杂度为O(n*log n)、额外空间复杂度为O(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
28
29
30
31
32
33
34
35
36
37
38
39
40
function parentIndex(index) {
  if (!index) return index
  return Math.floor((index - 1) / 2)
}

//比父节点大则与父节点交换
function heapInsert(arr, index) {
  while (arr[index] > arr[parentIndex(index)]) {
    swap(arr, index, parentIndex(index))
    index = parentIndex(index)
  }
}

//比两个子节点中最大的一个小，则与其交换
function heapify(arr, index, heapSize) {
  let left = index * 2 + 1
  while (left < heapSize) {
    let max = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left
    max = arr[index] < arr[max] ? max : index
    if (max === index) break
    swap(arr, index, max)
    index = max
    left = index * 2 + 1
  }
}

function heapSort(arr) {
  let heapSize = arr.length
  //生成大根堆（父节点大于子节点）,该循环时间复杂度为O(n*log n)
  for (let i = 0; i < heapSize; i++) {
    heapInsert(arr, i)
  }
  //该循环时间复杂度为O(n*log n)
  while (heapSize) {
    swap(arr, 0, --heapSize)
    heapify(arr, 0, heapSize)
  }
}

testSort(heapSort) //排序成功

优化写法：（优化前一个循环：只需要使用heapify方法即可将一个数组转化为堆结构，且时间复杂度为O(n)）

1
2
3
4
5
6
7
8
9
10
11
12
13
function heapSort(arr) {
  let heapSize = arr.length
  //该循环时间复杂度为O(n)
  for (let i = heapSize - 1; i >= 0; i--) {
    heapify(arr, i, heapSize)
  }
  while (heapSize) {
    swap(arr, 0, --heapSize)
    heapify(arr, 0, heapSize)
  }
}

testSort(heapSort) //排序成功

稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

  • 不稳定的排序算法：选择排序、快速排序、堆排序等
  • 稳定的排序算法：冒泡排序、插入排序、归并排序等

目前没有发现时间复杂度为O(n*log n)、额外空间复杂度低于O(n)且具有稳定性的排序算法。

一般情况下，快速排序更常用，因为其常数项时间更低。额外空间要求很少时使用堆排序；要求稳定性时使用归并排序。

还可以使用综合排序的方法提高效率。（比如在快排过程中的一些样本量比较少的步骤中使用插入排序）

  • 本文标题：排序
  • 本文作者：灵感胜于汗水
  • 创建时间：2022-05-13 22:53:44
  • 本文链接：https://cjhsyc.github.io/2022/05/13/排序/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！