JavaScript实现常见排序算法

本文实现的排序算法有：冒泡排序、选择排序、插入排序、希尔排序、快速排序。

function ArrayList() {
    // 列表的属性
    this.array = []
    // 列表的方法
    // - 插入项
    ArrayList.prototype.insert = function (item) {
        this.array.push(item)
    }
    // - 将列表以字符串形式返回
    ArrayList.prototype.toString = function () {
        return this.array.join(' ')
    }
    // 排序算法
    // - 冒泡排序
    ArrayList.prototype.bubbleSort = function () {
        var length = this.array.length
        for (let j = length - 1; j >= 0; j--) {
            for (let i = 0; i < j; i++) {
                if (this.array[i] > this.array[i + 1]) {
                    this.swap(i, i + 1)
                }
            }
        }
    }
    // - 选择排序
    ArrayList.prototype.selectionSort = function () {
        var length = this.array.length
        for (let j = 0; j < length - 1; j++) {
            var min = j
            for (let i = min + 1; i < length; i++) {    // 从第二个元素，即arr[1]开始与arr[min]比较
                if (this.array[i] < this.array[min]) {
                    min = i
                }
            }
            this.swap(j, min)
        }
    }
    // - 插入排序
    ArrayList.prototype.insertionSort = function () {
        var length = this.array.length
        for (let i = 1; i < length; i++) {
            var cur = this.array[i]
            var j = i   //  这里不用j = i - 1是因为其在不进行循环的情况会出错
            while (cur < this.array[j - 1] && j > 0) {
                this.array[j] = this.array[j - 1]
                j--
            }
            this.array[j] = cur
        }
    }
    // - 希尔排序
    ArrayList.prototype.shellSort = function () {
        var length = this.array.length
        var gap = length / 2 | 0    // 初始化增量gap
        while (gap >= 1) {
            // 以gap作为间隔，对数据进行分组，组内进行插入排序
            for (let i = gap; i < length; i++) {
                var cur = this.array[i]
                var j = i
                while (cur < this.array[j - gap] && j > gap - 1) {
                    this.array[j] = this.array[j - gap]
                    j -= gap
                }
                this.array[j] = cur
            }
            gap = gap / 2 | 0   // 按照N/2逐步减小增量
        }
    }
    // - 快速排序
    ArrayList.prototype.quickSort = function () {
        this.quick(0, this.array.length - 1)
    }
    // - 快速排序的递归函数
    ArrayList.prototype.quick = function (left, right) {
        if (left >= right) return  // 结束条件
        var pivot = this.median(left, right)     // 获取枢纽
        var i = left    // 左指针（默认指向首项）
        var j = right - 1   // 右指针（默认指向倒数第二项）
        while (i < j) {     // true => i < j，修复了第一轮循环出现i=j的bug
            while (this.array[++i] < pivot) { }  // 左指针向右移动，直到找到大于枢纽的元素
            while (this.array[--j] > pivot) { }   // 右指针向左移动，直到找到小于枢纽的元素
            if (i >= j) {
                break   // 左指针和右指针重合时退出循环
            } else {
                this.swap(i, j)     // 交换左右指针指向的元素
            }
        }
        this.swap(i, right - 1)     // 左指针i停留的位置即枢纽在序列中正确的位置
        this.quick(left, i - 1)     // 对枢纽左边的序列再次进行快速排序
        this.quick(i + 1, right)    // 对枢纽右边的序列再次进行快速排序
    }
    // - 交换元素
    ArrayList.prototype.swap = function (m, n) {
        [this.array[m], this.array[n]] = [this.array[n], this.array[m]]
    }
    // - 获取中位数并作为枢纽返回（快速排序）
    ArrayList.prototype.median = function (left, right) {
        var center = (left + right) / 2 | 0
        if (this.array[left] > this.array[center]) {
            this.swap(left, center)
        }
        if (this.array[left] > this.array[right]) {
            this.swap(left, right)
        }
        if (this.array[center] > this.array[right]) {
            this.swap(center, right)
        }
        this.swap(center, right - 1)
        return this.array[right - 1]
    }
}
// 使用排序算法
var list = new ArrayList()
list.insert(97)
list.insert(35)
list.insert(12)
list.insert(9)
list.insert(20)
list.insert(66)
list.insert(77)
list.insert(45)
list.insert(2)
list.insert(6)
list.quickSort()
alert(list.toString())