编辑代码

var array = []

console.log('== 快速排序 ==\n')

console.log(`快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn)，且它的性能通常比其他的复
杂度为O(nlogn)的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分
为较小的数组（但它没有像归并排序那样将它们分割开）。\n`)


function createRandomArray(size) {
    var arr = []
    for (let i = 0; i < size; i++) {
        arr.push(Math.round(Math.random() * size))
    }
    array = arr
    return arr
}

function mergeSort() {

}
/**
 * 快速排序--分而治之
 */
function quick(array, left, right) {
    var index


    if (array.length > 1) {
        // 找出主元并交换左右位置
        index = partition(array, left, right)
        console.log('新下标', index)
        console.log('排序 array:', array)

        if (left < index - 1) {
            quick(array, left, index - 1)
        }

        if (index < right) {
            quick(array, index, right)
        }
    } else {
        return array
    }

}
/** 
 * 【1,4,7,6,8,4,9】
 * 找出左侧比主元大的值7，右侧比主元小的值4 交换位置得
 * 【1,4,4,6,8,7,9】,i++,j-- i=3 j=4
 * left终止,j-- j=3 交换空气i++,j-- 返回index=4
 * 
 * 排序[1,4,4,6,`8`,7,9]
 * 1,4,4,6排个寂寞index=3再排[1,4,4]直到index=0终止
 * [8,7,9]排序得[7,8,9]
 * 最终得[1,4,4,6,7，8,9]
 * 
*/
function partition(array, left, right) {
    // 找出中间数主元
    var pivot = array[Math.floor((left + right) / 2)],
        i = left,
        j = right

    console.log('主元', pivot)

    // 如【1,4,7,6,8,4,9】
    while (i <= j) {
        // 找出左侧比主元大的数
        // 如主元6,1<6 i++,4<6 i++,7>6 得i=2
        while (array[i] < pivot) {
            i++
            console.log('i++', i)
        }
        // 找出右侧比主元小的数
        // 如主元6 9>6 j--,4<6 j=5
        while (array[j] > pivot) {
            j--
            console.log('j--', j)
        }

        if (i < j) {
            console.log('i<j111111111')
            // 交换左右数据
            swapQuickSort(array, i, j)
            i++
            j--

        }

    }

    return i
}

function swapQuickSort(array, index1, index2) {
    var aux = array[index1]
    array[index1] = array[index2]
    array[index2] = aux

}


function quickSort() {
    quick(array, 0, array.length - 1)
}


createRandomArray(9)
console.log('排序前：', array + '\n')
console.time('耗时')
quickSort()
console.timeEnd('耗时')
console.log('排序后数组：', array)