精华内容
下载资源
问答
  • Unity快速入门系列课程(第1部)

    千人学习 2019-05-08 15:49:57
    为满足入门学员的学习要求,“刘国柱讲Unity”系列课程,因此推出了本套“Unity快速入门系列课程”,目前内容包含如下:     1: 项目“我的世界”: 讲解Unity软件的重要组成窗口与基本使用。  ...
  • 快速排序

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

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

    展开全文
  • Android Studio实战 快速、高效地构建Android应用

    千次下载 热门讨论 2016-09-06 11:01:24
    《Android Studio实战 快速、高效地构建Android应用 全面涵盖关于Android Studio及其庞大工具生态系统的内容,包括Git和Gradle:除了介绍Android Studio与Git(用于源代码管理)和Gradle(一款构建及测试工具)的无缝...
  • 2.3快速原型模型的思想产生、原理及运用方式 2.4类型 2.5开发步骤 三、增量模型 3.1什么是增量模型 3.2特点 3.3优缺点 3.4作用 四、螺旋模型 4.1什么是螺旋模型 4.2特点 4.3优缺点 4.4...

    目录

    一、瀑布模型

    1.1什么是瀑布模型

    1.2特点

    1.3优缺点

    1.4客户需求

    二、快速原型模型

    2.1什么是快速原型模型

    2.2优缺点

    2.3快速原型模型的思想产生、原理及运用方式

    2.4类型

    2.5开发步骤

    三、增量模型

    3.1什么是增量模型

    3.2特点

    3.3优缺点

    3.4作用

    四、螺旋模型

    4.1什么是螺旋模型

    4.2特点

    4.3优缺点

    4.4限制条件


    一、瀑布模型

    1.1什么是瀑布模型

    1970年温斯顿.罗伊斯提出了著名的“瀑布模型”,直到80年代早期,它一直是唯一被广泛采用的软件开发模型

    瀑布模型将软件生命周期划分为制定计划、需求分析、软件设计、程序编写、软件测试运行维护等六个基本活动,并且规定了它们自上而下、相互衔接的固定次序,如同瀑布流水,逐级下落

    瀑布模型是最早出现的软件开发模型,在软件工程中占有重要的地位,它提供了软件开发的基本框架。其过程是从上一项活动接收该项活动的工作对象作为输入,利用这一输入实施该项活动应完成的内容给出该项活动的工作成果,并作为输出传给下一项活动

    从本质来讲,它是一个软件开发架构,开发过程是通过一系列阶段顺序展开的,从系统需求分析开始直到产品发布和维护,每个阶段都会产生循环反馈,因此,如果有信息未被覆盖或者发现了问题,那么最好 “返回”上一个阶段并进行适当的修改,开发进程从一个阶段“流动”到下一个阶段,这也是瀑布开发名称的由来

    对于经常变化的项目而言,瀑布模型毫无价值

    1.2特点

    1、阶段间具有顺序性和依赖性

    该阶段具有两重含义

    1. 必须等前一阶段的工作完成后,才能开始后一阶段的工作
    2. 前一阶段的输出文档就是后一阶段的输入文档,因此只有前一阶段的输出文档正确,后一阶段的工作才能获得正确的结果

    2、推迟实现的观点

    对于规模较大的软件项目来说,往往编码开始的越早,最终完成开发所需时间越长。因为前面阶段的工作没做或做的不扎实,过早地考虑进行程序实现,往往导致大量返工,有时甚至发生无法弥补的问题

    瀑布模型在编码之前设置了系统分析与系统设计的各个阶段,分析与设计阶段的基本任务规定,在这两个阶段主要考虑目标系统的逻辑模型,不涉及软件的物理实现

    清楚的区分逻辑设计与物理设计,尽可能推迟程序的物理实现,是按照瀑布模型开发软件的一条重要的指导思想

    3、质量保证的观点

    为了保证所开发的软件的质量,在瀑布模型的每一个阶段都应坚持两个重要做法

    1. 每个阶段都必须完成规定的文档,没有交出合格的文档就是没有完成该阶段的任务
    2. 每个阶段结束前都要对所完成的文档进行评审,以便尽早发现问题,改正错误

    传统的瀑布模型过于理想化,实际的瀑布模型是带"反馈环"的。如图所示(图中实线箭头表示开发过程,虚线箭头表示维护过程),当在后面阶段发现前面阶段的错误时,需要沿图中左侧的反馈线返回前面的阶段,修正前面阶段的产品后再回来继续完成后面阶段的任务

    瀑布模型是文档驱动的模型,遵守这个约束可使软件维护变得比较容易一些,从而显著降低软件预算

    1.3优缺点

    优点:

    • 项目提供了按阶段划分的检查点
    • 当前一阶段完成后,您只需要去关注后续阶段
    • 可在迭代模型中应用瀑布模型

    缺点:

    • 不适合需求模糊或需求经常变动的系统
    • 由于开销的逐步升级问题,它不希望存在早期阶段的反馈
    • 在一个系统完成以前,它无法预测一个新系统引入一个机构的影响
    • 用户可能需要较长等待时间来获得一个可供使用的系统,也许会给用户的信任程度带来影响和打击
    • 最终产品往往反映用户的初始需求而不是最终需求

    1.4客户需求

    对项目而言,是否使用这一模型主要取决于是否能理解客户的需求以及在项目的进程中这些需求的变化程度;对于经常变化的项目而言,瀑布模型毫无价值,可以考虑其他的架构来进行项目管理,比如螺旋模型

    瀑布模型强调文档的作用,并要求每个阶段都要仔细验证。但是,这种模型的线性过程太理想化,已不再适合现代的软件开发模式,几乎被业界抛弃,其主要问题在于:

    1. 各个阶段的划分完全固定,阶段之间产生大量的文档,极大地增加了工作量
    2. 由于开发模型是线性的,用户只有等到整个过程的末期才能见到开发成果,从而增加了开发的风险
    3. 早期的错误可能要等到开发后期的测试阶段才能发现,进而带来严重的后果

    按照瀑布模型的阶段划分,软件测试可以分为单元测试集成测试系统测试

     

    二、快速原型模型

    2.1什么是快速原型模型

    快速原型是快速建立起来的可以在计算机上运行的程序,它所能完成的功能往往是最终产品能完成的功能的一个子集

    快速原型模型是增量模型的另一种形式,在开发真实系统之前,迅速建造一个可以运行的软件原型 ,以便理解和澄清问题,在该原型的基础上,逐渐完成整个系统的开发工作

    它允许在需求分析阶段对软件的需求进行初步而非完全的分析和定义,快速设计开发出软件系统的原型,该原型向用户展示待开发软件的全部或部分功能和性能;用户对该原型进行测试评定,给出具体改进意见以丰富细化软件需求;开发人员据此对软件进行修改完善,直至用户满意认可之后,进行软件的完整实现及测试、维护

    2.2优缺点

    优点

    • 克服瀑布模型的缺点,减少由于软件需求不明确带来的开发风险
    • 适合预先不能确切定义需求的软件系统的开发

    缺点

    • 所选用的开发技术和工具不一定符合主流的发展;快速建立起来的系统结构加上连续的修改可能会导致产品质量低下
    • 使用前提是要有一个展示性的产品原型,一定程度上可能会限制开发人员的创新

    2.3快速原型模型的思想产生、原理及运用方式

    1、思想产生

    在需求分析阶段得到完全、一致、准确、合理的需求说明十分困难

    获得一组基本需求说明后,就快速地使其“实现”,通过原型反馈,加深对系统的理解满足用户基本要求,使用户在试用后对需求说明进行补充和精确化,从而获得合理完整、现实可行的需求说明

    再把快速原型思想用到软件开发的其他阶段,向软件开发的全过程扩展

    先用相对少的成本,较短的周期开发一个简单的、但可以运行的系统原型向用户演示或让用户试用,以便及早澄清并检验一些主要设计策略,在此基础上再开发实际的软件系统

    2、原理

    利用原型辅助软件开发

    经过简单快速分析快速实现一个原型,用户与开发者在试用原型过程中加强通信与反馈,通过反复评价和改进原型,减少误解,弥补漏洞,最终提高软件质量

    3、运用方式

    由于运用原型的目的和方式不同,在使用原型时也采取不同的策略

    • 抛弃策略:将原型用于开发过程的某个阶段,促使该阶段的开发结果更加完整、准确、一致、可靠,该阶段结束后,原型随之作废。探索型和实验型就是采用此策略的
    • 附加策略:将原型用于开发的全过程,原型由最基本的核心开始,逐步增加新的功能和新的需求,反复修改反复扩充,最后发展为用户满意的最终系统,演化型快速原型就是采用此策略

    采用何种形式、何种策略运用快速原型主要取决于软件项目的特点、可供支持的原型开发工具和技术等,根据实际情况的特点决定

    2.4类型

    在软件开发中,原型是软件的一个早期可运行的版本,它反映最终系统的部分重要特性

    探索型

    这种原型目的是要弄清对目标系统的要求,确定所希望的特性,并探讨多种方案的可行性

    实验型

    这种原型用于大规模开发和实现之前,考核方案是否合适,规格说明是否可靠

    进化型

    这种原型的目的不在于改进规格说明,而是将系统建造得易于变化,在改进原型的过程中,逐步将原型进化成最终系统

    2.5开发步骤

    1、快速分析

    在分析人员与用户密切配合下,迅速确定系统的基本需求,根据原型需要体现的特征描述基本需求以满足开发原型的需要

    2、构造原型

    在快速分析的基础上,根据基本需求说明尽快实现一个可行的系统

    要求具有强有力的软件工具的支持,并忽略最终系统在某些细节上的要求,主要考虑原型系统能够充分反映所要评价的特性

    3、运行原型

    发现问题,消除误解,开发者与用户充分协调

    4、评价原型

    在运行的基础上,考核评价原型的特性,分析运行效果是否满足用户的愿望,纠正过去交互中的误解与分析中的错误,增添新的要求,并满足因环境变化或用户的新想法引起的系统要求变动,提出全面的修改意见

    5、修改

    根据评价原型的活动结果进行修改

    若原型未满足需求说明的要求,说明对需求说明存在不一致的理解或实现方案不够合理,根据明确的要求迅速修改原型

    快速原型模型不带反馈环,软件产品的开发基本上是线性顺序进行的

    快速原型的本质是"快速"。开发人员应尽可能地建造出原型系统,以加速软件开发过程,节约软件开发成本

    原型的用途是获知用户的真正需求,一旦需求确定了,原型将被抛弃

     

    三、增量模型

    3.1什么是增量模型

    增量模型也称渐增模型。使用增量模型开发软件时,把软件产品作为一系列的增量构件来设计、编码、集成和测试。每个构件由多个相互作用的模块构成,并且能够完成特定的功能

    使用增量模型时,第一个增量构件往往实现软件的基本需求,提供最核心的功能

    把软件产品分解成增量构件时,唯一必须遵守的约束条件是,当把新构件集成到现有构件中时,所形成的产品必须是可测试的

    瀑布模型或快速原型模型目标是一次就把一个满足所有需求的产品提交给用户

    增量模型把整个软件产品分解成许多个增量构件,分批地逐步向用户提交产品

    3.2特点

    把瀑布模型的顺序特征与快速原型法的迭代特征相结合

    将软件看作一系列相互联系的增量,在开发过程的各次迭代中,每次完成其中的一个增量

    风险更大的增量模型

    确定用户需求后就着手拟定第一个构件的规格说明文档,完成后规格说明组转向第二个构件的规格说明文档,同时设计组开始涉及第一个构件

    使用该方法将不同的构件并行构建,可能加快工程进度,但将冒构建无法集成到一起的风险

    3.3优缺点

    优点

    1. 能在较短的时间内向用户提交可完成部分工作的产品
    2. 将待开发的软件系统模块化,可以分批次地提交软件产品,使用户可以及时了解软件项目的进展
    3. 以组件为单位进行开发降低了软件开发的风险。一个开发周期内的错误不会影响到整个软件系统
    4. 开发顺序灵活。开发人员可以对组件的实现顺序进行优先级排序,先完成需求稳定的核心组件。当组件的优先级发生变化时,还能及时地对实现顺序进行调整

    缺点

    1. 由于各个构件是逐渐并入已有的软件体系结构中的,所以加入构件必须不破坏已构造好的系统部分,这需要软件具备开放式的体系结构
    2. 在开发过程中,需求的变化是不可避免的。增量模型的灵活性可以使其适应这种变化的能力大大优于瀑布模型和快速原型模型,但也很容易退化为边做边改模型,从而是软件过程的控制失去整体性
    3. 如果增量包之间存在相交的情况且未很好处理,则必须做全盘系统分析,这种模型将功能细化后分别开发的方法较适应于需求经常改变的软件开发过程

    3.4作用

    1、开发初期的需求定义只是用来确定软件的基本结构,使得开发初期用户只需要对软件需求进行大概的描述;而对于需求的细节性描述,则可以延迟到增量构件开发时进行,以增量构件为单位逐个地进行需求补充。这种方式能够有效适应用户需求的变更

    2、软件系统可以按照增量构件的功能安排开发的优先顺序,并逐个实现和交付使用。不仅有利于用户尽早用上系统,能够更好地适应新的软件环境,而且在以增量方式使用系统的过程中,还能获得对软件系统后续构件的需求经验

    3、软件系统是逐渐扩展的,因此开发者可以通过对诸多构件的开发,逐步积累开发经验。实际上,增量式开发还有利于技术复用,前面构件中设计的算法、采用的技术策略、编写的源码等,都可以应用到后面将要创建的增量构件中去

    4、增量式开发有利于从总体上降低软件项目的技术风险。个别的构件或许不能使用,但一般不会影响到整个系统的正常工作

    5、实际上,在采用增量模型时,具有最高优先权的核心增量构件将会被最先交付,而随着后续构件不断被集成进系统,这个核心构件将会受到最多次数的测试。这意味着软件系统最重要的心脏部分将具有最高的可靠性,这将使得整个软件系统更具健壮性

     

    四、螺旋模型

    4.1什么是螺旋模型

    螺旋模型是一种演化软件开发过程模型,它兼顾了快速原型的迭代特征以及瀑布模型的系统化与严格监控。螺旋模型最大的特点在于引入了其他模型不具备的风险分析,使软件在无法排除重大风险时有机会停止,以减小损失。同时,在每个迭代阶段构建原型是螺旋模型用以减小风险的途径

    螺旋模型是快速原型模型以进化的开发方式为中心,在每个项目阶段使用瀑布模型法。该模型的每一个周期都包括需求定义、风险分析、工程实现和评审4个阶段,由这4个阶段进行迭代。软件开发过程每迭代一次,软件开发又前进一个层次。用螺旋模型的软件过程如下

    简化的螺旋模型

    完整的数据模型

     

    图中带箭头的点划线的长度代表当前累计的开发费用,螺旋线的角度值代表开发进度,螺旋线的每个周期对应于一个开发阶段

    图中的四个象限代表了以下活动

    1. 制定计划:确定软件目标,选定实施方案,弄清项目开发的限制条件
    2. 风险分析:分析评估所选方案,考虑如何识别和消除风险
    3. 实施工程:实施软件开发和验证
    4. 客户评估:评价开发工作,提出修正建议,制定下一步计划

    4.2特点

    螺旋模型在“瀑布模型”的每一个开发阶段前引入一个非常严格的风险识别、风险分析和风险控制,它把软件项目分解成一个个小项目。每个小项目都标识一个或多个主要风险,直到所有的主要风险因素都被确定

    螺旋模型强调风险分析,使得开发人员和用户对每个演化层出现的风险有所了解,继而做出应有的反应,因此特别适用于庞大、复杂并具有高风险的系统

    4.3优缺点

    优点

    1. 对可选方案和约束条件的强调有利于已有软件的重用,也有助于把软件质量作为软件开发的一个重要目标
    2. 减少了过多测试(浪费资金)或测试不足(产品故障多)所带来的风险
    3. 在螺旋模型中维护只是模型的另一个周期,在维护和开发之间并没有本质区别

    缺点

    1. 采用螺旋模型需要具有相当丰富的风险评估经验和专门知识,在风险较大的项目开发中,如果未能够及时标识风险,势必造成重大损失
    2. 过多的迭代次数会增加开发成本,延迟提交时间

    4.4限制条件

    1. 螺旋模型强调风险分析,但要求许多客户接受和相信这种分析,并做出相关反应是不容易的,因此,这种模型往往适应于内部的大规模软件开发
    2. 如果执行风险分析将大大影响项目的利润,那么进行风险分析毫无意义,因此,螺旋模型只适合于大规模软件项目
    3. 软件开发人员应该擅长寻找可能的风险,准确地分析风险,否则将会带来更大的风险

    一个阶段首先是确定该阶段的目标,完成这些目标的选择方案及其约束条件,然后从风险角度分析方案的开发策略,努力排除各种潜在的风险,有时需要通过建造原型来完成。如果某些风险不能排除,该方案立即终止,否则启动下一个开发步骤。最后,评价该阶段的结果,并设计下一个阶段

    展开全文
  • 快速幂算法——带你从零开始一步一步优化 目录 快速幂算法——带你从零开始一步一步优化 什么是快速幂算法 再次思考 快速幂算法初步入门 压榨性能再优化 终极优化 参考资料 博客文章版权声明 什么是...

                    快速幂算法——带你从零开始一步一步优化


    目录

                    快速幂算法——带你从零开始一步一步优化

    什么是快速幂算法

    再次思考

     

    快速幂算法初步入门

    压榨性能再优化

    终极优化

    参考资料

    博客文章版权声明


    什么是快速幂算法


    首先,我们先来看一道ACM程序设计题,这道题是杭电OJ中序号为2035的题目,没做过这道题目的同学可以跟着一起做一下(点击此处传送),题目如下:

    问题描述:

    这道题目乍一看会觉得并不难啊,题目短短一行而已,而且思路也很容易,求幂这种算法一般在初学程序设计语言的时候应该都有联系过,只要写一个简单的循环就能够搞定。

    /**
     * 普通的求幂函数
     * @param base 底数
     * @param power  指数
     * @return  求幂结果的最后3位数表示的整数
     */
    long long normalPower(long long base,long long power){
        long long result=1;
        for(int i=1;i<=power;i++){
            result=result*base;
        }
        return result%1000;
    }
    
    

    这道题不是分分钟解决吗?接下来,让我们来写一个主函数测试一下:

    int main(){
        long long base,power;
        cin>>base>>power;
    
        cout<<"base="<<base<<" power="<<power<<" "<<normalPower(base,power)<<endl;
    
        return 0;
    
    }

    然后,让我们愉快的来求一下2^100的结果的后三位数表示的整数是什么吧!输出结果如下:

    为什么答案会是0呢?明明没有错误的啊!~ 

    先不急,我们再来考虑一下,这道题其实出的很有意思,题目要求你输出结果的后三位,为什么不让你直接输出结果呢?难道仅仅只是为了增大题目的难度吗?当然不是,我们在初中就学过“指数爆炸”,下面我们在来回顾一下“指数”的概念:

    指数:在乘方a中,其中的a叫做底数,n叫做指数,结果叫幂。

    f(x)=a^x , 随着x单位长度的递增,f(x)会呈“爆炸性”增长。

    一张纸对折一次,厚度变成原来的2倍。再对折第二次,变为原来的2的2次方倍即4倍。以此类推,假设纸的厚度为0.1mm,则对折24次以后,长度超过1千米;对折39次达55000千米,超过地球赤道长度;对折42次达44万千米,超过地球至月球的距离;对折51次达22亿千米,超过地球至太阳的距离;对折82次为51113光年,超过银河系半径的长度。

    因此,如果题目让你求2的100次方,貌似我们程序设计语言中最大的long lnog类型也无法承载这么大的数值,所以题目才不会要求你输出结果,因为结果可能会非常的大,大到没有任何类型可以承载。所以我们会发现上面的结果为什么是0,因为已经发生溢出了。

    那为什么题目要求输出结果的最后三位数表示的整数呢?有的同学可能会问:求一个数的最后三位数表示的整数好办,只要用这个结果进行“取模”运算,让其对1000取模,得到的数就是这个数最后三位数表示的整数。(例如:12345的最后三位数表示的整数是:12345%1000=345)。但是,你这结果都无法求出来,让我怎么进行“取模”运算呢?你这不是瞎闹吗?

    别急,我们首先来了解一下“取模”运算的运算法则:(具体的证明感兴趣的同学可以问度娘)

    1. (a + b) % p = (a % p + b % p) % p (1)

    2. (a - b) % p = (a % p - b % p ) % p (2)

    3. (a * b) % p = (a % p * b % p) % p (3)

    其中我们只要关注第“3”条法则即可:(a * b) % p = (a % p * b % p) % p ,我们仔细研究一下这个运算法则,会发现多个因子连续的乘积取模的结果等于每个因子取模后的乘积再取模的结果。也就是说,我们如果要求:

    (a*b*c)%d=(a%d*b%d*c%d)%d;

    因此,我们可以借助这个法则,只需要在循环乘积的每一步都提前进行“取模”运算,而不是等到最后直接对结果“取模”,也能达到同样的效果。

    所以,我们的代码可以变成这个样子:

    /**
     * 普通的求幂函数
     * @param base 底数
     * @param power  指数
     * @return  求幂结果的最后3位数表示的整数
     */
    long long normalPower(long long base,long long power){
        long long result=1;
        for(int i=1;i<=power;i++){
            result=result*base;
            result=result%1000;
        }
        return result%1000;
    }

    我们再来测试一下,这样又能不能输出结果呢?我们仍然来求一下2^100的后三位是什么:

    这一次完美的得到了我们想要的结果。2^100的幂结果的后三位整数位376。

    为了打消一些同学对这个运算法则的怀疑,我们再用一个结果比较小的式子来验证一下:我们知道2^10为1024,按理来说,最后输出的结果的后三位数表示的整数应该是24,那么是不是这样呢?我们来试一试:

    最后的结果果然是24,所以这个法则是没有问题的。我们把下面的代码提交给OJ看一下是否能通过:

    #include <iostream>
    #include <cmath>
    
    using namespace std;
    
    /**
     * 普通的求幂函数
     * @param base 底数
     * @param power  指数
     * @return  求幂结果的最后3位数表示的整数
     */
    long long normalPower(long long base, long long power) {
        long long result = 1;
        for (int i = 1; i <= power; i++) {
            result = result * base;
            result = result % 1000;
        }
        return result % 1000;
    }
    
    int main() {
        long long base, power;
        while (true) {
            cin >> base >> power;
            if (base == 0 && power == 0) break;
            cout << normalPower(base, power) << endl;
        }
        return 0;
    
    }

    最后的结果是成功Accept了。

    再次思考


    虽然这个求幂的方法很有用,并且提交给OJ也直接Accept了,但是我们来考虑一下这个算法的时间复杂度,假设我们求2的100次方,那么将会执行100次循环。如果我们分析一下这个算法,就会发现这个算法的时间复杂度为O(N),其中N为指数。求一下小的结果还好,那如果我们要求2的1000000000次方呢?这个程序可能会运行很久很久,具体会多久呢,让我们来测试一下,测试代码如下:

    #include <iostream>
    #include <cmath>
    #include <time.h>
    
    using namespace std;
    
    /**
     * 普通的求幂函数
     * @param base 底数
     * @param power  指数
     * @return  求幂结果的最后3位数表示的整数
     */
    long long normalPower(long long base, long long power) {
        long long result = 1;
        for (int i = 1; i <= power; i++) {
            result = result * base;
            result = result % 1000;
        }
        return result % 1000;
    }
    
    int main() {
        clock_t start, finish;
        //clock_t为CPU时钟计时单元数
        long long base, power;
        cin >> base >> power;
        start = clock();
        //clock()函数返回此时CPU时钟计时单元数
        cout << normalPower(base, power) << endl;
        finish = clock();
        //clock()函数返回此时CPU时钟计时单元数
        cout << "the time cost is" << double(finish - start) / CLOCKS_PER_SEC;
        //finish与start的差值即为程序运行花费的CPU时钟单元数量,再除每秒CPU有多少个时钟单元,即为程序耗时
        return 0;
    
    }

    结果如图所示:

    我们发现,虽然结果是成功求出来了,但是用了将近18秒的时间才求出最后的答案。这效率当然是非常的低下的,更谈不上实际的生产应用了。那么有没有什么好的办法能够对其进行优化呢?接下来就是我们本次的主题了:快速幂算法。

     

    快速幂算法初步入门


    快速幂算法能帮我们算出指数非常大的幂,传统的求幂算法之所以时间复杂度非常高(为O(指数n)),就是因为当指数n非常大的时候,需要执行的循环操作次数也非常大。所以我们快速幂算法的核心思想就是每一步都把指数分成两半,而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小,所需要执行的循环次数也变小,而最后表示的结果却一直不会变。让我们先来看一个简单的例子:

    3^10=3*3*3*3*3*3*3*3*3*3

    //尽量想办法把指数变小来,这里的指数为10

    3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)

    3^10=(3*3)^5

    3^10=9^5

    //此时指数由10缩减一半变成了5,而底数变成了原来的平方,求3^10原本需要执行10次循环操作,求9^5却只需要执行5次循环操作,但是3^10却等于9^5,我们用一次(底数做平方操作)的操作减少了原本一半的循环量,特别是在幂特别大的时候效果非常好,例如2^10000=4^5000,底数只是做了一个小小的平方操作,而指数就从10000变成了5000,减少了5000次的循环操作。

    //现在我们的问题是如何把指数5变成原来的一半,5是一个奇数,5的一半是2.5,但是我们知道,指数不能为小数,因此我们不能这么简单粗暴的直接执行5/2,然而,这里还有另一种方法能表示9^5

    9^5=(9^4)*(9^1)

    //此时我们抽出了一个底数的一次方,这里即为9^1,这个9^1我们先单独移出来,剩下的9^4又能够在执行“缩指数”操作了,把指数缩小一半,底数执行平方操作

    9^5=(81^2)*(9^1)

    //把指数缩小一半,底数执行平方操作

    9^5=(6561^1)*(9^1)

    //此时,我们发现指数又变成了一个奇数1,按照上面对指数为奇数的操作方法,应该抽出了一个底数的一次方,这里即为6561^1,这个6561^1我们先单独移出来,但是此时指数却变成了0,也就意味着我们无法再进行“缩指数”操作了。

    9^5=(6561^0)*(9^1)*(6561^1)=1*(9^1)*(6561^1)=(9^1)*(6561^1)=9*6561=59049

    我们能够发现,最后的结果是9*6561,而9是怎么产生的?是不是当指数为奇数5时,此时底数为9。那6561又是怎么产生的呢?是不是当指数为奇数1时,此时的底数为6561。所以我们能发现一个规律:最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。

    让我们来看一段简单的动画演示(点击放大):

    接下来,再让我们用代码来演示一下上面的算法:

    long long fastPower(long long base, long long power) {
        long long result = 1;
        while (power > 0) {
            if (power % 2 == 0) {
                //如果指数为偶数
                power = power / 2;//把指数缩小为一半
                base = base * base % 1000;//底数变大成原来的平方
            } else {
                //如果指数为奇数
                power = power - 1;//把指数减去1,使其变成一个偶数
                result = result * base % 1000;//此时记得要把指数为奇数时分离出来的底数的一次方收集好
                power = power / 2;//此时指数为偶数,可以继续执行操作
                base = base * base % 1000;
            }
        }
        return result;
    }

    我们再来测试一下此时的快速幂算法和普通的求幂算法的效率,我们仍然来求2的1000000000次方,看一看用时又会是多少:

    真让人简直不可思议,竟然只花了0.002秒就求出了结果,而且结果也是376,然而普通的算法却用了将近18秒的时间才求出最后的结果。

    压榨性能再优化


    虽然上面的快速幂算法效率已经很高了,但是我们仍然能够再一次的对其进行“压榨级别”的优化。我们上面的代码看起来仍然有些地方可以再进一步地进行简化,例如在if和else代码块中仍然有重复性的代码:

                power = power / 2;
                base = base * base % 1000;

                power = power - 1;//把指数减去1,使其变成一个偶数
                power = power / 2;
    可以压缩成一句:
                power = power / 2;

    因为power是一个整数,例如当power是奇数5时,power-1=4,power/2=2;而如果我们直接用power/2=5/2=2。在整型运算中得到的结果是一样的,因此,我们的代码可以压缩成下面这样:

    long long fastPower(long long base, long long power) {
        long long result = 1;
        while (power > 0) {
            if (power % 2 == 1) {
                result = result * base % 1000;
            }
            power = power / 2;
            base = (base * base) % 1000;
        }
        return result;
    }

    接下来,我们来测试一下优化后的性能如何,仍然是求2的1000000000次方:

    结果仍然是正确的376,但时间上的花费从0.002减少成了0.001。

     

    终极优化


    在C语言中,power%2==1可以用更快的“位运算”来代替,例如:power&1。因为如果power为偶数,则其二进制表示的最后一位一定是0;如果power是奇数,则其二进制表示的最后一位一定是1。将他们分别与1的二进制做“与”运算,得到的就是power二进制最后一位的数字了,是0则为偶数,是1则为奇数。例如5是奇数,则5&1=1;而6是偶数,则6&1=0;因此奇偶数的判断就可以用“位运算”来替换了。

    同样,对于power=power/2来说,也可以用更快的“位运算”进行替代,我们只要把power的二进制表示向右移动1位就能变成原来的一半了。

    最后,我们的代码就能优化成下面这样:
    long long fastPower(long long base, long long power) {
        long long result = 1;
        while (power > 0) {
            if (power & 1) {//此处等价于if(power%2==1)
                result = result * base % 1000;
            }
            power >>= 1;//此处等价于power=power/2
            base = (base * base) % 1000;
        }
        return result;
    }

    我们仍然测试一下求2的1000000000次方,看看终极优化后的代码的性能是怎样的:

    简直可怕,时间花费竟然接近于0秒,我们从最开始的18秒最后压缩到接近0秒,真的是感慨算法的威力!如果同样两家公司,采用不同的算法,给用户带来的体验区别是非常大的,这无不让我们感受到算法的威力。

     

    基础不牢?新手不友好?无人带路?关注《扬俊的小屋》公众号吧!


     

    参考资料


    【1】https://www.rookieslab.com/posts/fast-power-algorithm-exponentiation-by-squaring-cpp-python-implementation#brute-force-python-implementation  作者:Ravi Ojha 翻译:刘扬俊

    【2】百度百科——指数爆炸

    https://baike.baidu.com/item/%E6%8C%87%E6%95%B0%E7%88%86%E7%82%B8/8440078?fr=aladdin 

     

    博客文章版权声明


     

     

     

     

     

     

     

     

    展开全文
  • C#.NET NFine快速开发框架_V1.1 程序

    万次下载 热门讨论 2016-08-20 00:31:12
    NFine 是基于 C# 语言的极速 WEB + ORM 框架,其核心设计目标是开发迅速、代码量少、学习简单、功能强大、轻量级、易扩展,让Web开发更迅速、简单。能解决60%重复工作。为您节约更多时间,去陪恋人、家人和朋友。...
  • C#使用 MQTTnet 快速实现 MQTT 通信 Demo

    千次下载 热门讨论 2019-03-14 10:15:44
    此Demo对应本人博客文章《MQTT(一)C#使用 MQTTnet 快速实现 MQTT 通信》 开发环境Win7 + vs2017
  • 快速排序(过程图解)

    万次阅读 多人点赞 2018-07-02 12:10:50
    于是我就想了一个办法,后来才知道原来这就是“快速排序”,请允许我小小的自恋一下(^o^)。 方法其实很简单:分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于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;
    }

     

     
    展开全文
  • 软件工程--快速原型模型详解

    千次阅读 2019-11-11 15:41:31
    快速原型模型 所谓快速原型是快速建立起来的可以在计算机上运行的程序,它所能完成的功能往往是最终产品能完成的功能的一个子集。 如下图所示(图中实线箭头表示开发过程,虚线箭头表示维护过程)。 快速原型模型的...
  • 快速排序法(详解)

    万次阅读 多人点赞 2019-07-01 17:27:49
    假设对以下10个数进行快速排序: 6 1 2 7 9 3 4 5 10 8 我们先模拟快速排序的过程:首先,在这个序列中随便找一个数作为基准数,通常为了方便,以第一个数作为基准数。 6 1 2 ...
  • PyQt5快速开发与实战pdf

    万次阅读 多人点赞 2019-04-22 00:24:50
    下载 第1章 认识PyQt 5 1 1.1 PyQt框架简介 1 1.1.1 PyQt 5的特点 3 1.1.2 Qt与PyQt的关系 4 1.1.3 其他图形界面开发库介绍 4 1.1.4 PyQt 4/PyQt 5 6 1.1.5 Python 2/Python 3 6 1.2 PyQt 5环境搭建 7 ...
  • 图解快速排序(C++实现)

    万次阅读 多人点赞 2019-03-05 10:25:18
    参考大话数据结构这本书对快速排序的讲解,本文作一个梳理,并在最后给出快排的C++实现代码。 假设我们现在对“612 79345 108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到...
  • Winform快速开发框架

    热门讨论 2015-03-25 10:20:44
    支持基类的三层架构,基类中封装了很多常用方法,支持实体类增删改扩展方法,可自定义各类属性及标签,布局采用weifengluo控件,十分小巧,数据库参考配置文件及实体类自己创建即可。
  • 快速排序的运行时间依赖于划分是否平衡,而平衡与否又依赖于用于划分的元素。如果划分是平衡的,那么快速排序算法性能与归并排序一样。如果划分是不平衡的,那么快速排序的性能就接近于插入排序了。在本文中,我们将...
  • 软件过程模型 要点 ...不带反馈环,线性顺序进行,本质是“快速” 确保交付的产品符合客户的要求 还没有证明无懈可击 无完整的需求说明,只有一些基本要求 增量模型 每一个增量均发布一个可操作...
  • 我们输入代码后可以按上方的运行,或者按快捷键shift+回车键快速执行代码 后面的教程所包含的代码都是在jupyter notebook中运行 好了,jupyter notebook的教程在这里,有什么问题可以在评论里回复 
  • 【spark论文翻译】An Architecture for Fast and General Data Processing on Large Cluster 大型集群上的快速和通用数据处理架构。CSDN CODE翻译社区出品。 之前上传的版本图表有问题,这版已经修复。请更新谢谢。
  • 算法 - 快速排序(C#)

    万次阅读 多人点赞 2019-01-29 20:29:11
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!... /* * 快速排序(QuickSort)是对冒泡排序的一种... * 然后再按此方法对这两部分数据分别进行快速排序,整个排序...
  • STM32嵌入式微控制器快速上手

    热门讨论 2014-10-06 11:55:16
    STM32嵌入式微控制器快速上手.pdf。深入浅出的讲解stm32的开发,是入门学习者的一个不错选择。
  • C#Excel大量数据快速导入数据库

    热门讨论 2015-11-06 16:16:39
    C#Excel大量数据快速导入数据库.
  • 快速排序算法

    万次阅读 多人点赞 2019-01-11 21:09:08
    但是这种算法时间复杂度高,当需要排序的元素较多时,程序运行时间很长,因此产生了快速排序算法。该算法的实现可分为以下几步: 1. 在数组中选一个基准数(通常为数组第一个); 2. 将数组中小于基准数的数据移到...
  • 快速

    万次阅读 多人点赞 2019-02-18 11:24:54
    以前我看快速幂真的看不懂,但是当我慢慢对递归(递归大法好)有一些理解后,对二分又理解一些后,就能够自己写出快速幂的递归写法了。 求 a^b % m的值,这个用普通算法我就不说了,时间复杂度O(b) 当我知道快速...
  • Python实现快速排序

    千次阅读 多人点赞 2020-07-12 21:00:14
    Python实现快速排序
  • 在《快速排序-[快速排序的性能]》中,我们给出了在最坏情况下快速排序性能的直观分析,以及它速度比较快的原因。在本文中,我们要给出快速排序性能的更严谨的分析。我们首先从最坏情况分析开始,其方法可以用于原版...
  • 数据结构-快速排序

    万次阅读 多人点赞 2018-08-30 22:56:25
    快速排序 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。  基本思想:  快速排序使用分治的思想,从待排序序列中选取一个记录...
  • 本课程从零开始,以通俗易懂的方式讲解PHP技术,手把手教你掌握每一个知识点。 课程内容包括: 1.PHP简介 2.安装PHP环境 3....访问MySQL 6.状态管理(Cookie、Session) 7.表单处理 8.文件上传 9....!... 讲师介绍
  • C语言快速排序,以及注意点。

    万次阅读 多人点赞 2019-06-13 15:53:55
    快速排序尤其适用于对大数据的排序,它的高速和高效无愧于“快速”两个字。虽然说它是“最常用”的,可对于初学者而言,用它的人却非常少。因为虽然很快,但它也是逻辑最复杂、最难理解的算法,因为快速排序要用到...
  • 数据结构-快速排序(含全部代码)

    万次阅读 2021-03-15 17:09:19
    目录 函数分析 代码 全部代码 截图 算法可视化 ...L,int low,high) 参数:顺序表L,待排...//快速排序分割函数 int Partition(SqList &L,int low,int high) { int pivotekey = L.data[low]; //保存枢轴 whil
  • 快速排序算法——C/C++

    万次阅读 多人点赞 2019-06-12 22:55:14
    快速排序 1、算法思想 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 2、实现原理 ...
  • 什么是快速开发框架

    千次阅读 2018-09-18 16:52:08
    前言 做为一个程序员,在开发的过程中会发现,有框架同无框架,做起事来是完全不同的概念,关系到开发的效率、程序的健壮、性能、团队协作、后续功能维护、扩展.........那么什么是快速开发框...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,428,745
精华内容 1,371,498
关键字:

快速