手记

最简单清晰的理解《快速排序》

作为程序员理解算法是非常重要的,最近又在看快速排序的实现细节,做了一些总结。

快速排序是一种经典的递归和分而治之的思想

 

一、从一组无序的数据分而治之,从中任意选择一个数据作为基准数据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

0人推荐
随时随地看视频
慕课网APP