美文网首页
分解javascript快速排序算法

分解javascript快速排序算法

作者: Searchen | 来源:发表于2018-05-30 23:46 被阅读8次

    快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法,通过递归的方 式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直 到所有数据都是有序的。

    这个算法首先要在列表中选择一个元素作为基准值(pivot)。数据排序围绕基准值进行, 将列表中小于基准值的元素移到数组的底部,将大于基准值的元素移到数组的顶部。

    实现一:

    快速排序
    function quickSort(arr) {  
        if (arr.length <= 1) {
            return arr;
        }  
        var pivotIndex = Math.floor(arr.length / 2); //取中间值
        var pivot = arr.splice(pivotIndex, 1)[0];  //基准元素
        var left = [];  
        var right = [];  
        for (var i = 0; i < arr.length; i++) {    
            if (arr[i] < pivot) {      
                left.push(arr[i]);    
            } else {      
                right.push(arr[i]);    
            }  
        }  
        return quickSort(left).concat([pivot], quickSort(right));
    }
    

    上面简单版本的缺点是,它需要Ω(n)的额外存储空间,也就跟归并排序一样不好。额外需要的存储器空间配置,在实际上的实现,也会极度影响速度和高速缓存的性能。

    摘自维基百科

    按照维基百科中的原地(in-place)分区版本,实现快速排序方法如下:

    function quickSort(array) {
        // 交换元素位置
        function swap(array, i, k) {
            var temp = array[i];
            array[i] = array[k];
            array[k] = temp;
        }
        // 数组分区,左小右大
        function partition(array, left, right) {
            var storeIndex = left;
            var pivot = array[right]; // 直接选最右边的元素为基准元素
            for (var i = left; i < right; i++) {
                if (array[i] < pivot) {
                    swap(array, storeIndex, i);
                    storeIndex++; // 交换位置后,storeIndex 自增 1,代表下一个可能要交换的位置
                }
            }
            swap(array, right, storeIndex); // 将基准元素放置到最后的正确位置上
            return storeIndex;
        }
        function sort(array, left, right) {
            if (left > right) {
                return;
            }
            var storeIndex = partition(array, left, right);
            sort(array, left, storeIndex - 1);  //递归整理左部分
            sort(array, storeIndex + 1, right); // 递归整理右部分
        }
        sort(array, 0, array.length - 1);
        return array;
    }
    
    var array = [11, 43, 24, 76, 89, 43, 65]
    
    console.log(quickSort(array))
    

    如果不了解原理,这时候可能理解不了。现在一步一步拆分理解.

    1、以6为基准元素,放在数组的最右边,i向右走,j 向左走

    var pivot = array[right]; // 直接选最右边的元素为基准元素
    
    以6为基准元素,放在数组的最右边

    2、 i = 8 > 6 (基元素) j <2 小于基元素 ,这时候
    i 和 j 交换位置,交换完继续走

    for (var i = left; i < right; i++) {
                if (array[i] < pivot) {
                    swap(array, storeIndex, i);
                    storeIndex++; // 交换位置后,storeIndex 自增 1,代表下一个可能要交换的位置
                }
            }
    
    8和2交换位置

    3、走到什么时候呢?走到i 越过 j 的时候,意味着子级划分结束

    swap(array, right, storeIndex); // 将基准元素放置到最后的正确位置上
    
    i 越过 j ,这时候 i = 9 比基数元素大,交换位置

    相关文章

      网友评论

          本文标题:分解javascript快速排序算法

          本文链接:https://www.haomeiwen.com/subject/xdpajftx.html