精华内容
参与话题
问答
  • 快速排序

    万次阅读 多人点赞 2017-03-18 18:11:48
    快速排序

    快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中,对数组,列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序在面试中经常会遇到。

    本文首先介绍快速排序的思路,算法的实现、分析、优化及改进,最后分析了.NET 中列表排序的内部实现。

    一 原理

    Sorting_quicksort_anim

    快速排序的基本思想如下:

    1. 对数组进行随机化。
    2. 从数列中取出一个数作为中轴数(pivot)。
    3. 将比这个数大的数放到它的右边,小于或等于它的数放到它的左边。
    4. 再对左右区间重复第三步,直到各区间只有一个数。

    Basic Step of Quick Sort

    如上图所示快速排序的一个重要步骤是对序列进行以中轴数进行划分,左边都小于这个中轴数,右边都大于该中轴数,然后对左右的子序列继续这一步骤直到子序列长度为1。

    下面来看某一次划分的步骤,如下图:

    Partition trace in Quick Sort

    上图中的划分操作可以分为以下5个步骤:

    1. 获取中轴元素
    2. i从左至右扫描,如果小于基准元素,则i自增,否则记下a[i]
    3. j从右至左扫描,如果大于基准元素,则i自减,否则记下a[j]
    4. 交换a[i]和a[j]
    5. 重复这一步骤直至i和j交错,然后和基准元素比较,然后交换。

    划分过程的代码实现如下:

    /// <summary>
    /// 快速排序中的划分过程
    /// </summary>
    /// <param name="array">待划分的数组</param>
    /// <param name="lo">最左侧位置</param>
    /// <param name="hi">最右侧位置</param>
    /// <returns>中间元素位置</returns>
    private static int Partition(T[] array, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        while (true)
        {
            //从左至右扫描,如果碰到比基准元素array[lo]小,则该元素已经位于正确的分区,i自增,继续比较i+1;
            //否则,退出循环,准备交换
            while (array[++i].CompareTo(array[lo]) < 0)
            {
                //如果扫描到了最右端,退出循环
                if (i == hi) break;
            }
    
            //从右自左扫描,如果碰到比基准元素array[lo]大,则该元素已经位于正确的分区,j自减,继续比较j-1
            //否则,退出循环,准备交换
            while (array[--j].CompareTo(array[lo]) > 0)
            {
                //如果扫描到了最左端,退出循环
                if (j == lo) break;
            }
    
            //如果相遇,退出循环
            if (i >= j) break;
    
            //交换左a[i],a[j]右两个元素,交换完后他们都位于正确的分区
            Swap(array, i, j);
        }
        //经过相遇后,最后一次a[i]和a[j]的交换
        //a[j]比a[lo]小,a[i]比a[lo]大,所以将基准元素与a[j]交换
        Swap(array, lo, j);
        //返回扫描相遇的位置点
        return j;
    }

    划分前后,元素在序列中的分布如下图:

    before and after partition

    二 实现

    与合并算法基于合并这一过程一样,快速排序基于分割(Partition)这一过程。只需要递归调用Partition这一操作,每一次以Partition返回的元素位置来划分为左右两个子序列,然后继续这一过程直到子序列长度为1,代码的实现如下:

    public class QuickSort<T> where T : IComparable<T>
    {
        public static void Sort(T[] array)
        {
            Sort(array, 0, array.Length - 1);
        }
    
        private static void Sort(T[] array, int lo, int hi)
        {
            //如果子序列为1,则直接返回
            if (lo >= hi) return;
            //划分,划分完成之后,分为左右序列,左边所有元素小于array[index],右边所有元素大于array[index]
            int index = Partition(array, lo, hi);
    
           //对左右子序列进行排序完成之后,整个序列就有序了
            //对左边序列进行递归排序
            Sort(array, lo, index - 1);
            //对右边序列进行递归排序
            Sort(array, index + 1, hi);
        }
    }

    下图说明了快速排序中,每一次划分之后的结果:

    the two part sorted

    一般快速排序的动画如下:

    quicksort

    三 分析

    1. 在最好的情况下,快速排序只需要大约nlgn次比较操作,在最坏的情况下需要大约1/2 n2 次比较操作。

      在最好的情况下,每次的划分都会恰好从中间将序列划分开来,那么只需要lgn次划分即可划分完成,是一个标准的分治算法Cn=2Cn/2+N,每一次划分都需要比较N次,大家可以回想下我们是如何证明合并排序的时间复杂度的。

      the compare complexity in  quick sort at the bese case

      在最坏的情况下,即序列已经排好序的情况下,每次划分都恰好把数组划分成了0,n两部分,那么需要n次划分,但是比较的次数则变成了n, n-1, n-2,….1, 所以整个比较次数约为n(n-1)/2~n2/2.

      the compare complexity in  quick sort at the worst case

    2. 快速排序平均需要大约2NlnN次比较,来对长度为n的排序关键字唯一的序列进行排序。 证明也比较简单:假设CN为快速排序平均花在比较上的时间,初始C0=C1=0,对于N>1的情况,有:

      image

      其中N+1是分割时的比较次数,image 表示将序列分割为0,和N-1左右两部分的概率为1/N, 划分为1,N-2左右两部分的概率也为1/N,都是等概率的。

      然后对上式左右两边同时乘以N,整理得到:

      image

      然后,对于N为N-1的情况:

      image

      两式相减,然后整理得到:

      image

      然后左右两边同时除以N(N+1),得到:

      image

      可以看到,这是一个递归式,我们将image 递归展开得到:

      image

      然后处理一下得到:

      image

    3. 平均情况下,快速排序需要大约1.39NlgN次比较,这比合并排序多了39%的比较,但是由于涉及了较少的数据交换和移动操作,他要比合并排序更快。
    4. 为了避免出现最坏的情况,导致序列划分不均,我们可以首先对序列进行随机化排列然后再进行排序就可以避免这一情况的出现。
    5. 快速排序是一种就地(in-place)排序算法。在分割操作中只需要常数个额外的空间。在递归中,也只需要对数个额外空间。
    6. 另外,快速排序是非稳定性排序。

    Quick Sort is not Stable

    四 改进

    对一般快速排序进行一些改进可以提高其效率。

    1. 当划分到较小的子序列时,通常可以使用插入排序替代快速排序

    对于较小的子序列(通常序列元素个数为10个左右),我们就可以采用插入排序直接进行排序而不用继续递归,算法改造如下:

    private const int CUTTOFF = 10;
    private static void Sort(T[] array, int lo, int hi)
    {
        //如果子序列为1,则直接返回
        if (lo >= hi) return;
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1) 
        {
            Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        //划分,划分完成之后,分为左右序列,左边所有元素小于array[index],右边所有元素大于array[index]
        int index = Partition(array, lo, hi);
    
        //对左右子序列进行排序完成之后,整个序列就有序了
    
        //对左边序列进行递归排序
        Sort(array, lo, index - 1);
        //对右边序列进行递归排序
        Sort(array, index + 1, hi);
    }

    2. 三平均分区法(Median of three partitioning)

    在一般的的快速排序中,选择的是第一个元素作为中轴(pivot),这会出现某些分区严重不均的极端情况,比如划分为了1和n-1两个序列,从而导致出现最坏的情况。三平均分区法与一般的快速排序方法不同,它并不是选择待排数组的第一个数作为中轴,而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说,主要有两点优势:

    (1) 首先,它使得最坏情况发生的几率减小了。

    (2) 其次,未改进的快速排序算法为了防止比较时数组越界,在最后要设置一个哨点。如果在分区排序时,中间的这个元素(也即中轴)是与最右边数过来第二个元素进行交换的话,那么就可以省略与这一哨点值的比较。

    对于三平均分区法还可以进一步扩展,在选取中轴值时,可以从由左中右三个中选取扩大到五个元素中或者更多元素中选取,一般的,会有(2t+1)平均分区法(median-of-(2t+1)。常用的一个改进是,当序列元素小于某个阈值N时,采用三平均分区,当大于时采用5平均分区。

    采用三平均分区法对快速排序的改进如下:

    private static void Sort(T[] array, int lo, int hi)
    {
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1) 
        {
            //Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        //采用三平均分区法查找中轴
        int m = MedianOf3(array, lo, lo + (hi - lo) / 2, hi);
        Swap(array, lo, m);
        //划分,划分完成之后,分为左右序列,左边所有元素小于array[index],右边所有元素大于array[index]
        int index = Partition(array, lo, hi);
    
        //对左右子序列进行排序完成之后,整个序列就有序了
    
        //对左边序列进行递归排序
        Sort(array, lo, index - 1);
        //对右边序列进行递归排序
        Sort(array, index + 1, hi);
    }
    
    /// <summary>
    /// 查找三个元素中位于中间的那个元素
    /// </summary>
    /// <param name="array"></param>
    /// <param name="lo"></param>
    /// <param name="center"></param>
    /// <param name="hi"></param>
    /// <returns></returns>
    private static int MedianOf3(T[] array, int lo, int center, int hi)
    {
        return (Less(array[lo], array[center]) ?
               (Less(array[center], array[hi]) ? center : Less(array[lo], array[hi]) ? hi : lo) :
               (Less(array[hi], array[center]) ? center : Less(array[hi], array[lo]) ? hi : lo));
    }
    
    private static bool Less(T t1, T t2)
    {
        return t1.CompareTo(t2) < 0;
    }

    使用插入排序对小序列进行排序以及使用三平均分区法对一般快速排序进行改进后运行结果示意图如下:

    Improvement using Insertsort and 3 mediation partition

    3. 三分区(3-way partitioning) 快速排序

    通常,我们的待排序的序列关键字中会有很多重复的值,比如我们想对所有的学生按照年龄进行排序,按照性别进行排序等,这样每一类别中会有很多的重复的值。理论上,这些重复的值只需要处理一次就行了。但是一般的快速排序会递归进行划分,因为一般的快速排序只是将序列划分为了两部分,小于或者大于等于这两部分。

    既然要利用连续、相等的元素不需要再参与排序这个事实,一个直接的想法就是通过划分让相等的元素连续地摆放:

     3-way partition quick sort

    然后只对左侧小于V的序列和右侧大于V对的序列进行排序。这种三路划分与计算机科学中无处不在,它与Dijkstra提出的“荷兰国旗问题”(The Dutch National Flag Problem)非常相似。

    Dijkstra的方法如上图:

    从左至右扫描数组,维护一个指针lt使得[lo…lt-1]中的元素都比v小,一个指针gt使得所有[gt+1….hi]的元素都大于v,以及一个指针i,使得所有[lt…i-1]的元素都和v相等。元素[i…gt]之间是还没有处理到的元素,i从lo开始,从左至右开始扫描:

    · 如果a[i]<v: 交换a[lt]和a[i],lt和i自增

    · 如果a[i]>v:交换a[i]和a[gt], gt自减

    · 如果a[i]=v: i自增

    下面是使用Dijkstra的三分区快速排序代码:

    private static void Sort(T[] array, int lo, int hi)
    {
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1)
        {
            Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        //三分区
        int lt = lo, i = lo + 1, gt = hi;
        T v = array[lo];
        while (i<=gt)
        {
            int cmp = array[i].CompareTo(v);
            if (cmp < 0) Swap(array, lt++, i++);
            else if (cmp > 0) Swap(array, i, gt--);
            else i++;
        }
    
        //对左边序列进行递归排序
        Sort(array, lo, lt - 1);
        //对右边序列进行递归排序
        Sort(array, gt + 1, hi);
    }

    三分区快速排序的每一步如下图所示:

    3-way partitioning trace

    三分区快速排序的示意图如下:

    3 way quick sort visual trace

    Dijkstra的三分区快速排序虽然在快速排序发现不久后就提出来了,但是对于序列中重复值不多的情况下,它比传统的2分区快速排序需要更多的交换次数。

    Bentley 和D. McIlroy在普通的三分区快速排序的基础上,对一般的快速排序进行了改进。在划分过程中,i遇到的与v相等的元素交换到最左边,j遇到的与v相等的元素交换到最右边,i与j相遇后再把数组两端与v相等的元素交换到中间

    Bentley  McIlroy 3 way partition 

    这个方法不能完全满足只扫描一次的要求,但它有两个好处:首先,如果数据中没有重复的值,那么该方法几乎没有额外的开销;其次,如果有重复值,那么这些重复的值不会参与下一趟排序,减少了无用的划分。

    下面是采用 Bentley&D. McIlroy 三分区快速排序的算法改进:

    private static void Sort(T[] array, int lo, int hi)
    {
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1)
        {
            Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        // Bentley-McIlroy 3-way partitioning
        int i = lo, j = hi + 1;
        int p = lo, q = hi + 1;
        T v = array[lo];
        while (true)
        {
            while (Less(array[++i], v))
                if (i == hi) break;
            while (Less(v, array[--j]))
                if (j == lo) break;
    
            // pointers cross
            if (i == j && Equal(array[i], v))
                Swap(array, ++p, i);
            if (i >= j) break;
    
            Swap(array, i, j);
            if (Equal(array[i], v)) Swap(array, ++p, i);
            if (Equal(array[j], v)) Swap(array, --q, j);
        }
    
        //将相等的元素交换到中间
        i = j + 1;
        for (int k = lo; k <= p; k++) Swap(array, k, j--);
        for (int k = hi; k >= q; k--) Swap(array, k, i++);
    
        Sort(array, lo, j);
        Sort(array, i, hi);
    }

    三分区快速排序的动画如下:

    3wayquick sort

    4.并行化

    和前面讨论对合并排序的改进一样,对所有使用分治法解决问题的算法其实都可以进行并行化,快速排序的并行化改进我在之前的浅谈并发与并行这篇文章中已经有过介绍,这里不再赘述。

    五 .NET 中元素排序的内部实现

    快速排序作为一种优秀的排序算法,在很多编程语言的元素内部排序中均有实现,比如Java中对基本数据类型(primitive type)的排序,C++,Matlab,Python,FireFox Javascript等语言中均将快速排序作为其内部元素排序的算法。同样.NET中亦是如此。

    .NET这种对List<T>数组元素进行排序是通过调用Sort方法实现的,其内部则又是通过Array.Sort实现,MSDN上说在.NET 4.0及之前的版本,Array.Sort采用的是快速排序,然而在.NET 4.5中,则对这一算法进行了改进,采用了名为Introspective sort 的算法,即保证在一般情况下达到最快排序速度,又能保证能够在出现最差情况是进行优化。他其实是一种混合算法:

    • 当待分区的元素个数小于16个时,采用插入排序
    • 当分区次数超过2*logN,N是输入数组的区间大小,则使用堆排序(Heapsort)
    • 否则,使用快速排序。

    有了Reflector这一神器,我们可以查看.NET中的ArraySort的具体实现:

    Array.Sort这一方法在mscorlib这一程序集中,具体的实现方法有分别针对泛型和普通类型的SortedGenericArray和SortedObjectArray,里面的实现大同小异,我们以SortedGenericArray这个类来作为例子看:

    ArraySort implementation in .NET_1

    首先要看的是Sort方法,其实现如下:

    ArraySort implementation in .NET_2

    该方法中,首先判断运行的.NET对的版本,如果是4.5及以上版本,则用IntrospectiveSort算法,否则采用限定深度的快速排序算法DepthLimitedQuickSort。先看IntrospectiveSort:

    ArraySort implementation in .NET_3

    该方法第一个元素为数组的最左边元素位置,第二个参数为最右边元素位置,第三个参数为2*log2N,继续看方法内部:

    ArraySort implementation in .NET_4

    可以看到,当num<=16时,如果元素个数为1,2,3,则直接调用SwapIfGreaterWithItem进行排序了。否则直接调用InsertSort进行插入排序。

    这里面也是一个循环,每循环一下depthLimit就减小1个,如果为0表示划分的次数超过了2logN,则直接调用基排序(HeapSort),这里面的划分方法PickPivortAndPartitin的实现如下:

    ArraySort implementation in .NET_5

    它其实是一个标准的三平均快速排序。可以看到在.NET 4.5中对Quick进行优化的部分主要是在元素个数比较少的时候采用选择插入,并且在递归深度超过2logN的时候,采用基排序。

    下面再来看下在.NET 4.0及以下平台下排序DepthLimitedQuickSort方法的实现:

    从名称中可以看出这是限定深度的快速排序,在第三个参数传进去的是0x20,也就是32。

    DepthLimitedQuickSort

    可以看到,当划分的次数大于固定的32次的时候,采用了基排序,其他的部分是普通的快速排序。

    六 总结

    由于快速排序在排序算法中具有排序速度快,而且是就地排序等优点,使得在许多编程语言的内部元素排序实现中采用的就是快速排序,本问首先介绍了一般的快速排序,分析了快速排序的时间复杂度,然后就分析了对快速排序的几点改进,包括对小序列采用插入排序替代,三平均划分,三分区划分等改进方法。最后介绍了.NET不同版本下的对元素内部排序的实现。

    快速排序很重要,希望本文对您了解快速排序有所帮助。

    展开全文
  • 【排序】快速排序

    千次阅读 热门讨论 2016-10-27 06:24:22
    快速排序

    前言

            之前总结了交换排序的一种——冒泡排序,今天来说另外一种——快速排序。

    快速排序

            何为快速排序,它实质上是对冒泡排序的一种改进,基本思想:在n个记录中取某一个记录的键值为标准,通常取第一个键值为基准,通过一趟排序将待排序的记录分为小于或等于这个键值和大于这个键值的两个独立的部分,这时一部分的记录键值均比另一部分记录的键值小,然后,对这两部分记录继续分别进行快速排序,以达到整个序列有序。

    效果图


    代码

    类C描述

    void QuickSort(List R,int low,int high)//总快速排序
    {
            if(low<high)
            {
                    temp=QuickPartition(R,low,high);
                    QuickSort(R,low,temp-1);//分治思想
                    QuickSort(R,temp+1,high);
            }
    }
    int QuickPartition(List R,int low,int high)//每次循环代码
    {
            x=R[low];
            while(low<high)
            {
                    while((low<high)&&(R[high].key>=x.key))
                            high--;
                    R[low]=R[high];
                    while((low<high)&&(R[low].key<=x.key))
                            low++;
                    R[high]=R[low];
            }
            R[low]=x;
            return low;
    }
    C#描述

    static void Main(string[] args)//主程序
    {
            int[] R = { 3, 7, 8, 5, 2, 1, 9, 5, 4 };
            int low = 0;
            int high = R.Length - 1;
            QuickSort(R, low, high);
            Console.WriteLine("排序后数组:");
            for (int i = 0; i <= R.Length - 1; i++)
            {
                    Console.Write(R[i] + ",");
            }
            Console.WriteLine();
            Console.ReadKey();
    }
    private static void QuickSort(int[] R,int low,int high)//总快速排序
    {
            int temp;
            if(low<high)
            {
                    temp = QuickPartition(R, low, high);
                    QuickSort(R, low, temp - 1);
                    QuickSort(R, temp + 1, high);
            }
    }
    private static int QuickPartition(int[] R, int low, int high)//单次快速排序方法
    {
            int x = R[low];
            while(low<high)
            {
                    while(low <high && R[high]>=x)
                    { high--; }
                    R[low] = R[high];
                    while(low<high && R[low]<=x)
                    {low++;}
                    R[high] = R[low];
            }
            R[low] = x;
            return low;
    }

            注:快速排序有两种,分别是递归快速排序和非递归快速排序,本篇博客只写了递归快速排序,通过对两种类型的代码比较,更能体现快速排序的分治思想。

            就平均时间性能而言,快速排序方法最佳,但在最坏情况下,即对几乎已是排好序的输入序列,时间复杂度高达O(n^2),另外,对于较小的n值该算法效果不明显,对于较大的n值效果较好。

    总结

    各种排序对比图


    另附:快速排序舞蹈视频

    展开全文
  • 白话经典算法系列之六 快速排序 快速搞定

    万次阅读 多人点赞 2011-08-13 17:19:58
    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的...
     快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小的程序方面的考试如软考,考研中也常常出现快速排序的身影。

    总的说来,要直接默写出快速排序还是有一定难度的,因为本人就自己的理解对快速排序作了下白话解释,希望对大家理解有帮助,达到快速排序,快速搞定

     

    快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。

    该方法的基本思想是:

    1.先从数列中取出一个数作为基准数。

    2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。

    3.再对左右区间重复第二步,直到各区间只有一个数。

     

    虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤。因此我的对快速排序作了进一步的说明:挖坑填数+分治法

    先来看实例吧,定义下面再给出(最好能用自己的话来总结定义,这样对实现代码会有帮助)。

     

    以一个数组作为示例,取区间第一个数为基准数。

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    72

    6

    57

    88

    60

    42

    83

    73

    48

    85

    初始时,i = 0;  j = 9;   X = a[i] = 72

    由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。

    从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

     

    数组变为:

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    48

    6

    57

    88

    60

    42

    83

    73

    88

    85

     i = 3;   j = 7;   X=72

    再重复上面的步骤,先从后向前找,再从前向后找

    从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++;

    从i开始向后找,当i=5时,由于i==j退出。

    此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。

     

    数组变为:

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    48

    6

    57

    42

    60

    72

    83

    73

    88

    85

    可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

     

     

    对挖坑填数进行总结

    1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。

    2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

    3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

    4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。

    照着这个总结很容易实现挖坑填数的代码:

    int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
    {
    	int i = l, j = r;
    	int x = s[l]; //s[l]即s[i]就是第一个坑
    	while (i < j)
    	{
    		// 从右向左找小于x的数来填s[i]
    		while(i < j && s[j] >= x) 
    			j--;  
    		if(i < j) 
    		{
    			s[i] = s[j]; //将s[j]填到s[i]中,s[j]就形成了一个新的坑
    			i++;
    		}
    
    		// 从左向右找大于或等于x的数来填s[j]
    		while(i < j && s[i] < x)
    			i++;  
    		if(i < j) 
    		{
    			s[j] = s[i]; //将s[i]填到s[j]中,s[i]就形成了一个新的坑
    			j--;
    		}
    	}
    	//退出时,i等于j。将x填到这个坑中。
    	s[i] = x;
    
    	return i;
    }
    

    再写分治法的代码:

    void quick_sort1(int s[], int l, int r)
    {
    	if (l < r)
        {
    		int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
    		quick_sort1(s, l, i - 1); // 递归调用 
    		quick_sort1(s, i + 1, r);
    	}
    }

    这样的代码显然不够简洁,对其组合整理下:

    //快速排序
    void quick_sort(int s[], int l, int r)
    {
        if (l < r)
        {
    		//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
    				j--;  
                if(i < j) 
    				s[i++] = s[j];
    			
                while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
    				i++;  
                if(i < j) 
    				s[j--] = s[i];
            }
            s[i] = x;
            quick_sort(s, l, i - 1); // 递归调用 
            quick_sort(s, i + 1, r);
        }
    }

    快速排序还有很多改进版本,如随机选择基准数,区间内数据较少时直接用另的方法排序以减小递归深度。有兴趣的筒子可以再深入的研究下。

     

    注1,有的书上是以中间的数作为基准数的,要实现这个方便非常方便,直接将中间的数和第一个数进行交换就可以了。

     

     转载请标明出处,原文地址:http://blog.csdn.net/morewindows/article/details/6684558

    展开全文
  • C语言 快速排序函数

    千次阅读 2017-09-12 18:34:11
    C语言 快速排序函数用法 #include #include #include struct student { int id; char name[12]; char sex; }; int compare(const void* a,const void* b)//基本数据类型排序 { return *(char*)a-*(char*)b;/...

    C语言 快速排序函数用法

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct student
    {
      int id;
      char name[12];
      char sex;
    };
    int compare(const void* a,const void* b)//基本数据类型排序
    {
      return *(char*)a-*(char*)b;//从小到大
        //取值//强转为相应类型的指针!!
    }
    int compare_struct(const void* a,const void* b)
    {
      return (*(struct student*)a).id-((struct student*)b)->id;
             //注意优先级诶!//否则报错在非结构体中。。。
    }
    int compare_struct_duoji(const void* a,const void* b)//多级排序
    {
      struct student student_a=*(struct student*)a;
      struct student student_b=*(struct student*)b;
     
      if(student_a.id==student_b.id)
      {
        return student_a.sex-student_b.sex;
      }
      else
      {
        return student_a.id-student_b.id;
      }
    }
    void main()
    {
    //*************char型*************
      char a[5]="hello";
      qsort(a,5,sizeof(a[0]),compare);
          //元素个数//元素大小//函数指针
      int i;
      for(i=0;i<5;i++)
          printf("%c ",a[i]);
      printf("\n");
     
    //************struct型************
      struct student e[4]={{100,"chen",'m'},{100,"li",'f'}, \
                 {70,"wang",'f'},{100,"zhang",'m'}};
      qsort(e,4,sizeof(e[1]),compare_struct_duoji);
     
      for(i=0;i<4;i++)
          printf("%d %s %c\n",e[i].id,e[i].name,e[i].sex);
    }


    展开全文
  • C语言快速排序

    千次阅读 2018-12-25 19:46:10
    快速排序(Quick Sort)概念:是由冒泡排序改进而得到的。在冒泡排序过程中,只对相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的一次交换,消除多个逆序,则...
  • 排序之快速排序

    千次阅读 2017-02-26 16:10:43
    快速排序
  • JS排序算法:冒泡法、快速排序法、选择排序法、插入排序法、哈希排序//生成数组 var arr = new Array(1000); for (var i = 0; i ; i++) { arr[i] = (Math.round(Math.random() * 1000)); }1.冒泡法 排序思想:...
  • 快速排序(过程图解)

    万次阅读 多人点赞 2018-07-02 12:10:50
    假设我们现在对“612 79345 108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧...
  • 快速排序C语言

    千次阅读 2018-06-03 16:44:16
    快速排序利用了分治法思想,将带排序数组分解成多个部分进行排序,每个部分排序实际是进行一次数组的重新划分,选定一个元素将其作为中间元素,使元素两侧只有大于或是小于他的元素。用递归树可证得快速排序的时间...
  • 本文(所有排序算法代码+综合比较代码)链接: 一、比较目的:        由于《数据结构》课本中各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。所以我希望通过...
  • 快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n ...
  • 快速排序算法

    万次阅读 2020-03-13 21:08:20
    快排的作用: ...=j),于是就分成了(i到k-1)和(k+1到j)两端没有排序好 例题 有如下数组 27 99 0 8 13 64 86 16 7 10 88 25 90 i ...
  • 快速排序---(面试碰到过好几次)

    万次阅读 多人点赞 2018-09-10 12:20:21
       快速排序,说白了就是给基准数据找其正确索引位置的过程.    如下图所示,假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组,设两个指示...
  • 快速排序基本思路(通俗易懂+例子)

    万次阅读 多人点赞 2017-07-02 22:06:32
    快速排序今天看到大神写的一篇快速排序的博客,肃然起敬,觉得原来快速排序这么简单 下面进行简单的试试快速排序的基本思想是 1、先从数列中取出一个数作为基准数 2、分区过程,将比这个数大的数全放到它的...
  • 排序算法系列:快速排序算法

    万次阅读 多人点赞 2016-03-01 15:40:07
     本文就来说说交换排序的最后一拍:快速排序算法。之所以说它是快速的原因,不是因为它比其他的排序算法都要快。而是从实践中证明了快速排序在平均性能上的确是比其他算法要快一些,不然快速一说岂不是在乱说?  ...
  • 上个厕所的功夫,就学会了“快速排序”算法

    万次阅读 多人点赞 2020-05-17 20:25:09
    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司的笔试面试,包括像BAT、TMD等知名IT公司都喜欢考查快速排序原理和手写...
  • 冒泡排序、快速排序、选择排序、插入排序、归并排序
  • 算法 - 快速排序(C#)

    万次阅读 多人点赞 2019-01-29 20:29:11
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!... /* * 快速排序(QuickSort)是对冒泡排序的一种... * 然后再按此方法对这两部分数据分别进行快速排序,整个排序...
  • 在算法系列(三)排序算法上篇 ...当然有了,堆排序,归并排序,快速排序,它们的时间复杂度都是O(nlogn)。堆排序使用了树结构,到目我们前还没有介绍树相关的算法,这里先分析归并排序跟快速排序。 归并排序 基本原理
  • using Microsoft.AspNetCore.Builder; using Microsoft.Extensions.DependencyInjection; using Microsoft.Extensions.Hosting; using Microsoft.OpenApi.Models; using Volo.Abp; using Volo.Abp.AspNetCore.Mvc;...
  • c++快速排序代码

    千次阅读 2019-01-18 14:26:22
    c++ 快速排序代码(方便下次直接用) #include &lt;iostream&gt; using namespace std; int Partitions(int a[], int low, int high) { if (low &gt;=high) //先检查左右条件 return -1; int i = ...

空空如也

1 2 3 4 5 ... 20
收藏数 771,658
精华内容 308,663
关键字:

快速