美文网首页
分解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快速排序算法

    快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法,通过递归的方 式将数据依次分解为包含较小元素和较...

  • 3.2 快速排序算法

    Chapter3: 更好的查找与排序算法 2. 快速排序算法 1. 什么是快速排序算法 分解数组 A[p..r] ...

  • JS数据结构与算法-快速排序与二分查找算法

    快速排序快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法,通过递归的方式将数据依次分解为包含较小元...

  • 十大算法

    1.归并排序,快速排序和堆排序 2.比例积分微分算法 3.整数因式分解 4.安全哈希算法 5.傅立叶变换与快速傅立...

  • JS实现排序算法

    原文:常见排序算法之JavaScript实现 - 知乎 目录 冒泡排序 选择排序 插入排序 合并排序 快速排序 1...

  • JavaScript实现经典排序算法

    使用JavaScript实现的经典排序算法 util 冒泡 简单选择 直接插入 快速排序 堆排序 归并排序

  • 分解javascript 堆排序算法

    掌握算法,先理解原理 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉...

  • 分解javascript 选择排序算法

    掌握算法,先理解原理 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序...

  • 分解javascript 希尔排序算法

    掌握算法,先理解原理 希尔排序,利用插入排序的简单,又要克服插入排序一次只能交换相邻两个数的缺点。看下面两张图的两...

  • 分解javascript冒泡排序算法

    掌握算法,先理解原理 一趟冒泡 交换位置: 很好理解,我们a,b 交换位置,我们先把a 移走,然后再把b 放进a,...

网友评论

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

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