// 封装一个列表类
function arrayList() {
this.array = []
// 追加方法
this.append = function (item) {
this.array.push(item)
}
//将数组转化为字符串
this.toString = function () {
return this.array.join('-')
}
// 实现排序算法
// 封装交换位置函数
this.swap = function (m, n) {
let temp = this.array[m]
this.array[m] = this.array[n]
this.array[n] = temp
}
// 冒泡排序 比较次数和交换次数都是O(n²)
this.bubbleSort = function () {
let length = this.array.length
//通过嵌套两次循环，每次循环排除一个元素(length-1)
for (let i = length - 1; i >= 0; i--) {
// 两两比较、交换，大的往后靠，循环完毕最后一个位置必是最大值
for (let j = 0; j < i; j++) {
if (this.array[j] > this.array[j + 1])
this.swap(j, j + 1)
}
}
}
// 选择排序 比较次数是O(n²)，交换次数是O(N)
this.selectionSort = function () {
let length = this.array.length
// 1、先循环数组 拿下标0跟其他所有数比较，如果更小则交换到下标0来
for (let j = 0; j < length; j++) {
let min = j //记录下标
for (let i = j + 1; i < length; i++) {
if (this.array[min] > this.array[i]) {
// 经过不断的循环赋值，此时j就是最小值
min = i
}
}
this.swap(j, min)
}
}
// 插入排序 比较次数是O(n²)，复制次数是O(N) 但是真实次数实际上是更少的
this.insertSort = function () {
let length = this.array.length
// 外层循环
for (let i = 1; i < length; i++) {
let temp = this.array[i]
let j = i
while (this.array[j - 1] > temp && j > 0) { //比如 9 5 4 前面更大就位移 把 5 给 4
this.array[j] = this.array[j - 1]
j--
}
// 此时的J一定是0
this.array[j] = temp //进行复原4 9 5 不复原的话是9 9 5
}
}
// 希尔排序
this.shellSort = function () {
let length = this.array.length
// 初始化间隔
let gap = Math.floor(length / 2)
// 外层循环 每次间隔都在变小 直到间隔小于小于1停止循环
while (gap >= 1) {
for (let i = gap; i < length; i++) {
let temp = this.array[i]
let j = i
while (this.array[j - gap] > temp && j > 0) {
this.array[j] = this.array[j - gap] // 9 5 4 3 2
j = j - gap // 停止while循环 以及进行依次比较
}
this.array[j] = temp //要是写j-gap的话 那么j的值是一直和i 同步的， 那么相当于你每次都是用下标0 替换的下标gap
}
gap = Math.floor(gap / 2)
}
}
// 快速排序获取枢纽 并把枢纽放在数组倒数第二的位置 这样只用找一边的枢纽了？
this.getPivot = function (left, right) {
let center = Math.floor((left + right) / 2)
if (this.array[left] > this.array[center]) {
this.swap(left, center)
}
if (this.array[center] > this.array[right]) {
this.swap(center, right)
}
if (this.array[left] > this.array[center]) {
this.swap(left, center)
}
this.swap(center, right - 1)
return this.array[right - 1]
}
// 快速排序实现 通过递归实现
this.quickSort = function () {
// 传入下标值 获取枢纽用
this.qucikSortRecusion(0, this.array.length - 1)
}
// 快速排序的递归
this.qucikSortRecusion = function (left, right) {
// 1、中断条件：第一位和最后一位在0处重合 遍历完成。
if (left >= right) return
// 2、获得枢纽值
let pivot = this.getPivot(left, right)
// 3、进行比较交换
let i = left
let j = right - 1 //获取枢纽时最右是大于枢纽的
while (i < j) {
while (this.array[++i] < pivot) {} //从左边开始 获得大于于枢纽的值i
while (this.array[--j] > pivot) {} //从右边开始 获得小于枢纽的值j
if (i < j) {
this.swap(i, j)
}
}
this.swap(i, right - 1) //把最大值 i 倒数放
// 4、递归重复操作
this.qucikSortRecusion(left, i - 1)
this.qucikSortRecusion(i + 1, right)
}
}
let arr = new arrayList()
arr.append(12)
arr.append(45)
arr.append(24)
arr.append(4)
arr.append(66)
arr.append(22)
arr.append(76)
arr.append(8)
arr.append(99)
arr.append(100)
arr.append(500)
console.log(arr.toString())
总结：
1、冒泡排序是先找出最大元素 length需要动态--
2、选择排序是先找出最小元素 选择排序第一次找出最小值和下标0交换，第二次用最小值与其他数进行比较
3、插入排序，把第一个元素看为局部有序，第二个元素比较进行排序后移。 循环
4、希尔排序要点，间隔。 比如1-9 那就是9比7，7比5... 每次比较都需要再减去间隔
5、快速排序，找出数组的中位数，作为枢纽放在倒数第二位；利用递归，分成两个局部有序，再进行排序
6、通常情况下快速排序>希尔排序>=插入排序>=选择排序>冒泡排序
7、外层循环的作用是再循环内部循环
