一. 几种简单的排序
冒泡排序, 选择排序和插入排序
做一些简单的准备工作
准备一个 CArray 类, 用来实现一个自己的数组
class CArray {
constructor(numElements) {
this.dataStore = []
this.position = 0
this.numElements = numElements
for (let i = 0; i < numElements; i++) {
this.dataStore[i] = i
}
}
}
当我们 new 这个数组的时候, 可以像 JS 里new 一个普通的数组一样:
const arr = new CArray(n)
去生成一个长度为 n, 内部元素为 [0, 1, 2, 3, ..., n] 的数组
当然, 我们需要一个乱序的数据, 所以, 这里给 CArray 类 一个 setData 方法
setData() {
for (let i = 0; i < this.dataStore.length; i++) {
this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1))
}
}
所以, 执行 setData 方法, 就可以得到一个乱序的数组了
const arr = new CArray(10)
arr.setData()
console.log(arr.dataStore ) // 长度为10, 乱序的数组
冒泡排序
流程: 遍历数组, 将相邻的2个元素两两对比, 如果前一个数比后一个数大, 则交换 2 个元素的值; 这样, 在第一次遍历时, 就会将最大的数移动到最右边, 接下来的步骤是将剩余部分最大的数往剩余部分的最右边移的过程, 直到最后一个数
因为冒泡排序和选择排序都会用到交换数组两个位置的值, 这里我们定义一个 swap 方法
function swap(arr, index1, index2) {
[arr[index1], arr[index2]] = [arr[index2], arr[index1]]
}
接下来是冒泡排序的实现
直接定义在 CArray 类上
bubleSort() {
const data = this.dataStore
let len = data.length
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - i; j++) {
if (data[j] > data[j + 1]) {
swap(data, j, j + 1)
}
}
}
}
选择排序
流程: 选择排序从数组的开头开始, 将第一个元素和其他元素进行比; 检查完所有元素后，最小的元素会被放到数组的第一个位置, 然后算法会从第二个位置继续; 这个过程一直进行, 当进行到数组的倒数第二个位置时, 所有的数据便完成了排序
代码实现:
selectionSort() {
let minIndex
let data = this.dataStore
for (let i = 0; i < data.length; i++) {
minIndex = i
for (let j = i + 1; j < data.length; j++) {
if (data[j] < data[minIndex]) {
minIndex = j
}
}
swap(data, minIndex, i)
}
}
插入排序
流程: 插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置
代码实现:
insertSort() {
let data = this.dataStore
for (let i = 1; i < data.length; i++) {
let current = data[i]
let index = i
// 当 当前的数小于前一位的数
while (current < data[index - 1] && index > 0) {
// 将前面的数往都后移一位
data[index] = data[index - 1]
index -= 1
}
console.log(data[index], current)
// 直到当前的数大于等于之前一位的数
data[index] = current
}
}
