作为程序员理解算法是非常重要的, 最近又在看快速排序的实现细节, 做了一些总结.
快速排序是一种经典的递归和分而治之的思想
一, 从一组无序的数据分而治之, 从中任意选择一个数据作为基准数据 MARK, 数组中大于 MARK 的数据放到 MARK 的右边存入数组 max 中, 小于 MARK 的放到 MARK 的左边存入数组 min 中;
二, 对于 max 数组和 min 数组继续步骤一的操作, 直到数组中只有一个元素为止 (递归);
快速排序的时间复杂度为: n*logn
概念就是这么简单, 但是为什么会给我们一种很复杂的错觉呢, 就我个人而言觉得原因在于, 我们经常看到的是快速排序的实现代码 (java,c#,c,c++). 我这里不进行列举, 网上有大把的实例. 我在这里想说的是, 恰恰是这些实现的代码加大了理解快速排序的难度, 我们很多的时间用在了理解代码上, 而不是理解算法本身上. 所以, 在我看来, 算法和算法的实现代码不应该混在一起. 而且在我看来, 最能清晰的表达出快速排序的实现代码是. python, 如果你有编程经验, 即使不会 python, 也基本可以轻松理解下面的代码:
- def quicksort(array):
- if len(array) <2:
- return array
- else:
- pivot = array[0] // 基准数据 MARK
- less = [i for i in array[1:] if i <= pivot] // 小于 MARK 的数组
- greater = [i for i in array[1:] if i> pivot] // 大于 MARK 的数组
- return quicksort(less) + [pivot] + quicksort(greater) // 递归
- print quicksort([10, 5, 2, 3])
这段代码的重点在于递归的清晰表达上, 数组和数组直接用加号就可以进行合并, 貌似其它语言不行, 行云流水的就把意思表达的很清楚. 有兴趣的同学可以去找找其它语言的实现代码进行对比. 也可以看出为什么 python 目前相当火爆, 好的语言在表达上应该清晰. 这里我不是推广 python, 实际上我自己并不会 python.
作为一个 c# 和 java 的开发者, 我当然也想在自己熟悉的领域中找到很简单直观的代码来进行反驳, 但是很遗憾我还没有找到. 然后我从时间复杂度上做文章, 大家重点看分而治之这个词, 有了分而治之才有了快速排序的基础, 所以我给出了 c# 的快速排序的实现代码:
- static void Main(string[] args)
- {
- List<int> list = new List<int>() { 3, 2, 4, 1 ,1,4};
- List<int> result = new List<int>();
- int size = list.Count;
- for (int i = 0; i <size; i++)
- {
- int min = findMin(list);
- result.Add(min);
- list.Remove(min);
- }
- foreach (var item in result)
- {
- Console.WriteLine(item);
- }
- }
- public static int findMin(List<int> parm)
- {
- List<int> lessList = new List<int>();
- if (parm.Count> 1)
- {
- int index = parm[0];
- foreach (var item in parm)
- {
- if (item < index)
- {
- lessList.Add(item);
- }
- }
- if (lessList.Count == 0)
- {
- return index;
- }
- else
- {
- return findMin(lessList);
- }
- }
- else
- {
- return parm[0] ;
- }
- }
我的理解在于, 如何通过分而治之快速查找的依次找到最值. 实际上分而治之类似于二分查找. 从一组数据中通过分而治之找到最值使用的复杂度是 logn, 然后总的时间复杂度也是 n*logn. 在这个快速排序的实现代码中, 代码清晰, 算法思想明确, 即使看起来还是没有 python 简洁, 但是清晰表达的目的是达到了, 欢迎大家指教!
来源: https://www.cnblogs.com/pettyColorcat/p/9381949.html