快速排序

快速排序英文名quick sort，又城划分排序，是对冒泡排序的一种改进，是目前所有排序算法中最快的一种。

快速排序：快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

分治法：在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。平均情况下需要logn轮，因此快速排序算法的平均时间复杂度是O（nlogn）。快速排序的平均时间复杂度是 O（nlogn），最坏情况下的时间复杂度是 O（n^2）。

基准元素的选择：基准元素，英文pivot，用于在分治过程中以此为中心，把其他元素移动到基准元素的左右两边。

挖坑法

var arr = [4, 7, 6, 5, 3, 2, 8, 1]
// 挖坑法
console.log('排序前的arr:' + arr + "长度" +arr.length+ "\n")
quickSort(arr,0,arr.length-1)
console.log('quickSort排序后的arr:' + arr)
function quickSort(arr, startIndex, endIndex) {
    // 取第一个元素作为基准值
    var pivot = arr[startIndex]
    var left = startIndex
    var right = endIndex
    // 坑的位置,初始等于pivot
    var index = startIndex

    // 大循环在左右指针重合或者交错时结束
    while (right >= left) {
        // right指针从右向左比较
        while (right >= left) {
            if (arr[right] < pivot) {
                arr[left] = arr[right]
                index = right
                left++
                console.log("right右向左数组right" + right + "个位置left" + left + "个位置" + "index值为" + index + "数组为" + arr)
                break
            }
            right--
        }

         // left指针从左向右比较
        while (right >= left) {
            if (arr[left] > pivot) {
                arr[right] = arr[left]
                index = left
                right--
                console.log("left左向右数组left" + left + "个位置rigth" + right + "个位置" + "index值为" + index + "数组为" + arr + "\n")
                break
            }
            left++
        }
    }
    arr[index] = pivot
    console.log("index的值为" + index)
    return index
}