排序算法之快速排序

概述

快速排序算法是基于交换的高效排序算法, 采用了分治的思想.

其基本思想如下:

  1. 从数列中取出一个数作为基准数
  2. 将数组进行划分, 将比基准数大的元素移至右侧, 比基准数小的元素移至左侧
  3. 对左右的子区间重复进行排序, 直至每个子区间只有一个元素

15370881372550a9b795b7b (811×252)

其时间空间复杂度如下:

1537078413518a139f5fcc7 (586×80)

快速排序就是将小的放左边, 大的放右边, 在对左右进行重复执行.

其代码实现如下:

1537078624950c34257242d (640×799)

同时, 快速排序也可以进行三切分, 分为大于、等于、小于三组, 对于重复元素比较多的情况, 如此切分是比较好的, 可以有效避免相等元素的比较, 将相等元素聚集起来, 就可以不必再切分这些元素了.

------------

原文地址 https://hujingnb.com/archives/168

转载请保留原文连接: 排序算法之快速排序 | 烟草的香味

guest
0 评论
内联反馈
查看所有评论
0
希望看到您的想法,请发表评论。x