资讯专栏INFORMATION COLUMN

快速排序思想及实现

biaoxiaoduan / 1823人阅读

摘要:思想快速排序的思想很简单,整个排序过程只需要三步在数据集之中,找一个基准点建立两个数组,分别存储左边和右边的数组利用递归进行下次比较实现如果数组只有一个数,就直接返回找到中间数的索引值,如果是浮点数,则向下取整找到中间数的值

思想

"快速排序"的思想很简单,整个排序过程只需要三步:

(1)在数据集之中,找一个基准点

(2)建立两个数组,分别存储左边和右边的数组

(3)利用递归进行下次比较

JS实现
var needSortArr = [12, 23, 45, 11, 2, 55, 12, 1];
function quickSort (arr) {
    if (arr.length <= 1) {
        return arr;         //如果数组只有一个数,就直接返回;
    }
    var num = Math.floor(arr.length / 2),        //找到中间数的索引值,如果是浮点数,则向下取整
        numberOfCenter = arr.splice(num, 1),     //找到中间数的值
        left = [], right = [];
    for(var i = 0; i < arr.length; i++) {
        if (arr[i] < numberOfCenter) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([numberOfCenter], quickSort(right));
}
alert(quickSort(needSortArr));

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/80699.html

相关文章

  • 排序之八大绝技

    摘要:需要注意的是排升序要建大堆,排降序建小堆。应用场景需要前个最大或最小元素时,或者与其他排序一块使用五冒泡排序排序思想大的元素向下沉,小的元素向上浮。 目录 一.插入排序 1.插入排序思想 2.动态图形演示  3.插排思路与图解 4.插入排序代码实现(升序) 5.时间复杂度,空间复杂度及稳定...

    Vixb 评论0 收藏0
  • 快速排序优化

    摘要:快速排序的核心是以基数为中心,将数组分为两个区间,小于基数的放到基数的左边,大于基数的放到基数的右边。快速排序在每次挖坑的过程中,需要个空间存储基数。而快速排序的大概需要次的处理,所以占用空间也是个。 快速排序 原理 快速排序是C.R.A.Hoare提出的一种交换排序。它采用分治的策略,所以也称其为分治排序。 实现快速排序算法的关键在于,先在数组中选一个数作为基数,接着以基数为中心将数...

    zhaochunqi 评论0 收藏0
  • Java数据结构与算法——快速排序

    摘要:快排是一种不稳定的排序算法,在经过排序后,等值的元素的相对位置可能发生改变。 声明:码字不易,转载请注明出处,欢迎文章下方讨论交流。 前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本篇文章介绍排序算法中最常用也是面试中最容易考到的排序算法——快排,包括快排的思想和原理、java快排代码、快排的特点性能和快排的适用场景。 0、其他排序算法索引(待更) java数据结构与...

    Panda 评论0 收藏0
  • JavaScript 数据结构与算法之美 - 归并排序快速排序、希尔排序、堆排序

    摘要:之所以把归并排序快速排序希尔排序堆排序放在一起比较,是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此,快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法为王。 想学好前端,先练好内功,只有内功深厚者,前端之路才...

    haitiancoder 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<