精华内容
下载资源
问答
  • 使用递归的方法实现快速排序,简洁明了,避免了烦琐的考虑循环。
  • 这个代码是利用快速排序算法,求第K大的数。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后...
  • 快速排序

    万次阅读 多人点赞 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不同版本下的对元素内部排序的实现。

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

    展开全文
  • 本文主要要谈的是利用javascript实现in-place思想的快速排序 分治法: 在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同...
  • 基本思想:  选择一个基准元素,比如选择最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分... 快速排序是不稳定的排序。  快速排序的时间复杂度为O(nlogn)。  当n较大时使用快排比...

    基本思想:

            选择一个基准元素,比如选择最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,又称为轴位置,此位置的元素确定后不再参与排序,然后再用同样的方法递归地排序划分的两部分。

    分析:

          快速排序是不稳定的排序。

      快速排序的时间复杂度为O(nlogn)。

      当n较大时使用快排比较好,当序列基本有序时用快排反而不好。

    代码实现:

    递归实现

        int[] quickSort(int arr[],int left,int right){
            if(Objects.isNull(arr)){
                return arr;
            }
            if(left<right){
                //获取排序轴索引,该索引本身不再参与排序
                int middle=findMiddlePartion(arr,left,right);
                //从左到中排序
                quickSort(arr,left,middle-1);
                //从中到右排序
                quickSort(arr,middle+1,right);
            }
            return arr;
        }
    
        //该算法实现 绝对优于多层while循环的那种实现
        int findMiddlePartion(int arr[],int left,int right){
            //以最右的数 为基准元素
            int baseMiddleNum=arr[right];
            //从最左位开始  记录替换索引
            int low=left-1;
            //遍历中不包含基准元素
            for(int i=left;i<right;i++){
                //比基准元素小的 从最左位开始放
                if(arr[i]<=baseMiddleNum){
                    //记录最左位已替换的索引
                    low++;
                    if(i==low){
                        continue;
                    }
                    //交换
                    int temp=arr[low];
                    arr[low]=arr[i];
                    arr[i]=temp;
                }
            }
            //基准元素放到轴位置
            if((low)+1!=right){
                int temp=arr[low+1];
                arr[low+1]=baseMiddleNum;
                arr[right]=temp;
            }
            //返回下一次遍历位置 以该位置为轴分别向两侧排序
            return low+1;
        }

    非递归实现:

        int[] quickSortNonRecursive(int arr[],int left,int right){
            if(Objects.isNull(arr)){
                return arr;
            }
            //通过栈实现
            Stack<Integer> stack=new Stack<>();
            stack.push(left);
            stack.push(right);
            while(!stack.isEmpty()){
                int rightNew=stack.peek();
                stack.pop();
                int leftNew=stack.peek();
                stack.pop();
                //获取排序轴索引,该索引本身不再参与排序
                int middle=findMiddlePartion(arr,leftNew,rightNew);
                if(middle-1>leftNew){
                    stack.push(left);
                    stack.push(middle-1);
                }
                if(middle+1<rightNew){
                    stack.push(middle+1);
                    stack.push(rightNew);
                }
            }
            return arr;
        }

     

    展开全文
  • 结合题目讲解“快速排序算法”

    万次阅读 2016-10-16 16:44:38
    根据一道快速排序算法自考题,进行学习方法上的反思,同时讲解自己对快速排序算法的理解

      理论很丰满,实战很骨感,作为一个嫌弃自己的胖子,我对实战很是热衷,导致总是对理论知识不上心,做题的时候就蒙了。

      比如有这样一道自考题:


      

      看完以后第一感觉就是翻书,因为觉得过了一遍书中知识点的情况下,做题的时候再仔细看看,然后推敲那些自己还没有掌握好的知识效果会更好,在这个过程中暴露了自己看书的一个很不好的习惯,就是知道把握全局,也知道要注重每个标题下边的初始知识介绍,但是总是莫名其妙地就一头扎进了书上的例题讲解中不能自拔,还傻傻地问自己为什么是这个样子,书上讲过吗?结果很是打脸,疑惑之处的解答基本上会在每个小标题下边那个“开门见山”的位置上,呵呵~~~在想以后是不是学习时候先看例题,再回去看书……

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


      这道题的答案如下

      

      我在做题的时候发现只会第一趟排序,第二趟不知从何下手了,其实就是看书的时候没留意上文阐述的基本思想,后来终于搞明白了。下面是自己根据这道题,以及解题过程中出现的小失误,总结的解题分析,相当于是对书中基本思想的扩写吧(以升序排列为例):

      1、很废话,若是要求升序排列,比较之后调换位置就把小的放在左边,降序排列同理;
      2、第一趟排序的时候默认以第一个数为基准;


      3、简言之,就是一来一去:挑选完基准数据后,要注意的是,不是跟和它挨着的那个数开始往后依次比较,而是将这个待排序序列末端的数据选做比较对象,从末端开始往回比较,遇到比它小的直接交换位置,比如上题中的默认首位基准数据265,首先和末位的438比较,可知438比它大,那么就和438前边的数据比较,发现076比它小,于是,265就和076交换位置,此时,265的位置发生了改变,比较方向就需要发生改变了,期初它的比较对象是从后往前,经过这次交换后,它的比较对象的选择顺序就要变成从前往后,此时和它比较的是301,比它大,二者交换位置,依照上述方法继续接下来的工作,得到了第一趟的排序结果。


      4、注意一趟排序是由多次比较交换位置得到的,即看清一趟和一次
      5、通过观察答案所展示的排序过程我们会发现,基准是用来作为子序列的划分界限的,很像是分块,划分后,它的左边都是比它小的,右边都是比它大的,第一趟排序的基准是第一个数,第二趟排序的基准有两个,分别是每个子序列(用[]括起来的部分)的第一个数,他们各自负责自己所在块的排序,排序方法同序号3所述。
      6、在得到最后的排序结果之前,我们会发现待排序序列都在[]里边,基准都在外边,就像图中标注的那样,上一趟待排序子序列中的第一个数据会成为下一趟排序的基准。


      PS:上图中第四趟只有一个数据742是在[]中的了,我在做题的时候以为到第四趟就截止了,毕竟它只剩下一个待排序数字独立成为一个序列了,后来发现竟然还有第五趟,其实这不难理解,第五趟只是起到了一个确定作用,达到去除第四趟结果那个[]的作用。


      站在个人角度而言,这篇博客,叙述的貌似是快速排序方法,其实算是对自己学习方法的一个反思吧:

      (1)不要把全局观忘了,要注意看书的侧重点;

      (2)切忌眼高手低,不要觉得自己曾经接触过相关知识就觉得自己掌握得很好,从而可以绕开理论知识了,有些实战之前,还是需要巩固下理论知识的。




    展开全文
  • 利用快速排序找到第k大的数字

    千次阅读 2017-09-16 22:11:05
    概念快速排序 - 维基百科中文 快速排序 - 维基百科中文具体思路及代码快排的思路就是把数字分成两边,小的放左边,大的放右边,相等的要么都放左边要么都放右边。 快排基本版 我这里是以最右边的元素为基准,从左...

    概念及本文参考

    快速排序 - 维基百科英文
    快速排序 - 维基百科中文

    具体思路及代码

    快排的思路就是把数字分成两边,小的放左边,大的放右边,相等的要么都放左边要么都放右边。

    找到第k大的元素就是:根据快排分区得到的主元下标比k大还是比k小,再对其中一边进行快排查找直到得到的主元下标等于k。

    • 快排基本版

    我这里是以最右边的元素为基准,从左往右找大于基准的数字和从右往左找小于或等于基准的数字并进行交换,直到左右两个的下标相遇(相等),就返回这个下标。需要O(n)的存储空间。

    int partition1(int *arr, int left, int right) {
        int pivot = arr[right];
        int low = left, high = right - 1;
        while (low < high) {
            while (low < high && arr[low] <= pivot)
                ++low;
            while (high > low && arr[high] > pivot)
                --high;
            if (low < high)
                swap(&arr[low], &arr[high]);
        }
        // 把主元放进一个合适的地方并返回主元下标
        if (arr[high] > pivot) {
            swap(&arr[high], &arr[right]);
            return high;
        }
        else {
            swap(&arr[high + 1], &arr[right]);
            return high + 1;
        }
    }
    • 快排优化版

      这个版本又叫原地(in-place)分区。暂时地把基准放在数字最后面,最后再交换回中间。空间复杂度O(logn)。

    // 以主元为中心划分:左边<=右边>;返回主元下标
    // 原地分区(in-place)算法
    int partition(int *arr, int left, int right) {
        int pivot = arr[right]; // 取最后一个元素为主元
        int large_num_index = left; 
    
        // 找到第一个一个大于pivot值的元素下标
        while (arr[large_num_index] <= pivot && large_num_index < right)
            ++large_num_index;
    
        // 与large_num_index后第一个小于pivot的值进行交换
        for (int i = large_num_index + 1; i < right; i++)
            if (arr[i] < pivot)
                swap(&arr[i], &arr[large_num_index++]);
    
        // 把主元元素交换到中间位置并作为一个分隔的标志
        swap(&arr[right], &arr[large_num_index]);
        return large_num_index;
    }
    

    测试代码

    • 对两种快排算法的测试
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    #define ARRAYSIZE 100    
    #define MAX_NUM 65536
    #define MIN_NUM -1
    #define TRUE 1
    #define FALSE 0
    
    void swap(int *a, int *b) {
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }
    // 打印出数组
    void print_array(int arr[], int num) {
        for (int i = 0; i < num; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
    
    // 递归快排
    void quicksort(int *arr, int left, int right) {
        if (left < right) {
            int pivot_index = partition(arr, left, right);
            quicksort(arr, left, pivot_index - 1);
            quicksort(arr, pivot_index + 1, right);
        }
    }
    
    void quicksort1(int *arr, int left, int right) {
        if (left < right) {
            int pivot_index = partition1(arr, left, right);
            quicksort1(arr, left, pivot_index - 1);
            quicksort1(arr, pivot_index + 1, right);
        }
    }
    
    // 复制数组
    void copy_array(int *copyarr, int *arr, int num) {
        for (int i = 0; i < num; i++)
            copyarr[i] = arr[i];
    }
    
    // 比较两个数组内容是否相同
    int comp_array(int *arr, int *copyarr, int num) {
        for (int i = 0; i < num; i++)
            if (copyarr[i] != arr[i])
                return FALSE;
        return TRUE;
    }
    
    void quicksort_test() {
        srand((unsigned)time(NULL));
        int arr[ARRAYSIZE] = {0};
        int copyarr[ARRAYSIZE] = {0};
        for (int i = 0; i < ARRAYSIZE; i++)
            arr[i] = rand();
        copy_array(copyarr, arr, ARRAYSIZE);
        print_array(arr, ARRAYSIZE);
    
        quicksort(arr, 0, ARRAYSIZE - 1);
        quicksort1(copyarr, 0, ARRAYSIZE - 1);
        cout << endl;
        print_array(arr, ARRAYSIZE);
        print_array(copyarr, ARRAYSIZE);
        if (comp_array(copyarr, arr, ARRAYSIZE))
            cout << "Correct" << endl;
        else
            cout << "Error" << endl;
    }
    
    int main() {
        quicksort_test();
    }

    测试结果可知这两种快排得出的结果一致。

    • 对查找第K大元素的测试
    
    int find_kth_element(int *arr, int left, int right, int k) {
        if (left <= right) {
            int pivot_index = partition(arr, left, right);
            if (pivot_index == k)
                return arr[pivot_index];
            else if (pivot_index < k)
                return find_kth_element(arr, pivot_index + 1, right, k);
            else
                return find_kth_element(arr, left, pivot_index - 1, k);
        }
        return -1;
    }
    
    int find_kth_element1(int *arr, int left, int right, int k) {
        if (left <= right) {
            int pivot_index = partition1(arr, left, right);
            if (pivot_index == k)
                return arr[pivot_index];
            else if (pivot_index < k)
                return find_kth_element1(arr, pivot_index + 1, right, k);
            else
                return find_kth_element1(arr, left, pivot_index - 1, k);
        }
        return -1;
    }
    
    // 升序
    int compare(const void *a, const void *b) {
        return (*(int *)a - *(int *)b);
    }
    
    void find_kth_element_test() {
        srand((unsigned)time(NULL));
        int arr[ARRAYSIZE] = {0};
        int copyarr[ARRAYSIZE] = {0};
        int examarr[ARRAYSIZE] = {0};
        for (int i = 0; i < ARRAYSIZE; i++)
            arr[i] = rand();
        copy_array(copyarr, arr, ARRAYSIZE);
        copy_array(examarr, arr, ARRAYSIZE);
        print_array(arr, ARRAYSIZE);
        int k = ARRAYSIZE / 2;
        cout << find_kth_element(arr, 0, ARRAYSIZE - 1, k) << endl;
        cout << find_kth_element1(copyarr, 0, ARRAYSIZE - 1, k) << endl;
        // 用stdlib自带的qsort进行验证
        qsort(examarr, ARRAYSIZE, sizeof(int), compare);
        cout << examarr[k] << endl;
    }
    
    int main() {
        find_kth_element_test();
    }

    测试结果是三种方法得出的数字都是一致的~

    记得去年也做过这道题,当时我还写了很久,嗯,现在用的时间也很久QAQ

    展开全文
  • 快速排序: 使用快速排序算法对数组进行排序 题目 一个数组有 N 个元素,使用快速排序对其进行排序输出(本题还会人工阅卷,请使用快速排序算法进行排序) 输入描述: 输入为两行。 第一行一个整数n(1 ≤ n ≤ 100000),...
  • 快速排序的非递归实现(利用栈)

    千次阅读 2019-06-12 10:54:41
    快速排序 递归算法使用的栈由程序自动产生,栈中包含:函数调用时的参数和函数中的局部变量。如果局部变量很多或者函数内部又调用了其他函数,则栈会很大。每次递归调用都要操作很大的栈,效率自然会下降。 非递归...
  • 主要介绍了java利用冒泡排序对数组进行排序方法,实例分析了冒泡排序的概念与java实现方法,以及java操作数组的相关技巧,需要的朋友可以参考下
  • 经过调研发现,对任意无序整数数组,快速排序有两种实现方法,这里简单阐述下思路: 思路一:随意选择一个基准元,一般选择数组的起始元或末尾元,Weiss这本书上特意搞了个算法来选择基准元,……,总之就是基准元...
  • 利用快速排序算法将读入的 N个数从小到大排序后输出,请勿使用std::sort。 输入格式 第一行一个整数 n (1≤n≤105)。 第二行 n 个整数 ai (1≤ai≤109)。 输出格式 输出一行,为 ai 排序后的结果。 解题思路 先从...
  • 利用list对对象进行快速排序

    千次阅读 2018-07-28 13:27:12
    java利用list对元素进行快速排序,并赋予排序等级 1.java的构造函数是在new一个对象时自动调用的函数,可以传参也可以不传参。 2.list集合不可以直接打印。 package package1; public class Student {  String ...
  • 快速排序的实现方法

    千次阅读 2018-05-31 14:53:44
    转自... 快速排序采用的思想是分治思想,先简单的介绍一下分治的思想。分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性...
  • 排序算法是比较常见的算法,道理也...结合快速排序,写了三个方法。 第一种: //不需要将基准值归位的快速排序 public static void quickSort(int []a,int left,int right) { if(left>=right) return ; int ...
  • 所谓的快速排序其实就是利用二分法加递归的原理,每次取出数组中的中间位置的值作为参照,然后再借助两个额外的数组。遍历原数组中的每个元素跟中间值(参照值)进行比较,把小于中间值的元素放在一个新数组中,相反...
  • C语言快速排序算法及三种优化方式

    千次阅读 多人点赞 2017-11-05 20:32:25
    C语言快速排序算法及三种优化方式 C语言快速排序算法及三种优化方式 原理 快速排序复杂度分析 1 时间复杂度 2 空间复杂度 快速排序代码实现 1 普通快速排序 2 快速排序优化1-三数取中优化不必要的交换 3 快速排序...
  • 分治法实现快速排序算法

    千次阅读 2019-07-29 11:16:25
    方法:分治法求解问题的思想是将问题中通过整体代入的思想将问题递归地分成小问题(即规模较小的原问题),并且每一次递归后都要进行合并操作,只有这样在递归结束后,分解的小问题的解就自动合并成最终的解...
  • 快速排序的几种实现方式

    千次阅读 2017-11-30 14:29:02
    之后分别对基准记录的左边和右边两个区间进行快速排序,直至将整个区间排序完成。 以下讨论不同的几种实现方式,都以从小到大排序为准。 基准值最左/最右+双指针 覆盖值(标准算法) 这种方法将基准...
  • 排序算法——归并排序与快速排序

    万次阅读 多人点赞 2018-07-27 20:50:08
    今天总结一下两种性能优秀的排序算法,归并排序与快速排序。 首先,二者都运用了递归和分治的两种重要思想。在这里递归就不做详细介绍。 分治:顾名思义,分而治之,这是在排序中我们非常常见的一种思想,同时也是...
  • 快速排序算法详细图解

    万次阅读 2020-08-21 17:37:08
    而目前来说,快速排序是相对比较好的一种算法:实现难度低,时间复杂度低。但快速排序在一些情况下也可能出现退化到和冒泡算法一样的时间复杂度,所以需要读者注意一下,下面我会讲到。那么接下来就来看看这个算法。...
  • 快速排序深度优化详解

    万次阅读 2019-02-24 17:25:36
    更多详情见原文:快速排序优化详解 正如它的名字所体现,快速排序是在实践中最快的已知排序算法,平均运行时间为O(NlogN),最坏的...快速排序利用了分治的策略。而分治的基本基本思想是:将原问题划分为若干与原问...
  • 分治算法之快速排序

    万次阅读 2017-10-06 21:38:31
    分治算法由两部分组成: 分:递归解决较小的问题(基本情况除外)。...分治算法的经典例子有归并排序和快速排序,它们分别有O(N logN)的最坏情形以及平均情形的时间界。 所有有效的分治算法都是把问题分成一些子
  • 快速排序详细图解分析(含代码示例)

    千次阅读 多人点赞 2019-06-04 14:07:44
    快速排序基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个...
  • 快速排排序是效率非常高的排序算法之一。  它的基本思想是:首先...然后再通过此方法堆这两部分数据分别进行快速排序,整个排序过程可以递归实现。但是具体的将待排序的数据分为两个部分的方法,却有很多:   举...
  • 常用的交换排序有冒泡排序和快速排序。 冒泡排序算法: 基本思想:n个元素,序列进行N-1次循环,依次比较相邻两个元素的大小,如果array[i]&gt;array[i+1],则交换两个元素,反之则不交换。这样每次循环都能...
  • 1、掌握快速排序随机算法的设计思想与方法。 2、熟练使用高级编程语言实现不同的快速排序算法。 3、利用实验测试给出不同快速排序算法的性能以理解其优缺点。 快速排序是算法导论中的经典算法。在本实验中,给定一...
  • 快速排序的基本思想关于快速排序,它的基本思想就是选取一个基准,一趟排序确定两个区间,一个区间全部比基准值小,另一个区间全部比基准值大,接着再选取一个基准值来进行排序,以此类推,最后得到一个有序的数列。...
  • 排序

    千次阅读 2009-07-29 09:08:00
    ),则利用快速 排序方法 ,以第一个 记录 为基准得到的一次划分结果为 A.38,40,46,56,79,84 B.40,38,46,79,56,84 C. 40,38,46,56,79,84 D. 40,38,46,84,56,79 6 .一组 记录 的 排序 码 为( 25...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 167,813
精华内容 67,125
关键字:

利用快速排序的方法