JavaScript经典排序算法——快速排序

╰半夏微凉° 2022-05-26 05:06 239阅读 0赞

快速排序是对冒泡排序的一种改进。**基本思想**是：通过一趟排序将待排序列分割成独立的两部分，其中一部分序列均比另一部分序列的元素小，则可分别对这两部分序列继续进行排序，以达到整个序列有序。

首先在待排序记录中选取一个元素作为**基准（pivot）**，然后将所有小于它的元素都安置在它的左边，所有大于它的元素都安置在它的右边。由此可以将该”枢轴“最后所落的位置i作为分界线，将原序列分为两个子序列R1……Ri-1和Ri+1……Rn。这个过程称为一趟快速排序。

一趟快速排序的具体做法是：设置两个指针i和j，开始时，i指向第一个元素，j指向最后一个元素，然后从j所指位置起向前搜索找到第一个小于”基准“的元素与”基准“进行互换，接着从i所指位置开始向后搜索，找到第一个大于”基准“的元素与”基准“进行互换，重复这两步直至i=j。

步骤分析：

第一步：找基准，一般是将第一个元素作为基准；

第二步：遍历序列，把所有小于“ 基准 ” 的元素放在left子序列中，大于“ 基准 ” 的放在right子序列中；

第三步：对分割的两个子序列进行递归上述两步，直至整个序列有序。

## 动图演示： ##

![20180425165633657][]

## 快速排序过程： ##

![20180425170041518][]

## JavaScript代码实现： ##

[20180425165633657]: /images/20220526/09dbc0592ec24b11a8a0994902667a3a.png
[20180425170041518]: /images/20220526/695b8bc241a848579b4636816cf33d11.png

还没有评论，来说两句吧...