首頁 >web前端 >js教程 >程式碼詳解JavaScript如何實現快速排序

程式碼詳解JavaScript如何實現快速排序

零到壹度
零到壹度原創
2018-04-10 10:27:442368瀏覽

本篇文章給大家分享的內容是JavaScript如何實現快速排序,有著一定的參考價值,有需要的朋友可以參考一下

偶然看到阮一峰老師博客中幾年前的快速排序演算法,每次循環一次都要創建兩個額外數組,如果資料量大的話要佔用不少額外記憶體。但是數組是引用型,是可修改的,可以直接操作原數組本身來節約記憶體。

快速排序方法的關鍵在於選取一個值,將整個陣列分成兩部分,小的在左,大的在右,下面就是這個函數的寫法:

//该函数的主要目的是交换数组中两个元素的位置
function swap(arr, index1, index2) {

    let data = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = arr[index1];

    //数组是引用类型,允许修改原数组。
}

//选取随机值,将数组分为两部分
function partition(arr, start, end) {
    let keyIndex = end,
        key = arr[keyIndex]; //将随机值(以后称key值)定为最后一个数,也可以真的随机选取,见下一行
    // let keyIndex = Math.floor(Math.random() * (end - start)) + start;

    let i = start,
        j = end,
        order = true;
    //当order为true时正向筛选,当order为false时逆向筛选
    //先从正向开始,因为我们把key值保存到了数组的结尾处。
    while(i != j) {
        if(order) {
            //正向筛选
            if (arr[i]>key) {
                swap(arr, i, j); //将大于key的数字和key进行交换
                order = false;
            } else {
                i++;
            }

        } else {
            //逆向筛选
            if(arr[j]<key) {
                swap(arr, i, j); //将小于key的数字和key进行交换
                order = true;
            } else {
                j--;
            }
        }
    }
    return i;//返回key值最终的位置
}

觀察分組演算法partition不難發現,其實i和j位置上總是有一個存key值,然後和比它大或比它小的值交換。那我們也可以將其寫成單向的分組方法:

function partition2(arr, start, end) {
    let keyIndex = end,
        key = arr[end];
    let i = start -1,
        j = start;
    for (;j<end;j++) {
        if (arr[j]< key) {
        // i位置的值永远比key值小
            i++;
            if (i != j) {
                swap(arr, i, j);
            }
        }
    } 
    ++i;
    swap(arr, i, end);

    return i; //返回key值最终的位置
}

接下來遞歸呼叫分組函數,將整個陣列排序:

function quickSort(arr, start, end) {
    if (start == end) return;
    let index = partition(arr, start, end);
    if (index > start){
        quickSort(arr, start, index-1);
    }
    if (index<end) {
        quickSort(arr, index+1, end);
    }
}

#相關推薦:

快速排序兩種方式實作及最佳化總結

#快速排序原理及java實作

#C 實作快速排序

以上是程式碼詳解JavaScript如何實現快速排序的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn