作为程序员理解算法是非常重要的，最近又在看快速排序的实现细节，做了一些总结。
快速排序是一种经典的递归和分而治之的思想
一、从一组无序的数据分而治之，从中任意选择一个数据作为基准数据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 arrayelse:pivot = array[0] //基准数据MARKless = [i for i in array[1:] if i <= pivot] //小于MARK的数组greater = [i for i in array[1:] if i > pivot] //大于MARK的数组<br><br>return quicksort(less) + [pivot] + quicksort(greater) //递归 |
| 12 | <em id="__mceDel">print quicksort([10, 5, 2, 3])</em> |
这段代码的重点在于递归的清晰表达上，数组和数组直接用加号就可以进行合并，貌似其它语言不行，行云流水的就把意思表达的很清楚。有兴趣的同学可以去找找其它语言的实现代码进行对比。也可以看出为什么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