一. 幾種簡單的排序
冒泡排序, 選擇排序和插入排序
做一些簡單的準(zhǔn)備工作
準(zhǔn)備一個(gè) CArray 類, 用來實(shí)現(xiàn)一個(gè)自己的數(shù)組
class CArray {
constructor(numElements) {
this.dataStore = []
this.position = 0
this.numElements = numElements
for (let i = 0; i < numElements; i++) {
this.dataStore[i] = i
}
}
}
當(dāng)我們 new 這個(gè)數(shù)組的時(shí)候, 可以像 JS 里new 一個(gè)普通的數(shù)組一樣:
const arr = new CArray(n)
去生成一個(gè)長度為 n, 內(nèi)部元素為 [0, 1, 2, 3, ..., n] 的數(shù)組
當(dāng)然, 我們需要一個(gè)亂序的數(shù)據(jù), 所以, 這里給 CArray 類 一個(gè) setData 方法
setData() {
for (let i = 0; i < this.dataStore.length; i++) {
this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1))
}
}
所以, 執(zhí)行 setData 方法, 就可以得到一個(gè)亂序的數(shù)組了
const arr = new CArray(10)
arr.setData()
console.log(arr.dataStore ) // 長度為10, 亂序的數(shù)組
冒泡排序
流程: 遍歷數(shù)組, 將相鄰的2個(gè)元素兩兩對比, 如果前一個(gè)數(shù)比后一個(gè)數(shù)大, 則交換 2 個(gè)元素的值; 這樣, 在第一次遍歷時(shí), 就會(huì)將最大的數(shù)移動(dòng)到最右邊, 接下來的步驟是將剩余部分最大的數(shù)往剩余部分的最右邊移的過程, 直到最后一個(gè)數(shù)
因?yàn)槊芭菖判蚝瓦x擇排序都會(huì)用到交換數(shù)組兩個(gè)位置的值, 這里我們定義一個(gè) swap 方法
function swap(arr, index1, index2) {
[arr[index1], arr[index2]] = [arr[index2], arr[index1]]
}
接下來是冒泡排序的實(shí)現(xiàn)
直接定義在 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)
}
}
}
}
選擇排序
流程: 選擇排序從數(shù)組的開頭開始, 將第一個(gè)元素和其他元素進(jìn)行比; 檢查完所有元素后什黑，最小的元素會(huì)被放到數(shù)組的第一個(gè)位置, 然后算法會(huì)從第二個(gè)位置繼續(xù); 這個(gè)過程一直進(jìn)行, 當(dāng)進(jìn)行到數(shù)組的倒數(shù)第二個(gè)位置時(shí), 所有的數(shù)據(jù)便完成了排序
代碼實(shí)現(xiàn):
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)
}
}
插入排序
流程: 插入排序有兩個(gè)循環(huán)。外循環(huán)將數(shù)組元素挨個(gè)移動(dòng)钦勘，而內(nèi)循環(huán)則對外循環(huán)中選中的元素及它后面的那個(gè)元素進(jìn)行比較夭苗。如果外循環(huán)中選中的元素比內(nèi)循環(huán)中選中的元素小苍日，那么數(shù)組元素會(huì)向右移動(dòng)把敞，為內(nèi)循環(huán)中的這個(gè)元素騰出位置
代碼實(shí)現(xiàn):
insertSort() {
let data = this.dataStore
for (let i = 1; i < data.length; i++) {
let current = data[i]
let index = i
// 當(dāng) 當(dāng)前的數(shù)小于前一位的數(shù)
while (current < data[index - 1] && index > 0) {
// 將前面的數(shù)往都后移一位
data[index] = data[index - 1]
index -= 1
}
console.log(data[index], current)
// 直到當(dāng)前的數(shù)大于等于之前一位的數(shù)
data[index] = current
}
}
