Skip to content

Latest commit

 

History

History
736 lines (622 loc) · 19.4 KB

9-排序算法（第12章）.md

File metadata and controls

736 lines (622 loc) · 19.4 KB
Raw

9.排序算法

对计算机中存储的数据执行的两种最常见操作是排序和检索，对计算机中存储的数据执行的两种最常见操作是排序和检索。

9.1 辅助函数

在研究算法前，我们先创建一个辅助函数，该函数的作用就是方便对我们的算法进行测试，避免我们老是做一些重复性的工作。

class cArray {
  constructor(numElements) {
    this.dataStore = new Array(numElements)
    this.init()
  }
  // 初始化数组
  init() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = i
    }
  }
  // 把数组设置成随机数组
  setData() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = Math.floor(Math.random() * (this.dataStore.length + 1))
    }
  }
  // 清空数组
  clear() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = 0
    }
  }
  // 在数组顶部插入元素
  insert(ele) {
    this.dataStore.push(ele)
  }
  // 将数组转成字符串
  toString() {
    let result = ''
    for (let i = 0; i < this.dataStore.length; i++) {
      result += this.dataStore[i] + ' '
      if (i > 0 && i % 10 == 9) {
        result += '\n'
      }
    }
    return result
  }
  // 交换数组中的元素
  swap(index1, index2) {
    let temp = this.dataStore[index1]
    this.dataStore[index1] = this.dataStore[index2]
    this.dataStore[index2] = temp
  }
}

测试：

// 生成工具函数对象
let cArr = new cArray(100)
// 设置随机数据
cArr.setData()

console.log(cArr.toString())

// 打印结果
23 53 33 19 46 13 32 91 99 32 
50 57 88 4 65 46 61 77 81 3 
55 74 62 31 56 79 17 14 40 11 
65 92 93 71 80 92 37 22 92 83 
52 7 47 3 6 65 48 69 37 23 
64 43 14 76 92 4 4 20 49 96 
3 35 53 24 45 52 50 3 94 35 
43 50 68 37 14 9 75 93 97 57 
60 19 30 23 26 24 12 53 78 88 
65 28 25 68 95 8 0 35 5 10

// 清空数组
cArr.clear()
console.log(cArr.toString())
// 打印结果
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 

//  交换数组的元素
let dArr = new cArray(3)

console.log(dArr.toString())

// 打印结果
0 1 2 

dArr.swap(0, 1)

console.log(dArr.toString())

// 打印结果
1 0 2

我们的辅助函数能够生成一个随机数组，

9.2 冒泡排序

冒泡排序算法是最慢的排序算法之一，但也是最容易实现的一种排序算法。之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换 。

下图演示了如何对一个大的数字数据集合进行冒泡排序。在图中，我们分析了插入数组中的两个特定值： 2 和 72。这两个数字都被圈了起来。你可以看到 72 是如何从数组的开头移动到中间的，还有 2 是如何从数组的后半部分移动到开头的。

冒泡排序

程序：

bubbleSort() {
    let dataStore = this.dataStore
    let len = dataStore.length
    for (let i = 0; i < len - 1; i++) {
      for (let j = len - 1; j > i; j--) {
        if (dataStore[j] < dataStore[j - 1]) {
          this.swap(j, j - 1)
        }
      }
    }
  }

测试:

// 生成工具函数对象
let cArr = new cArray(10)
// 设置随机数据
cArr.setData()

console.log(cArr.toString())
//  5 3 9 4 2 6 10 5 3 8 

cArr.bubbleSort()

console.log(cArr.toString())
// 2 3 3 4 5 5 6 8 9 10

测试结果正确，我们的程序应该没有问题。

9.3 选择排序

我们接下来要看的是选择排序算法。选择排序从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序 。

选择排序

程序实现：

  // 选择排序
  selectionSort() {
    let dataStore = this.dataStore
    let len = dataStore.length
    for (let i = 0; i < len - 1; i++) {
      for (let j = i + 1; j < len; j++) {
        if (dataStore[i] > dataStore[j]) {
          this.swap(i, j)
        }
      }
    }
  }

测试

// 生成工具函数对象
let cArr = new cArray(10)
// 设置随机数据
cArr.setData()

console.log(cArr.toString())
// 3 2 0 10 7 4 4 7 0 6

cArr.selectionSort()

console.log(cArr.toString())
// 0 0 2 3 4 4 6 7 7 10

测试结果正确

9.4 插入排序

插入排序类似于人类按数字或字母顺序对数据进行排序，插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它前面的所有元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，然后在适当的位置插入外循环选中的元素。

以上的话，特别绕，还是直接看程序清晰

代码实现:

  // 插入排序
  insertionSort() {
    let temp, inser
    let dataStore = this.dataStore
    let len = dataStore.length
    for (let outer = 1; outer < len; outer++) {
      temp = dataStore[outer]
      let inner = outer
      while (inner > 0 && dataStore[inner - 1] > temp) {
        this.swap(inner, inner - 1)
        inner--
      }
      dataStore[inner] = temp
    }
  }

测试

// 生成工具函数对象
let cArr = new cArray(10)
// 设置随机数据
cArr.setData()

console.log(cArr.toString())
// 4 9 8 8 3 8 5 8 5 0 

cArr.insertionSort()

console.log(cArr.toString())
// 0 3 4 5 5 8 8 8 8 9

测试结果正确，说明我们的程序没有问题。

9.4 算法时间比较

测试：

// 生成工具函数对象
let cArr = new cArray(1000)
// 设置随机数据
cArr.setData()
// 保存生成的随机数组，为了比较各个算法的时间复杂度，必须保证它们处理的随机数组是一样的
let dataStore = cArr.dataStore.concat()
// 冒泡排序
console.time('bubbleSort')
cArr.insertionSort()
console.timeEnd('bubbleSort')

// 选择排序
cArr.dataStore = dataStore.concat()
console.time('selectionSort')
cArr.insertionSort()
console.timeEnd('selectionSort')

// 插入排序
cArr.dataStore = dataStore.concat()
console.time('insertion')
cArr.insertionSort()
console.timeEnd('insertion')

测试结果:

bubbleSort: 5.827880859375ms
selectionSort: 3.77392578125ms
insertion: 0.712890625ms

处理同样的1000条数据，我们可以看到冒泡排序是最慢的，其次是选择排序，插入排序是最快的。

不过这三种排序方法，在大数据时，性能还是较慢。以下是更加高级的算法。这算法在效率上要更高。

9.5 希尔排序

这个算法在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻的元素。和简单地比较相邻元素相比，使用这种方案可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时，所有元素之间的距离会不断减小，直到处理到数据集的末尾，这时算法比较的就是相邻元素了 。

希尔排序的工作原理是，通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分的实际应用场景，算法要用到的间隔序列可以提前定义好。有一些公开定义的间隔序列可以给我们使用。这个间隔序列是： 701, 301, 132, 57, 23, 10, 4, 1

下图演示了希尔排序的工作原理

希尔排序

希尔排序代码

 // 希尔排序
  shellSort () {
    // 间隔序列
    let gaps = [5, 3, 1]
    for (let g = 0; g < gaps.length; g++) {
      let tempG = gaps[g]
      for (let i = tempG; i < this.dataStore.length; i++) {
        let temp = this.dataStore[i]
        let j = i
        while (j >= tempG && this.dataStore[j - tempG] > temp) {
          this.dataStore[j] = this.dataStore[j - tempG]
          j -= tempG
        }
        this.dataStore[j] = temp
      }
    }
  }

测试

// 生成工具函数对象
let cArr = new cArray(10)
// 设置随机数据
cArr.setData()
console.log(cArr.toString()) 
// 4 7 8 10 1 1 0 3 10 4 
cArr.shellSort()
console.log(cArr.toString())
// 0 1 1 3 4 4 7 8 10 10

测试结果正确，说明我们的程序没有问题。

9.5.1 计算动态间隔序列

希尔排序的间隔序列是可以动态计算的，计算公式如下。

let N = this.dataStore.length;
let h = 1;
while (h < N/3) {
h = 3 * h + 1;
}

间隔值确定好后，这个函数就可以像之前定义的 shellsort() 函数一样运行了，唯一的区别是，回到外循环之前的最后一条语句会计算一个新的间隔值。

h = (h-1)/3

对我们的shell排序进行重新优化

  // 希尔排序
  shellSort () {
    // 间隔序列
    let N = this.dataStore.length
    let h = 1
    while (h < N / 3) {
      h = 3 * h + 1
    }
    while (h >= 1) {
      for (let i = h; i < this.dataStore.length; i++) {
        let temp = this.dataStore[i]
        let j = i
        while (j >= h && this.dataStore[j - h] > temp) {
          this.dataStore[j] = this.dataStore[j - h]
          this.swap(j, j - h)
          j -= h
        }
        this.dataStore[j] = temp
      }
      h = (h - 1) / 3
    }
  }

测试是正确的，我就不贴测试结果了。关于希尔排序的知识就这些。

9.6 归并排序

归并排序的命名来自它的实现原理：把一系列排好序的子序列合并成一个大的完整有序序列。从理论上讲，这个算法很容易实现。我们需要两个排好序的子数组，然后通过比较数据大小，先从最小的数据开始插入，最后合并得到第三个数组。

归并排序的核心思想是分治，分治是通过递归地将问题分解成相同或者类型相关的两个或者多个子问题，直到问题简单到足以解决，然后将子问题的解决方案结合起来，解决原始方案的一种思想。

归并排序通过将复杂的数组分解成足够小的数组（只包含一个元素），然后通过合并两个有序数组（单元素数组可认为是有序数组）来达到综合子问题解决方案的目的。所以归并排序的核心在于如何整合两个有序数组，拆分数组只是一个辅助过程。

作者写的这个归并排序算法非常复杂。我跟着捋了几遍，才略懂，有更好的讲解的话请@我。

归并排序代码：

  mergeSort() {
    let arr = this.dataStore
    if (arr.length < 2) {
      return
    }
    let step = 1
    let left, right
    while (step < arr.length) {
      left = 0;
      right = step
      while (right + step <= arr.length) {
        this.mergeArrays(arr, left, left + step, right, right + step)
        left = right + step
        right = left + step
      }
      if (right < arr.length) {
        this.mergeArrays(arr, left, left + step, right, arr.length)
      }
      step *= 2;

    }
  }
  mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
    let rightArr = new Array(stopRight - startRight + 1)
    let leftArr = new Array(stopLeft - startLeft + 1)
    let k = startRight
    for (let i = 0; i < (rightArr.length - 1); i++) {
      rightArr[i] = arr[k]
      k++
    }
    k = startLeft
    for (let i = 0; i < (leftArr.length - 1); i++) {
      leftArr[i] = arr[k]
      k++
    }
    rightArr[rightArr.length - 1] = Infinity
    leftArr[leftArr.length - 1] = Infinity
    let m = 0;
    let n = 0;
    for (let k = startLeft; k < stopRight; ++k) {
      if (leftArr[m] < rightArr[n]) {
        arr[k] = leftArr[m]
        m++
      } else {
        arr[k] = rightArr[n]
        n++
      }
    }
  }

测试：

let cArr = new cArray(10)
cArr.setData()
console.log(cArr.toString())
console.time('mergeSort')
// 5 7 5 9 8 7 8 5 2 5 
cArr.mergeSort()
console.timeEnd('mergeSort')
console.log(cArr.toString())
// 2 5 5 5 5 7 7 8 8 9

9.7 快速排序

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。

这个算法首先要在列表中选择一个元素作为基准值（pivot）。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。

快速排序

程序

// 快速排序
  qSort() {
    this.dataStore = this.qSortArr(this.dataStore)
  }
  qSortArr(list) {
    if (list.length == 0) {
      return []
    }
    let lesser = []
    let greater = []
    let pivot = list[0]
    for (let i = 1; i < list.length; i++) {
      if (list[i] < pivot) {
        lesser.push(list[i])
      } else {
        greater.push(list[i])
      }
    }
    return this.qSortArr(lesser).concat(pivot, this.qSortArr(greater))
  }

测试

let cArr = new cArray(10)
// 设置随机数据
cArr.setData()
console.log(cArr.toString())
// 8 7 2 9 10 2 3 5 9 4 
console.time('qSort')
cArr.qSort()
console.timeEnd('qSort')
console.log(cArr.toString())
// 2 2 3 4 5 7 8 9 9 10

自此，关于排序的算法就讲解忘了，读这一章用了很多时间，排序确实比较难，尤其是那个归并排序。好难理解。自己尝试实现，结果没实现出来，如果有好的实现方法，请一定告诉我。

本章完整的代码如下：

class cArray {
  constructor(numElements) {
    this.dataStore = new Array(numElements)
    this.init()
  }
  // 初始化数组
  init() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = i
    }
  }
  // 把数组设置成随机数组
  setData() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = Math.floor(
        Math.random() * (this.dataStore.length + 1)
      )
    }
  }
  // 清空数组
  clear() {
    for (let i = 0; i < this.dataStore.length; i++) {
      this.dataStore[i] = 0
    }
  }
  // 在数组顶部插入元素
  insert(ele) {
    this.dataStore.push(ele)
  }
  // 将数组转成字符串
  toString() {
    let result = ''
    for (let i = 0; i < this.dataStore.length; i++) {
      result += this.dataStore[i] + ' '
      if (i > 0 && i % 10 == 9) {
        result += '\n'
      }
    }
    return result
  }
  // 交换数组中的元素
  swap(index1, index2) {
    let temp = this.dataStore[index1]
    this.dataStore[index1] = this.dataStore[index2]
    this.dataStore[index2] = temp
  }
  // 冒泡排序
  bubbleSort() {
    let dataStore = this.dataStore
    let len = dataStore.length
    for (let i = 0; i < len - 1; i++) {
      for (let j = len - 1; j > i; j--) {
        if (dataStore[j] < dataStore[j - 1]) {
          this.swap(j, j - 1)
        }
      }
    }
  }
  // 选择排序
  selectionSort() {
    let dataStore = this.dataStore
    let len = dataStore.length
    for (let i = 0; i < len - 1; i++) {
      for (let j = i + 1; j < len; j++) {
        if (dataStore[i] > dataStore[j]) {
          this.swap(i, j)
        }
      }
    }
  }
  // 插入排序
  insertionSort() {
    let temp, inser
    let dataStore = this.dataStore
    let len = dataStore.length
    for (let outer = 1; outer < len; outer++) {
      temp = dataStore[outer]
      let inner = outer
      while (inner > 0 && dataStore[inner - 1] > temp) {
        this.swap(inner, inner - 1)
        inner--
      }
      dataStore[inner] = temp
    }
  }

  // 希尔排序
  shellSort() {
    // 间隔序列
    let N = this.dataStore.length
    let h = 1
    while (h < N / 3) {
      h = 3 * h + 1
    }
    while (h >= 1) {
      for (let i = h; i < this.dataStore.length; i++) {
        let temp = this.dataStore[i]
        let j = i
        while (j >= h && this.dataStore[j - h] > temp) {
          this.dataStore[j] = this.dataStore[j - h]
          this.swap(j, j - h)
          j -= h
        }
        this.dataStore[j] = temp
      }
      h = (h - 1) / 3
    }
  }
  // 归并排序
  mergeSort() {
    let arr = this.dataStore
    if (arr.length < 2) {
      return
    }
    let step = 1
    let left, right
    while (step < arr.length) {
      left = 0;
      right = step
      while (right + step <= arr.length) {
        this.mergeArrays(arr, left, left + step, right, right + step)
        left = right + step
        right = left + step
      }
      if (right < arr.length) {
        this.mergeArrays(arr, left, left + step, right, arr.length)
      }
      step *= 2;

    }
  }
  mergeArrays(arr, startLeft, stopLeft, startRight, stopRight) {
    let rightArr = new Array(stopRight - startRight + 1)
    let leftArr = new Array(stopLeft - startLeft + 1)
    let k = startRight
    for (let i = 0; i < (rightArr.length - 1); i++) {
      rightArr[i] = arr[k]
      k++
    }
    k = startLeft
    for (let i = 0; i < (leftArr.length - 1); i++) {
      leftArr[i] = arr[k]
      k++
    }
    rightArr[rightArr.length - 1] = Infinity
    leftArr[leftArr.length - 1] = Infinity
    let m = 0;
    let n = 0;
    for (let k = startLeft; k < stopRight; ++k) {
      if (leftArr[m] < rightArr[n]) {
        arr[k] = leftArr[m]
        m++
      } else {
        arr[k] = rightArr[n]
        n++
      }
    }
  }
  // 快速排序
  qSort() {
    this.dataStore = this.qSortArr(this.dataStore)
  }
  qSortArr(list) {
    if (list.length == 0) {
      return []
    }
    let lesser = []
    let greater = []
    let pivot = list[0]
    for (let i = 1; i < list.length; i++) {
      if (list[i] < pivot) {
        lesser.push(list[i])
      } else {
        greater.push(list[i])
      }
    }
    return this.qSortArr(lesser).concat(pivot, this.qSortArr(greater))
  }
}
// 生成工具函数对象
let cArr = new cArray(10)
// 设置随机数据
cArr.setData()

// 保存生成的随机数组，为了比较各个算法的时间复杂度，必须保证它们处理的随机数组是一样的
let dataStore = cArr.dataStore.concat()
// 冒泡排序
console.time('bubbleSort')
cArr.insertionSort()
console.timeEnd('bubbleSort')

// 选择排序
cArr.dataStore = dataStore.concat()
console.time('selectionSort')
cArr.insertionSort()
console.timeEnd('selectionSort')

// 插入排序
cArr.dataStore = dataStore.concat()
console.time('insertion')
cArr.insertionSort()
console.timeEnd('insertion')

// 希尔排序
cArr.dataStore = dataStore.concat()
console.time('shell')
cArr.shellSort()
console.timeEnd('shell')

// 归并排序
cArr.dataStore = dataStore.concat()
console.time('mergeSort')
cArr.mergeSort()
console.timeEnd('mergeSort')


cArr.dataStore = dataStore.concat()
console.time('qSort')
cArr.qSort()
console.timeEnd('qSort')