快速排序

  //创建列表类
        function ArrayList() {
            this.array = []
            ArrayList.prototype.insert = function (item) {
                this.array.push(item)
            }
            ArrayList.prototype.toString = function () {
                return this.array.join('-')
            }
            //交换两个数据的位置
            ArrayList.prototype.swap = function (m, n) {
                var temp = this.array[m]
                this.array[m] = this.array[n]
                this.array[n] = temp
            }
     ArrayList.prototype.median = function (left, right) {
                //取出中间的位置
                var 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[right]) {
                    this.swap(left, right)
                }
                //将center换到right-1的位置
                this.swap(center, right - 1)
                return this.array[right - 1]
            }
            ArrayList.prototype.quick = function () {
                this.quickSort(0, this.array.length - 1)
            }
            ArrayList.prototype.quickSort = function (left, right) {
                //借宿条件
                if (left >= right) return
                //获取枢纽
                var pivot = this.median(left, right)
                var i = left
                var j = right - 1
                // 进行交换
                while (true) {
                    while (this.array[++i] < pivot) {

                    }
                    while (this.array[--j] > pivot) {

                    }
                    if (i < j) {
                        this.swap(i, j)
                    } else {
                        break
                    }
                }
                this.swap(i, right - 1)
                this.quickSort(left, i - 1)
                this.quickSort(i + 1, right)

            }
        }

        var list = new ArrayList()
        list.insert(1)
        list.insert(5)
        list.insert(2)
        list.insert(3)
        list.insert(4)
        list.quick()
        alert(list)

快速排序

 

上一篇:从python来看数据结构基础


下一篇:学生管理系统查看所有学生升级判空