排序算法

选择排序

• 每次循环从待排序的数据中选出最小值，放在已排序数据的末尾

for (i = 0; i < arr.length; i++) {
    // 假设arr[i]为最小值
    var minIndex = i
    for (j = i+1; j < arr.length; j++) {
        if (arr[minIndex] > arr[j]) {
            // 找到更小的值，更新minIndex
            minIndex = j
        }
    }
    // 最小值和arr[i]交换位置
    var temp = arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = temp
}

冒泡排序

• 相邻元素之间比较
• 每次内循环一定是把最大的元素放到最后（假设a是最大的元素，其他元素（都比他小）与他比较之后都会进行交换，a一直往右挪）
• 所以结束条件可以设置为全部最大元素都排好序了

// 外循环  j可以看作已排好序的元素个数
for (j = 0; j < arr.length - 1; j++) {
    // 内循环 把最大的元素放到最后
    for (i = 0; i < arr.length - 1 - j; i++) {
        if (arr[i] > arr[i+1]) {
            // 交换
            temp = arr[i]
            arr[i] = arr[i+1]
            arr[i+1] = temp
        }
    }
}

插入排序

• 从第一个元素开始排序（因为默认第0个元素是有序的）
• 第n个元素会和第n-k（1 <= k <= n）个元素比较，直到找到了合适的位置
• 非常适合用于对几乎有序的数据排序
• 和希尔排序的思想是一样的

for (i = 1; i < arr.length; i++) {
    // key与前面的数据比较
    key = arr[i]
    for (j = i-1; j >= 0; j--) {
        if (arr[j] > key) {
            // 交换位置
            arr[j+1] = arr[j]
            arr[j] = key
        }
        // 前面（有序的）没有比key大的值了，找到了合适的位置
        else
            break
    }
}

/********************************
**优化  找到最合适的位置才进行交换
*********************************/

for (i = 1; i < arr.length; i++) {
    // key与前面的数据比较
    var key = arr[i]
    var j
    for (j = i-1; j >= 0; j--) {
        if (arr[j] > key) {
            // 比key大的值往后挪一位
            arr[j+1] = arr[j]
        }
        else
            break 
    }
    arr[j+1] = key
}

希尔排序

归并排序

• 将排好序的两个子数组归并成一个有序数组

自顶向下

• 一直将数组划分为一半（得到两个子数组）直到子数组元素个数为1
• 归并：两个子数组元素比较排序，得到一个有序数组

// 分
function Sort(arr, left, right) {
    if (left >= right){
        // 只有一个元素了
        return
    }

    // (left + right) 可能溢出
    // parseInt(left + (right-left) / 2)
    var mid = parseInt((left + right) / 2)
    // 左边
    Sort(arr, left, mid)
    // 右边
    Sort(arr, mid + 1, right)
    // 自顶向下到了底层
    // 如果左边最后一个元素 < = 右边第一个元素  不用merge
    if (arr[mid] > arr[mid+1]) {
        Merge(arr, left, mid, mid + 1, right)
    }
}

function Merge (arr, leftStart, leftEnd, rightStart, rightEnd) {
    // 全部复制
    // var temp = arr.concat([])

    // 只复制需要的部分 不能用splice
    var i = 0
    var j = leftStart
    var temp = []
    while (j <= rightEnd) {
        temp[i++] = arr[j++]
    }

    // temp的leftStart
    i = 0

    // temp的leftEnd
    var iend = leftEnd - leftStart

    // temp的rightStart
    j = rightStart - leftStart

    // temp的rightEnd
    var jend = rightEnd - leftStart

    while (i <= iend && j <= jend) {
        if (temp[i] < temp[j]) {
            arr[leftStart++] = temp[i++]
        } else {
            arr[leftStart++] = temp[j++]
        }
    }
    /************不写下面代码也行************ 
    *** 修改 while (i <= iend || j <= jend)
    *** 判断的时候 数据undefined  false  走else分支  也能将剩下部分复制
    ***************************************/

/***********可忽略部分开始*************/
    // 越界 将剩下部分全部复制
    if(i > iend) {
        while (j <= jend) {
            arr[leftStart++] = temp[j++]
        }
    } else {
        while (i <= iend) {
            arr[leftStart++] = temp[i++]
        }
    }
/***********可忽略部分结束*************/
}

var array = [21,32,43,98,54,45,23,4,66,86,30]
Sort(array, 0, array.length-1)
console.log(array)

自底向上（链表更适合）

for (i = 1; i < arr.length; i += i) {
    // i 表示子数组元素个数
    // j 表示子数组开始位置
    for (j = 0; j + i < arr.length; j += i + i) {
        // rightStart < arr.length  右边存在
        // 如果右边不存在 说明不用merge  且左边已经排好序了
        // Merge
        Merge(arr, j, j + i -1, j + i, Math.min(arr.length - 1, j + i + i - 1))
        // leftStart = j
        // leftEnd = j + i -1
        // rightStart = j + i
        // rightEnd = j + 2*i - 1
        // rightEnd可能越界  min(arr.length - 1, rightEnd)
        // Merge(arr, j, j + i -1, j + i, j + i + i - 1)  
    }
}

// 自底向上举个例子                        i        j--------->
// 1 1 1 1 1 1 1 1 1 1 1 1               1        0     2    4
// 11  11  11  11 11  11                 2        0     4    8
// 1111   1111   1111                    4        0     8    16
// 11111111      1111                    8        0     16   32

快速排序

• 设数组的第一个元素为key
• 将数组分为大于key和小于key的部分
• 设定两个指针：left 指向数组第0个元素，right指向最后一个元素
• 从后向前，找小于key的值，找到，交换arr[left]和arr[right]，left++
• 从前往后，找大于key的值，找到，交换arr[left]和arr[right]，right--，继续从后向前找
• 当 left >= right，已将数组分为大于key和小于key的部分
• 每个部分又进行快排

function Quick (arr, left, right) {
    var originLeft = left
    var originRight = right
    var key = arr[left]
    while (left < right) {
        // 从后往前 找小于key的值  找到就结束
        for (; left < right; right--) {
            // 找到  交换  小的挪前面  left++  结束
            if (arr[right] < key) {
                arr[left++] = arr[right]
                arr[right] = key
                break
            }
        }

        // 从前往后 找大于key的值  找到就结束
        for (; left < right; left++) {
            // 找到  交换  大的挪后面  right-- 结束
            if (arr[left] > key) {
                arr[right--] = arr[left]
                arr[left] = key
                break
            }
        }
    }

    // left >= right  已经分成两部分了
    // [originLeft, left - 1] <= key <= [left + 1, originRight]

    // [originLeft, left - 1]  区间元素个数 > 1
    if (left - 1 > originLeft) {
        Quick(arr, originLeft, left - 1)
    }
    
    // [left + 1, originRight]   区间元素个数 > 1
    if (originRight > left + 1) {
        Quick(arr, left + 1, originRight)
    }
}

var arr = [21,15,32,43,98,54,45,23,4,66,86]
Quick (arr, 0, arr.length-1)
console.log(arr)

快排缺点

• 在几乎有序的数据排序，效率不好，因为查找树不平衡
• 解决：随机决定key，不选arr[left]为key

/******随机指定key*************
*******减少交换次数************/
function Quick (arr, left, right) {
    var originLeft = left
    var originRight = right

    // 得到在闭区间[left, right] 的随机数
    var random = parseInt(Math.random() * (right - left + 1) + left)

    // 随机指定key
    var key = arr[random]

    // 交换arr[random] 和 arr[left] 
    arr[random] = arr[left]
    arr[left] = key
 
    while (left < right) {
        while (left < right) {
            if (arr[right] < key) {
                // 先不交换
                break
            }
            right--
        }

        while (left < right) {
            if (arr[left] > key) {
                // 交换
                var temp = arr[left]
                arr[left] = arr[right]
                arr[right--] = temp
                break
                // 交换后不能left++  left一定要指向小于等于key部分的最后一个元素
                // 因为最后会用left的位置保存key
                // arr[oringLeft] = arr[left]
            }
            left++
        }
    }

    // left == right  将小于等于key部分的最后一个元素 和 key 的交换
    arr[originLeft] = arr[left]
    arr[left] = key

    // 已经分成两部分了
    // [originLeft,left - 1] <= key <= [left + 1, originRight]
    if (left - 1 > originLeft) {
        Quick(arr, originLeft, left - 1)
    }

    if (originRight > left + 1) {
        Quick(arr, left + 1, originRight)
    }
}

var array = [21,32,78,43,98,54,23,4,56,43,45,6,86,30]
Quick(array, 0, array.length-1)
console.log(array)

堆排序

• 主要用于动态数组的排序，优先级操作

二叉堆

• 树状结构，每个父节点最多只有2个子节点
• 一定从左到右填满整层

最大堆

• 父节点一定大于子节点的二叉堆

堆索引从1开始，如下图（图片来自网络）

• 假设 i 是parent 的索引
  leftChild 的索引：2 * i
  rightChild 的索引：2 * i + 1

• 假设 i 是child 的索引
  parent 的索引：parseInt( i / 2 )

  
  heap1.jpg

堆索引从0开始，如下图（图片来自网络）

• 假设 i 是parent 的索引
  leftChild 的索引：2 * i + 1
  rightChild 的索引：2 * i + 2

• 假设 i 是child 的索引
  parent的索引：parseInt(( i - 1 ) / 2)

  
  heap0.jpg

构建最大堆，堆索引从1开始

• 新插入的元素和父节点比较，小于，直接插入，大于，父节点变为子节点，再和父节点的父节点比较（shiftUp）...
• 父节点可能没有父节点了
• 可以不开辟新空间，直接对传入的数据进行操作

function MaxHeap (arr) {
    var heap = []
    // 孩子节点
    var childIndex
    // 父节点
    var parentIndex 

    // 堆的索引从1开始 
    // index指向数据要插入的位置
    var index = 1

    // 遍历arr
    var i = 0
    while (i < arr.length) {
        childIndex = index
        parentIndex = parseInt(childIndex / 2)
        // 插入值 <= 父节点
        // heap[0]  undefined
        if (arr[i] <= heap[parentIndex] || heap[parentIndex] === undefined) {
            // 直接插入
            heap[index++] = arr[i++]
        } else {
            // 父节点 < 插入值   shift up
            // 新增节点的值 = 父节点的值
            heap[index++] = heap[parentIndex]
            // 新孩子节点 指向  当前父节点
            // 新父节点   指向  新孩子节点的父节点
            childIndex = parentIndex
            parentIndex = parseInt(childIndex / 2)

            // heap[childIndex]可以保存arr[i]？看父节点值  
            while (heap[parentIndex] < arr[i]) {
                // 父节点 < 插入值
                heap[childIndex] = heap[parentIndex]
                // 更新 childIndex  parentIndex
                childIndex = parentIndex
                parentIndex = parseInt(childIndex / 2)
                // 可能 parentIndex === 0
                // heap[0] === undefined
                // undefined 和数字比较都是false
            }
            heap[childIndex] = arr[i++]
        }
    }
    console.log(heap)
    return heap
}

弹出最大值，保持最大堆性质

• 输出第一个元素，令第一个元素 = 最后一个元素，删除最后一个元素
• shiftDown：从根节点开始，如果孩子节点 > 父节点，父节点和大的孩子节点交换，直到符合最大堆
• 可能没有右孩子

function DelMaxHeap(heap) {
    // 父节点
    var parent = 1
    // 取第一个元素 第0位是空的
    console.log('取出第一个元素：'+heap[parent])

    // 将最后一个元素放在根节点
    heap[parent] = heap[heap.length-1]

    // 删除最后一个元素
    heap.pop()

    // 左孩子
    var child = 2
    // 左右孩子比较
    // 存在 孩子比父节点大
    // 这个是有了两个孩子的情况 
    // while (child < heap.length-1 && Math.max(heap[child], heap[child+1]) > heap[parent]) {

    
    while (child < heap.length-1) {
        // 一定有左孩子  右孩子不一定有
        // 左孩子 > 父节点  || 右孩子 > 父节点
        if (heap[child] > heap[parent] || heap[child+1] > heap[parent]) {
            if (heap[child] < heap[child + 1]) {
                // 左孩子 < 右孩子
                // 父节点和右孩子交换
                let temp = heap[child + 1]
                heap[child + 1] = heap[parent]
                heap[parent] = temp
                // 更新parent 位置 = 右孩子的位置
                parent = child + 1
            } else {
                // 左孩子 >= 右孩子
                // 父节点和左孩子交换
                let temp = heap[child]
                heap[child] = heap[parent]
                heap[parent] = temp
                // 更新parent 位置 = 左孩子的位置
                parent = child
            }
            // 更新 child 位置
            child = 2 * parent
        } else {
            // 左右孩子 <= 父节点 
            // 左孩子 <= 父节点 && 右孩子不存在
            break
        }
    }
    console.log(heap)
}

/*************以下简化版***********
**********************************/
function DelMaxHeap(heap) {
    // 父节点
    var parent = 1
    // 取第一个元素 第0位是空的
    console.log('取出第一个元素：'+heap[parent])

    // 最后一个元素放根节点
    heap[parent] = heap[heap.length-1]

    // 删除最后一个元素
    heap.pop()

    // 左孩子
    var child = 2
    // 左右孩子比较
    // 存在 孩子比父节点大

    while (child < heap.length-1) {
        // 一定有左孩子  右孩子不一定有
        if (heap[child] < heap[child+1]) {
                // 左孩子 < 右孩子
                child = child+1
        }
        // 父节点和大的孩子交换
        if (heap[child] > heap[parent]) {
            let temp = heap[child]
            heap[child] = heap[parent]
            heap[parent] = temp
            // 更新parent 位置 = 左孩子的位置
            parent = child
            // 更新 child 位置
            child = 2 * parent
        } else {
            // 左右孩子 <= 父节点 
            // 左孩子 <= 父节点 && 右孩子不存在
            break
        }
    }
    console.log(heap)
}