算法系列(二)

  长时间没接着写了,今天接着未完成的革命,接下来就是快速排序:

  快速排序的思想就是先选取一个基准点,然后将小于基准点的放在基准点的左边,大于基准点的数放在基准点右边,然后将左、右边的数组再重复上述步骤直到全部排序完成。

  还是如数组:20 、40、50、10、60       

left指针指向20,right指针指向60,base参照数指向20。

其实思想是蛮简单的,就是通过第一遍的遍历(让left和right指针重合)来找到数组的切割点。

第一步:首先我们从数组的left位置取出该数(20)作为基准(base)参照物。

第二步:从数组的right位置向前找,一直找到比(base)小的数,

            如果找到,将此数赋给left位置(也就是将10赋给20),

            此时数组为:10,40,50,10,60,

            left和right指针分别为前后的10。

第三步:从数组的left位置向后找,一直找到比(base)大的数,

             如果找到,将此数赋给right的位置(也就是40赋给10),

             此时数组为:10,40,50,40,60,

             left和right指针分别为前后的40。

第四步:重复“第二,第三“步骤,直到left和right指针重合,

             最后将(base)插入到40的位置,

             此时数组值为: 10,20,50,40,60,至此完成一次排序。

第五步:此时20已经潜入到数组的内部,20的左侧一组数都比20小,20的右侧作为一组数都比20大,

            以20为切入点对左右两边数按照"第一,第二,第三,第四"步骤进行,最终快排大功告成。

附上JS实现代码:

 1     //快速排序
 2     function QuickSort(arr,left,right){
 3     if (left <right ){
 4         var i=Division(arr,left ,right );//获得下次分割的基准位置
 5         
 6         QuickSort (arr,left ,i-1);//基准位置左侧进行递归排序
 7         QuickSort (arr ,i+1,right );//基准位置右侧进行递归排序
 8         }
 9         return arr;
10     }
11     
12     function Division(arr,left,right){
13          var baseItem=arr[left ];  //将左指针作为基准数     
14     while (left <right ){//只要两指针未重合就一直执行
15             while (left <right && arr[right] >=baseItem ){//对右指针向左侧移动,直到找到比基准数小的值
16             right --;
17             }
18             arr [left ]=arr[right ];//将找到的值赋给左指针
19             
20             while (left <right && arr[left ] <= baseItem ){//对左指针向右侧移动,直到找到比基准值大的值
21                     left ++;
22                 }
23                 arr[right ]=arr[left ];//将找到的值赋给右指针
24          }
25         arr[left ]=baseItem ;//两针重合后将基准值赋给左指针;最终,我们发现left位置的左侧数值部分比left小,left位置右侧数值比left大
26         return left ;//返回重合后此时的指针位置
27     }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大内老A

深入理解C# 3.x的新特性(2):Extension Method[上篇]

在C#3.0中,引入了一些列新的特性,比如: Implicitly typed local variable, Extension method,Lambda ...

19860
来自专栏小樱的经验随笔

【批处理学习笔记】第二十一课:数值计算

    批处理里面的数值计算功能较弱,只能够进行整型计算,忽略浮点数的小数部分;同时数值计算的范围也受限于系统位数,对于目前较为常见的32位机来说,数值计算能处...

29040
来自专栏CSDN技术头条

Python编程中的反模式

这篇文章收集了我在Python新手开发者写的代码中所见到的不规范但偶尔又很微妙的问题。本文的目的是为了帮助那些新手开发者渡过写出丑陋的Python代码的阶段。为...

21760
来自专栏C/C++基础

C++智能指针

C++中,动态内存的管理是通过一对运算符来完成的,new用于申请内存空间,调用对象构造函数初始化对象并返回指向该对象的指针。delete接收一个动态对象的指针,...

29510
来自专栏chenjx85的技术专栏

leetcode-496-Next Greater Element I

16260
来自专栏前端下午茶

JS 原型模式

原型模式(Prototype pattern),用原型实例指向创建对象的类,使用于创建新的对象的类的共享原型的属性与方法。

39410
来自专栏java学习

Java每日一练(2017/7/21)

聊天系统 ●我希望大家积极参与答题!有什么不懂可以加小编微信进行讨论 ★珍惜每一天,拼搏每一天,专心每一天,成功每一 如果你是初学者,或者是自学者!你可以加小编...

34740
来自专栏angularejs学习篇

js中对arry数组的各种操作小结

  最近工作比较轻松,于是就花时间从头到尾的对js进行了详细的学习和复习,在看书的过程中,发现自己平时在做项目的过程中有很多地方想得不过全面,写的不够合理,所以...

23820
来自专栏向治洪

迭代器模式

迭代器模式(Iterator): 提供一种方法顺序访问一个聚合对象中的各个元素,而又不暴露其内部的表示。 用途:在软件构建过程中,集合对象内部结构常常变化各异。...

198100
来自专栏分布式系统和大数据处理

四种简单的排序算法

我觉得如果想成为一名优秀的开发者,不仅要积极学习时下流行的新技术,比如WCF、Asp.Net MVC、AJAX等,熟练应用一些已经比较成熟的技术,比如Asp.N...

15020

扫码关注云+社区

领取腾讯云代金券