3个O(n²)排序

一、选择排序

简单选择排序：每次从待排序的序列中选择最小的元素放到前面

  • 不稳定
  • O(n²)

1. 从前往后排序

arr[i…n)未排序，arr[0…i)已排序

arr[i…n)中的最小值放到arr[i]的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function selectSort (arr) {
  for (let i = 0; i < nums.length - 1; i++) {
    // 选择 arr[i...n) 中最小值的索引
    let minIndex = i
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j
      }
    }
    if (minIndex !== i) {
      swap(nums, minIndex, i)
    }
  }
}

2. 从后往前排序

arr[0…i]未排序，arr(i…n)已排序

arr[0…i]中的最大值放到arr[i]的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function selectSort (arr) {
  for (let i = nums.length - 1; i >= 1; i--) {
    // 选择 arr[0...i] 中最大值的索引
    let maxIndex = i
    for (let j = i - 1; j >= 0; j--) {
      if (nums[j] > nums[maxIndex]) {
        maxIndex = j
      }
    }
    if (maxIndex !== i) {
      swap(nums, maxIndex, i)
    }
  }
}

二、冒泡排序

冒泡排序：从头到尾/从尾到头,按顺序两两比较,每一趟将最小/最大值交换到最左/最右边

  • 稳定
  • O(n²)

1. 从前往后排序

1
2
3
4
5
6
7
8
9
function bubbleSort (arr) {
  for (let i = 0; i < arr.length - 1; i++) { // 一共有n-1轮
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
      }
    }
  }
}

优化1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubbleSort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let isSwapped = false // 记录是否有交换过
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        isSwapped = true
      }
    }
    if (!isSwapped) { // 如果没有过交换，说明已经有序
      break
    }
  }
}

优化2

1
2
3
4
5
6
7
8
9
10
11
12
function bubbleSort (arr) {
  for (let i = 0; i < arr.length - 1;) {
    let lastSwappedIndex = 0  // 记录最近一次最后交换的位置
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        lastSwappedIndex = j + 1
      }
    }
    i = arr.length - lastSwappedIndex
  }
}

2. 从后往前排序

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

优化

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

三、插入排序

插入排序：按顺序从待排序序列中取出一个并插入前面已经排序好的序列中

  • 稳定
  • O(n²)，对于有序数组，复杂度为O(n)

1. 从前往后排序

arr[i…n)未排序，arr[0…i)已排序

把arr[i]放到arr[0…i)中合适的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function insertSort (arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j - 1 >= 0; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1)
      } else {
        break
      }
    }
  }
}

// 简写形式
function insertSort (arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j - 1 >= 0 && arr[j] < arr[j - 1]; j--) {
      swap(arr, j, j - 1)
    }
  }
}

优化

arr[i…n)未排序，arr[0…i)已排序

存储arr[i], 找到arr[i]应该存放的位置

1
2
3
4
5
6
7
8
9
10
function insertSort (arr) {
  for (let i = 1; i < arr.length; i++) {
    const temp = arr[i]
    let j
    for (j = i; j - 1 >= 0 && temp < arr[j - 1]; j--) {
      arr[j] = arr[j - 1]
    }
    arr[j] = temp
  }
}

2. 从后往前排序

1
2
3
4
5
6
7
8
9
10
function insertSort (arr) {
  for (let i = arr.length - 2; i >= 0; i--) {
    const temp = arr[i]
    let j
    for (j = i; j + 1 <= arr.length - 1 && temp > arr[j + 1]; j++) {
      arr[j] = arr[j + 1]
    }
    arr[j] = temp
  }
}

helper.js

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * 交换数组中的两个值
 */

function swap (arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp

  // 只有当 i !== j 时才可以
  // arr[i] ^= arr[j]
  // arr[j] ^= arr[i]
  // arr[i] ^= arr[j]
}

/**
 * 生成一个长度为n的有序数组，[0...n)
 */

function generateOrderedArray (n) {
  const arr = new Array(n)
  for (let i = 0; i < n; i++)
    arr[i] = i
  return arr
}

/**
 * 生成一个长度为n的随机数组，每个值的范围在[0,bound)
 */

function generateRandomArray (n, bound) {
  const arr = new Array(n)
  for (let i = 0; i < n; i++)
    arr[i] = ~~(Math.random() * bound)
  return arr
}

/**
 * 生成一个长度为n的随机数组，每个值的范围在[start,end]
 */

function generateRandomArrayByStartAndEnd (n, start, end) {
  const arr = new Array(n)
  for (let i = 0; i < n; i++)
    arr[i] = ~~(Math.random() * (end - start + 1) + start)
  return arr
}

/**
 * 判断一个数组是否有序
 */

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

/**
 * 测试排序算法性能
 */

function testSort (fn, arr) {
  const startTime = Date.now()
  fn(arr)
  const endTime = Date.now()
  const spendTime = endTime - startTime
  if (!isSorted(arr)) {
    console.log(`${fn.name} failed!`)
    const debugArr = generateRandomArray(5, 10)
    console.log(`Before sort: [${debugArr.join(', ')}]`)
    fn(debugArr)
    console.log(`After sort: [${debugArr.join(', ')}]`)
    return
  }

  console.log(`${fn.name}: ${arr.length}, time: ${spendTime / 1000}s`)
}


module.exports = {
  swap,
  generateOrderedArray,
  generateRandomArray,
  generateRandomArrayByStartAndEnd,
  isSorted,
  testSort
}