Detailed code explanation of how JavaScript implements quick sorting

The content of this article is to share with you how to implement quick sorting in JavaScript. It has a certain reference value. Friends in need can refer to it

I accidentally saw Teacher Ruan Yifeng’s blog A quick sorting algorithm from a few years ago in China created two additional arrays each time it was looped. If the amount of data is large, it will take up a lot of extra memory. However, arrays are reference types and can be modified. The original array itself can be directly manipulated to save memory.

The key to the quick sort method is to select a value and divide the entire array into two parts, the small one on the left and the large one on the right. Here is how this function is written:

//该函数的主要目的是交换数组中两个元素的位置
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值最终的位置
}

Observe the grouping It is not difficult to find in the algorithm partition. In fact, there is always a key value stored in the i and j positions, and then it is exchanged with a value larger or smaller than it. Then we can also write it as a one-way grouping method:

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值最终的位置
}

Next, call the grouping function recursively to sort the entire array:

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);
    }
}

Related recommendations:

Summary of implementation and optimization of two methods of quick sort

Quick sort principle and java implementation

C++ implementation of quick sort

The above is the detailed content of Detailed code explanation of how JavaScript implements quick sorting. For more information, please follow other related articles on the PHP Chinese website!