精华内容
下载资源
问答
  • 快速排序

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

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

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

    千次阅读 多人点赞 2018-12-25 19:46:10
    冒泡排序过程中,只相邻的两记录进行比较,因此每次交换两相邻记录时只能消除一逆序。如果能通过两(不相邻)记录的一次交换,消除多逆序,则会大大加快排序的速度。快速排序方法的一次交换可以消除...

    快速排序(Quick Sort)概念:是由冒泡排序改进而得到的。在冒泡排序过程中,只对相邻的两个记录进行比较,因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的一次交换,消除多个逆序,则会大大加快排序的速度。快速排序方法中的一次交换可以消除多个逆序。

    快速排序的算法步骤:在待排序的n个记录中任取一个记录(通常取第一个记录)作为枢轴(或支点),设其关键字为pivotkey。经过一趟排序后,把所有关键字小于pivotkey的记录交换到前面,把所有关键字大于pivotkey的记录交换到后面,结果将待排序记录分成两个子表,最后将枢轴放置在分界处的位置。然后,分别对左右子表重复上述过程,直至每个子表只有一个记录时排序完成。

    例如对如下记录进行快速排序 :49,38,65,97,76,13,27,49*

    下面将会对上述记录进行快速排序,排序的过程如下所示:

    初始化:49(low/pivotkey),38,65,97,76,13,27,49*(high)

    第一趟排序以第一个数49作为枢轴进行快速排序

    排序的过程是交替振荡逼近的:就是pivotkey先和数组中最后一个数进行比较,不交换的话就和倒数第二个数进行比较直到交换,如果交换了,pivotkey就和数组第一个数进行比较,如果不交换的话pivotkey就和就和第二个数进行比较,直到交换,交换后pivotkey就要和之前后面所交换的前一个数进行比较,依次下去,这就是交替振荡逼近法。

    第一趟快速排序:{27,38,13},49,{76,97,65,49*}

    第二趟快速排序:{13},27,{38},49,{76,97,65,49*}

    第三趟快速排序:13,27,38,49,{49,65},76,{97}

    第四趟快速排序:13,27,38,49,49*,{65},76,97

    第四趟快速排序:13,27,38,49,49*,65,76,97

    下面我将用代码实现上述的过程:

    #include<stdio.h>
    #include<windows.h>
    void swap(int array[], int low, int high)//用于交换数组中两个数值
    {
    	int temp;//中间变量用于交换两个数值
    	temp = array[low];
    	array[low] = array[high];
    	array[high] = temp;
    }
    int partition(int array[], int low, int high)
    {
    	int pivotkey = array[low];//设置数组第一个元素为比较元素
    	while (low < high)
    	{
    		while ((low<high) && (array[high] >= pivotkey))
    		{/*数组最后一个元素比pivotkey大,那么array[high]就应该放
    			在pivotkey的后面,所以high需要向前移动*/
    			high--;
    		}
    		//否则就交换array[low]和array[high]的数值
    		swap(array, low, high);
    		while ((low<high) && (array[low] <= pivotkey))
    		{
    			low++;
    		}
    		//否则就交换array[low]和array[high]的数值
    		swap(array, low, high);
    	}
    	return low;//最后返回枢轴的位置。
    
    }
    void Qsort(int array[], int low, int high)
    {
    	if (low<high)//如果符合判断条件的话就递归
    	{
    		int key = partition(array, low, high);//用key去接收第一躺排序之后枢轴的位置】、
    		
    		Qsort(array, low, key - 1);//左边子序列
    
    		Qsort(array, key + 1, high);//右边子序列
    	}
    }
    void Quicksort(int array[], int len)//快排开始
    {
    	Qsort(array, 0, len - 1);//调用递归函数
    }
    
    void Print(int array[], int len)//用于打印整个数组
    {
    	for ( int i = 0;i<len; i++)
    	{
    		printf("%3d",array[i]);
    	}
    }
    
    void main()
    {
    	int array[] = { 13, 27, 38, 49, 49, 65, 76, 97};
    	Quicksort(array,8);//调用快速排序的函数对上面的数组进行快速排序
    	printf("快速排序的结果为:\n");
    	Print(array, 8);
    	printf("\n");
    	system("pause");//暂停一下
    
    }
    

    代码运行截图如下所示:

    在这里插入图片描述

    展开全文
  • 快速排序过程图解)

    万次阅读 多人点赞 2018-07-02 12:10:50
    假设我们现在“612 79345 108”这10进行排序。首先序列随便找一数作为基准数(不要被这名词吓到了,就是一用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一数6作为基准数吧...
    假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列。
           3  1  2 5  4  6  9 7  10  8
     
            在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6。想一想,你有办法可以做到这点吗?
     
            给你一个提示吧。请回忆一下冒泡排序,是如何通过“交换”,一步步让每个数归位的。此时你也可以通过“交换”的方法来达到目的。具体是如何一步步交换呢?怎样交换才既方便又节省时间呢?先别急着往下看,拿出笔来,在纸上画画看。我高中时第一次学习冒泡排序算法的时候,就觉得冒泡排序很浪费时间,每次都只能对相邻的两个数进行比较,这显然太不合理了。于是我就想了一个办法,后来才知道原来这就是“快速排序”,请允许我小小的自恋一下(^o^)。
     
           方法其实很简单:分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即j=10),指向数字8。

     
           首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。哨兵j一步一步地向左挪动(即j--),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。

     

     
     
     

           现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下。

            6  1  2  5  9 3  4  7  10  8

     
     
     
            到此,第一次交换结束。接下来开始哨兵j继续向左挪动(再友情提醒,每次必须是哨兵j先出发)。他发现了4(比基准数6要小,满足要求)之后停了下来。哨兵i也继续向右挪动的,他发现了9(比基准数6要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下。
            6  1  2 5  4  3  9  7 10  8
     
            第二次交换结束,“探测”继续。哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。
            3  1 2  5  4  6  9 7  10  8
     
     

     
     
            到此第一轮“探测”真正结束。此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。回顾一下刚才的过程,其实哨兵j的使命就是要找小于基准数的数,而哨兵i的使命就是要找大于基准数的数,直到i和j碰头为止。
     
            OK,解释完毕。现在基准数6已经归位,它正好处在序列的第6位。此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“3  1 2  5  4”,右边的序列是“9  7  10  8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。
     
            左边的序列是“3  1  2 5  4”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。好了开始动笔吧。
     
            如果你模拟的没有错,调整完毕之后的序列的顺序应该是。
            2  1  3  5  4
     
            OK,现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整,处理完毕之后的序列为“1 2”,到此2已经归位。序列“1”只有一个数,也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕,得到序列是“1 2”。序列“5 4”的处理也仿照此方法,最后得到的序列如下。
            1  2  3 4  5  6 9  7  10  8
     
            对于序列“9  7  10  8”也模拟刚才的过程,直到不可拆分出新的子序列为止。最终将会得到这样的序列,如下。
            1  2  3 4  5  6  7  8 9  10
     
            到此,排序完全结束。细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

     
     
            快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。
    #include <stdio.h>
    int a[101],n;//定义全局变量,这两个变量需要在子函数中使用
    void quicksort(int left, int right) {
    	int i, j, t, temp;
    	if(left > right)
    		return;
        temp = a[left]; //temp中存的就是基准数
        i = left;
        j = right;
        while(i != j) { //顺序很重要,要先从右边开始找
        	while(a[j] >= temp && i < j)
        		j--;
        	while(a[i] <= temp && i < j)//再找右边的
        		i++;       
        	if(i < j)//交换两个数在数组中的位置
        	{
        		t = a[i];
        		a[i] = a[j];
        		a[j] = t;
        	}
        }
        //最终将基准数归位
        a[left] = a[i];
        a[i] = temp;
        quicksort(left, i-1);//继续处理左边的,这里是一个递归的过程
        quicksort(i+1, right);//继续处理右边的 ,这里是一个递归的过程
    }
    int main() {
    	int i;
        //读入数据
    	scanf("%d", &n);
    	for(i = 1; i <= n; i++)
    		scanf("%d", &a[i]);
        quicksort(1, n); //快速排序调用
        //输出排序后的结果
        for(i = 1; i < n; i++)
        	printf("%d ", a[i]);
        printf("%d\n", a[n]);
        return 0;
    }

     

     
    展开全文
  • 原理是从第一个元素开始,比较相邻元素的大小,若大小顺序有误,则对调后再进行下一个元素的比较。如此经过第一次扫描后就可以确保最后一个元素位于正确的顺序;经过第二次扫描可以确保倒数第二个元素位于正确的顺序...

    排序算法1: 冒泡排序法(python示例)

    冒泡排序法又称为交换排序法,是从观察水中气泡变化构思而成。原理是从第一个元素开始,比较相邻元素的大小,若大小顺序有误,则对调后再进行下一个元素的比较。如此经过第一次扫描后就可以确保最后一个元素位于正确的顺序;经过第二次扫描可以确保倒数第二个元素位于正确的顺序。由此可知,N个元素经过(N-1)次扫描,就可以完成所有元素的排序。

    下面使用55、23、87、62、16数列来演示排序过程,这样大家可以清楚地知道冒泡排序法的具体流程。从小到大排序,原始顺序如图:
    在这里插入图片描述

    1. 第一次扫描,会先拿第一个元素55和第二个元素23进行比较,如果第二个元素小于第一个元素,则进行互换。接着拿55和87进行比较,就这样往右方向一直比较并交换。第一次比较完后,即可确定最大值在数组的最后面。下图是第一次扫描互换的一次过程,颜色填充为蓝色的数字是在此次扫描过程中向右交换前进的数字。
      在这里插入图片描述
      第一次扫描排序后的结果为:23、55、62、16、87。
    2. 第二次扫描,也是从头比较,但因为最后一个元素在第一次扫描就已确定是数组中的最大值(下图填充为绿色的数字),故只需比较3次即可把剩余数组元素的最大值排到剩余数组的最后面,即倒数第二个位置。
      在这里插入图片描述
    3. 第三次扫描完,完成三个值的排序,如下图所示。
      在这里插入图片描述
    4. 第四次扫描完,即可完成所有的排序,如下图所示。
      在这里插入图片描述
      由此可知,5个元素的冒泡排序法必须执行4(5-1)次扫描,第一次扫描需比较4(5-1)次,共比较了4+3+2+1=10次。

    下面设计一个python程序,并使用冒泡排序法来对数列进行从小到大的排序。
    读入原始数列:

    data = [55, 23, 87, 62, 16]  #原始数据
    data_len = len(data)  #原始数据长度
    print('原始数据为:')
    for i in range(data_len):
        print('%d' %data[i], end=' ')
    

    使用冒泡排序法排序:

    for i in range(data_len-1, 0, -1):  #扫描次数,共4次,(4,3,2,1)
        for j in range(i):
            if data[j] > data[j+1]:  #比较,交换
                data[j], data[j+1] = data[j+1], data[j]  #比较相邻两数,如果第一数较大则交换
        print('第%d次排序后的结果是:'%(data_len-i), end=' ')  #把各次扫描后的结果打印出来
        for j in range(data_len):
            print('%d' %data[j], end=' ')
        print()
    

    排序过程为:
    在这里插入图片描述
    排序后的结果为:

    print('排序后的结果为:')
    for j in range(data_len):
        print('%d' %data[j], end=' ')
    

    在这里插入图片描述

    排序算法2: 选择排序法(python示例)

    选择排序法(Selecting Sort)也算是枚举法的应用,就是反复从未排序的数列中取出最小的元素,加入到另一个数列中,最后的结果即为已排序的数列。从小到大排序的操作是一开始在所有的数据中挑选一个最小项放在第一个位置,再从第二项开始挑选剩下元素的最小项放在第2个位置,以此反复,直到完成排序为止。由此可知,N个元素经过(N-1)次扫描,就可以完成所有元素的排序。

    下面使用55、23、87、62、16数列从小到大的排序过程来说明选择排序法的演算流程。原始数据如图:
    在这里插入图片描述

    1. 首先找到此数列中最小值后,与数列中的第一个元素交换,如下图所示。
      在这里插入图片描述
    2. 从第二个值开始找,找到剩余数列中(不含第一个填充为绿色的数字)的最小值,再和第二个值交换,如下图所示。本次扫描,第二个数字恰巧是剩余数字中的最小值,因此位置不变。
      在这里插入图片描述
    3. 从第三个值开始找,找到此数列中(不含第一、二个的最小值),再和第三个值交换,如下图。
      在这里插入图片描述
    4. 从第四个值开始找,找到剩余数列的最小值,再和第四个值交换,排序完成,如下图。
      在这里插入图片描述
      由此可知,5个元素的选择排序法必须执行4(5-1)次扫描。

    下面设计一个python程序,并使用选择排序法对数列进行从小到大的排序
    读入原始数列:

    data = [55, 23, 87, 62, 16]  #原始数据
    data_len = len(data)  #原始数据长度
    print('原始数据为:')
    for i in range(data_len):
        print('%d' %data[i], end=' ')
    

    使用选择排序法排序:

    def select(data):
        for i in range(data_len-1):
            for j in range(i+1, data_len):
                if data[i] > data[j]:  #比较第i和第j个元素
                    data[i], data[j] = data[j], data[i]
    

    排序后的结果为:

    select(data)
    print('排序后的结果为:')
    for j in range(data_len):
        print('%d' %data[j], end=' ')
    

    在这里插入图片描述

    排序算法3: 插入排序法(python示例)

    插入排序法(Insert Sort)是将数组中的元素,逐一与已排序好的数据进行比较,前两个元素先排好,再将第三个元素插入适当的位置,所以这三个元素仍然是已排好序的,接着将第四个元素加入,重复此步骤,直到排序完成为止。可以看作是在一串有序的记录R1、R2…Ri中,插入新的记录R,使得i+1个记录排序妥当。

    下面我们仍然使用55、23、87、62、16数列从小到大的排序过程来说明插入排序法的演算流程。如下图所示,在步骤一种,以23为基准与55比较后,放到55的前面。步骤二则拿87与其他两个元素(23、55)比较。步骤三62在比较完前三个数后插入到87的前面……,步骤四将最后一个元素比较完成后即完成排序。由此可知,N个元素经过(N-1)个步骤,即可完成所有元素的排序。
    在这里插入图片描述
    下面设计一个python程序,并使用插入排序法进行从小到大的排序。
    读入原始数据:

    data = [55, 23, 87, 62, 16]  #原始数据
    data_len = len(data)  #原始数据长度
    print('原始数据为:')
    for i in range(data_len):
        print('%d' %data[i], end=' ')
    

    使用插入排序法排序:

    def insert(data):
        for i in range(1, data_len):
            tmp = data[i]  #tmp用来暂存数据
            NO = i - 1
            while NO >= 0 and tmp < data[NO]:
                data[NO+1] = data[NO]  #就把所有比tmp大的元素往后推一个位置,此步骤是由后往前比较后并插入
                NO -= 1
            data[NO+1] = tmp  #插入的位置
    

    排序后的结果为:

    insert(data)
    print('排序后的结果为:')
    for j in range(data_len):
        print('%d' %data[j], end=' ')
    

    在这里插入图片描述

    排序算法4: 希尔排序法(python示例)

    当原始记录的键值大部分已排好序的情况下,插入排序法会非常有效率,因为它不需要执行太多的数据搬移操作。“希尔排序法”是D.L.Shell在1959年7月所发明的一种排序法,可以减少插入排序法中数据搬移的次数,以加速排序的进行。排序的原则是将数据区分成特定间隔的几个小区块,以插入排序法排完区块内的数据后,再逐渐减少间隔的距离。

    下面我们用63、92、27、36、45、71、58、7数列从小到大的排序过程来说明希尔排序法的演算流程。原始数据如下图所示。
    在这里插入图片描述

    1. 第一次排序过程,将所有数据分成Y:(8 div 2)份,即Y=4,Y成为划分数。注意,划分数不一定是2,质数最好。为了算法方便,所以我们习惯选2。因而一开始的间隔设置为4,如下图所示,同颜色的数字为一个区块。
      在这里插入图片描述
      如此一来可得到4个区块,分别是(63,45)(92, 71)(27, 58)(36,7),再分别用插入排序法排序成为(45,63)(71,92)(27,58)(7,36),在整个队列中数据的排序如下图所示。
      在这里插入图片描述
    2. 第二次排序,将间隔缩小为(8/2)/2(即间隔为2),如下图所示,同颜色的数字为一个区块。
      在这里插入图片描述
      (45,27,63,58)(71,7,92,36)再分别用插入排序法,得到如下图所示的结果。
      在这里插入图片描述
    3. 第三次排序,再以((8/2)/2)/2的间距进行插入排序,也就是每一个元素进行排序,于是得到最后的结果,如下图所示。
      在这里插入图片描述
      下面设计一个python程序,并使用希尔排序法来对数列进行从小到大的排序。
      读入原始数列:
    data = [63,92,27,36,45,71,58,7]  #原始数据
    data_len = len(data)  #原始数据长度
    def showdata(data):
        for i in range(data_len):
            print('%d' %data[i], end=' ')
    print('原始数组是: ')
    showdata(data)
    

    使用希尔排序法排序:

    def shell(data):
        k = 1  # 第k次排序过程
        size = len(data)
        jmp = size // 2  #向下取整,例如1//2等于0;jmp为设置间距的位移量
        while jmp != 0:
            for i in range(jmp, size):  #i为扫描次数
                tmp = data[i]  #tmp用来暂存数据
                j = i - jmp  #以j来定位比较的元素
                while tmp < data[j] and j >= 0:  #插入排序法
                    data[j+jmp] = data[j]
                    j = j-jmp
                data[jmp+j] = tmp
            print('第%d次排序过程:'%k, end=' ')
            k += 1
            showdata(data)
            print()
            print('--------------------------------------')
            jmp = jmp//2  #控制循环次数
    shell(data)
    

    排序过程和结果为:
    在这里插入图片描述

    排序算法5: 合并排序法(python示例)

    合并排序法(Merge Sort)的工作原理是针对已排序好的两个或两个以上的数列(或数据文件),通过合并的方式,将其组合成一个大的且已排好序的数列(或数据文件)。

    下面我们使用38、16、41、72、52、98、63、25数列从小到大的排序过程来说明合并排序法的基本演算流程,如下图所示。
    在这里插入图片描述
    上面展示的合并排序法例子是一种最简单的合并排序,又称为2路(2-way)合并排序。
    步骤如下:

    1. 将N个长度为1的数列合并成N/2个已排序妥当且长度为2的数列。
    2. 将N/2个长度为2的数列合并成N/4个长度为4的数列。
    3. 将数列不断地合并,直到合并成一组长度为N的数列为止。

    下面设计一个python程序,并使用合并排序法来排序。
    读入数据:

    data = [38,16,41,72,52,98,63,25]  #原始数据
    

    合并两个有序数列:

    def merge(a, b):
        c = []
        h = j = 0
        while j < len(a) and h < len(b):
            if a[j] < b[h]:
                c.append(a[j])
                j += 1
            else:
                c.append(b[h])
                h += 1
    
        if j == len(a):
            for i in b[h:]:
                c.append(i)
        else:
            for i in a[j:]:
                c.append(i)
    
        return c
    

    合并排序:

    #递归法
    def merge_sort(lists):
        if len(lists) <= 1:
            return lists
        #二分列表
        middle = len(lists)//2
        left = merge_sort(lists[:middle])
        right = merge_sort(lists[middle:])
        return merge(left, right)
    

    输出最终结果:

    print (merge_sort(data))
    

    最终结果是 [16, 25, 38, 41, 52, 63, 72, 98]。

    排序算法6: 快速排序法(python示例)

    快速排序(Quick Sort)是由C.A.Hoare所提出来的。快速排序法又称分割交换排序法,是目前公认最佳的排序法,也是使用“分而治之”(Divide and Conquer)的方式,先在数据中找到一个虚拟的中间值,并按此中间值将所有打算排序的数据分为两部分。其中,小于中间值的数据放在左边,大于中间值的数据放在右边,再以同样的方式分别处理左、右两边的数据,直到排序完为止。
    快速排序的步骤:
    (1) 选择基准值。
    (2) 将数组分成两个子数组:小于基准值的元素和大于基准值的元素。
    (3) 对这两个子数组进行快速排序。
    算法简单描述:选择数组第一位元素位基准值,创建两个新数组,分别存放小于基准值和大于基准值的元素。然后这两个新数组递归进行上述操作,直到数组为空。然后将左右数组和基准值进行拼接。

    下面设计一个python程序,并使用快速排序法来排序。
    快速排序代码:

    def quicksort(array):
      if len(array) < 2:
        # 基线条件:为空或只包含一个元素的数组是“有序”的
        return array
      else:
        pivot = array[0]
        # 由所有小于基准值的元素组成的子数组
        less = [i for i in array[1:] if i <= pivot]
        # 由所有大于基准值的元素组成的子数组
        greater = [i for i in array[1:] if i > pivot]
    
        return quicksort(less) + [pivot] + quicksort(greater)
    

    输出排序结果:

    data = [35,10,42,3,79,12,62,18,51,23]  #原始数据
    quicksort(data)
    

    输出结果为 [3, 10, 12, 18, 23, 35, 42, 51, 62, 79]。

    快速排序法图解过程可参考:
    https://blog.csdn.net/qq_40941722/article/details/94396010

    展开全文
  • 数组有 N 个元素,使用快速排序对进行排序输出(本题还会人工阅卷,请使用快速排序算法进行排序) 输入描述: 输入为两行。 第一行一整数n(1 ≤ n ≤ 100000),表示一共有n个元素 第二行为n个数,即每个元素,每...
  • 今天就来谈谈快速排序,我们也不详谈快速排序的时间复杂度,我们重点来分析一下快速排序的思想。  快速排序的思想十分简单,假设给定一无序的数组,我们要从小到大排列,我们只需要完成以下几步  1、选取这...
  • JS排序算法:冒泡法、快速排序法、选择排序法、插入排序法、哈希排序//生成数组 var arr = new Array(1000); for (var i = 0; i ; i++) { arr[i] = (Math.round(Math.random() * 1000)); }1.冒泡法 排序思想:...
  • 关于快速排序的认识及其基本特征,请参寻我的另外一篇博文快速排序——以数组第一个元素为主元 以具体的例子
  • 所以我这里会尽可能地简单地把冒泡排序法拆解成一的小步骤。希望各位能尽可能地理解。 当然实在理解不了也没问题。本来排序法就不是考试的重点,只有一比较小的概率会出成程序大题。但是如果理解了的话,...
  • 针对相同元素值的快速排序

    千次阅读 2017-08-14 17:05:07
    如果数组元素值都相同,随机化的快速排序的运行时间将为O(n2)O(n^2)。 因此,可以考虑PARTITION过程进行优化。使新的PARTITION排列数组A[p..r]的元素,返回值是两数组的下标q和t,其中p≤q≤t≤rp \le q \...
  • 今天刷蓝桥杯题时,遇到了快速排序的算法,题目很简单,就是简单的不超过10数字的快排,我很快的写完了一提交,正确率为90%。错误原因为超时。于是我想总共就10数字,怎么会超时呢,会不会时陷入了死循环。...
  • 快速排序 过程图解

    万次阅读 多人点赞 2016-05-28 19:39:04
     原作者:啊哈磊  这是我见过的解释快速排序最好的文章,分享如下: ... 假如我们的计算机每秒钟可以运行10亿次,那么1亿进行排序,桶排序则只需要0.1秒,而冒泡排序则需要1千万秒,达到115天之
  • 快速排序过程图解 参考啊哈算法)

    万次阅读 多人点赞 2019-01-07 16:40:08
    假设我们现在“6 1 2 7 9 3 4 5 10 8”这10进行排序。首先序列随便找一数作为基准数(不要被这名词吓到了,就是一用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一数6作为...
  • 我们有这么一需求,老板和我们说,要求我们做这么一员工系统,公司员工的相关信息和为公司的贡献值都会系统进行记录,每到月底评功轮赏的时候,根据员工这一月的表现进行奖罚。你可能会说,这还不好做吗...
  • 图示为使用快速排序对一列数字排序的过程。事实上,快速排序通常明显比其他O(nlog2n)算法更快。因为它的内部循环(inner loop)可以大部分的架构上很有效率地被实现出来。复杂度和具体元素交换步骤如下 右图的交换...
  • 当划分产生的两子问题分别包含了n−1n-1n−1个元素和000个元素时,快速排序的最坏情况发生了。不妨假设算法的每一次递归调用中都出现了这种不平衡划分。划分操作的时间复杂度是Θ(n)\Theta(n)Θ(n)。由于...
  • 快速排序冒泡排序的一种改进,其基本思想是基于分治法的:待排序表L[1...n]任取一个元素p作为基准 通过一趟排序将待排序的表L划分为两部分L[1...k-1]和L[k+1...n],使得L[1...k-1]的所有元素小于p,L[k+1...
  • 快速排序的思想是数组[p,r]选择一分区点q,将数组一分为2,同时将小于分区点的数值的放到分区点左侧[p,q-1],大于分区点的数值的放到分区点右侧[q+1,r],重复这个过程快速排序也是用到了分治思想和递归实现...
  • 快速排序法:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分的所有数据要小,然后再按此方法这两部分数据分别进行快速排序(此过程可以用到函数递归的方法)。 #include #...
  • 排序算法整合(冒泡,快速,希尔,拓扑,归并)

    万次阅读 多人点赞 2019-08-20 14:09:50
    它会遍历若干次要排序的数列,每次遍历时,它都会从前往后依次的比较相邻两数的大小;如果前者比后者大,则交换它们的位置。这样,一次遍历之后,最大的元素数列的末尾! 采用相同的方法再次遍历时,第二大的...
  • 一、 快速排序基准位置的选取方法 1.固定位置法(就是选取的基准是固定的、一般是数组的第一个元素) 2.随机选取基准法 /** * 快速排序,递归实现 * 时间复杂度:好:O(无序)(nlog2n),坏(有序):O(n^2) * ...
  • 什么是快速排序呢? 说的简单点儿就是:你现在要一串数据进行排序...第二轮就可以分两边了 然后依次类推 个过程中就需要用到递归 我们还可以知道 要左右两边分别递归 最后就出来。这是我对快速排序最简单...
  • 快速排序总结是看到之前上数据结构的时候给老师写的一关于考试程序纠错的邮件。错误的程序如下: void QuickSort(RecType R[],int s,int t) { int i=s,j=t; RecType tmp; if (s) { tmp=R[s]; ...
  • 快排第n排序结果校验

    千次阅读 2016-11-13 16:17:25
    快排第n趟排序结果校验@(算法学习)(2014.11)下列选项,不可能是快速排序第二趟排序结果的是:A. 2,3,5,4,6,7,9 B. 2,7,5,6,4,3,9 C. 3,2,5,4,7,6,9 D. 4,2,3,5,7,6,9分析:只需要掌握一点就可以解出这问题:...
  • 分治法之快速排序算法解题思路

    千次阅读 2018-06-10 14:24:04
    先找一基准元素(比如待排序数组的第一个元素),进行一趟快速排序,使得该基准元素左边的所有数据都它小,而右边的所有数据都它大,然后再按此方法,左右两边的数据分别进行快速排序,整个排序过程可以递归进行...
  • 什么是快速排序快速排序简介快速排序(英文名:Quicksort,有时候也叫做划分交换排序)是一高效的排序算法,由Tony Hoare1959年发明(1961年公布)。当情况良好时,它可以比主要竞争对手的归并排序和堆排序快上...
  • 快速排序的基本思想1.2 时间复杂度的计算1.21 最坏情况时间复杂度计算1.22 最好情况时间复杂度1.23 平均时间复杂度计算2 总结 1. 快速排序的基本思想 用首元素 x 作划分标准,将输入数 组 A划分成不超过 x 的元素...
  • 快速排序复杂度的相关分析以及使用插入排序优化的快速排序
  • 算法系列(三)排序算法上篇 一文,介绍了冒泡排序,插入排序和选择排序算法。这篇文章继续讲解排序算法。 概述 冒泡排序,插入排序和选择排序算法这些算法的时间复杂度都是O(N^2),是否有更高效的排序算法呢?...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 100,153
精华内容 40,061
关键字:

在对n个元素进行快速排序的过程中