【数据结构与算法】—— 快速排序
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。【来自百度百科】
快排介绍
老样子,前面有介绍
快排思路
快速排序,在学习的时候,老师就说,快排,是分而治之。就像中国 960 万疆土,分成省市县镇乡村去管辖。这就是分而治之。在各自的辖区内,各自管辖,互不干涉,最后再把结果汇总,就形成了我中华960万的疆土。那这个辖区怎么划分?这就需要一个标准,这个标准就是我们所说的基数。基数怎么确定?随便。是的,你没听错,随便。我可以选择第一个数,可以选择最后一个数,也可以选择中间的那个数。同样,这个基数我也可以是随机的。那么,现在的问题来了,就是我现在确定了一个基数,怎么去做到分而治之呢?这个时候,有个大神美其名曰:填坑法。很形象,很生动,很通俗易懂。那这个填坑法怎么去做?我们看图说话。
快排分析
代码实现
public static void main(String[] args) { int[] data = {15, 7, 10, 8, 16}; System.out.println("排序前:\n" + Arrays.toString(data)); quickSort(data, 0, data.length - 1); System.out.println("排序后:\n" + Arrays.toString(data)); } /** * 快速排序,在学习的时候,老师就说,快排,是分而治之。就像中国 960 万疆土,分成省市县镇乡村去管辖。这就是分而治之。在各自的辖区内, * 各自管辖,互不干涉,最后再把结果汇总,就形成了我中华960万的疆土。 * 那这个辖区怎么划分?这就需要一个标准,这个标准就是我们所说的基数。基数怎么确定?随便。是的,你没听错,随便。我可以选择第一个数, * 可以选择最后一个数,也可以选择中间的那个数。同样,这个基数我也可以是随机的。 * 那么,现在的问题来了,就是我现在确定了一个基数,怎么去做到分而治之呢?这个时候,有个大神美其名曰:填坑法。很形象,很生动,很通俗 * 易懂。那这个填坑法怎么去做?我们看图说话。 * * @param data */ private static void quickSort(int[] data, int left, int right) { if (left < right) { // 首先定下基数 int X = data[left]; int p = left, q = right; while (p < q) { // 从 左 -> 右 找 比 X 小的 while (p < q && data[q] >= X) { q--; } if (p < q) { data[p] = data[q]; p++; } while (p < q && data[p] < X) { p++; } if (p < q) { data[q] = data[p]; q--; } } data[p] = X; quickSort(data, left, p - 1); quickSort(data, p + 1, right); } }
// 这里要是用到 scala 就很简单了。可以利用 scala 里面的模式匹配 def main(args: Array[String]): Unit = { var list: List[Int] = List ( 1 , 2 , 5 , 8 , 10 , 25 , 9 , 6 ) println(quickSort(list)) } def quickSort(list: List[Int]): List[Int] = list match { case Nil => Nil case List() => List() case head :: tail => val (left, right) = tail.partition(_ < head) quickSort(left) ::: head :: quickSort(right) }
相关推荐
Masimaro 2020-06-21
Joymine 2020-06-06
清溪算法君老号 2020-06-01
GhostLWB 2020-04-20
田有朋 2020-04-19
sunjunior 2020-04-10
cmsmdn 2020-03-03
shenwenjie 2020-02-26
sunjunior 2020-02-15
路漫 2020-01-12
sunnyJam 2019-12-31
KilluaZoldyck 2019-12-15
yuanran0 2019-12-14
Happyunlimited 2019-12-10
baike 2019-12-09
yishujixiaoxiao 2019-12-02
YUAN 2019-11-19
alicelmx 2019-11-12