精华内容
下载资源
问答
  • 详解五大排序算法

    千次阅读 2016-06-05 02:54:56
    为什么要学习排序 一旦建立一个重要的数据库后,就可能根据某些需求对数据进行不同方式的排序: 比如闹钟功能,按时间远近排序出 闹钟列表,联系人列表按字母A-Z排序,城市列表按省市县的类别排序等等。 排序...

    为什么要学习排序



    一旦建立一个重要的数据库后,就可能根据某些需求对数据进行不同方式的排序:

    比如闹钟功能,按时间远近排序出 闹钟列表,联系人列表按字母A-Z排序,城市列表按省市县的类别排序等等。

    排序非常重要而且非常耗时,幸好 人们已经总结出一系列的排序供我们学习,使用。

    如何排序?


    NBA总决赛正在如火如荼的进行,老詹也正朝着他的第5个总亚军前进着。假设骑士队队员在运动场上排列成一队,如图所示,所有队员已经站好,准备热身,现在需要按身高从低到高 为队员们排队(最矮的站在左边),给他们照一张集体照,应该怎么排队呢?

    在排序这件事情上,人与计算机程序相比有以下优势:我可以同时看到所有的队员,并且可以立刻找出最高的一个,毫不费力得测量和比较每一个人的身高。而且队员们不一定要固守特定的空间,他们可以相互推推攘攘就腾出了位置,还能互相前后站立,经过一些具体的调整,毫不费力地给队员们排好队

    这里写图片描述


    计算机程序员却不能像人这样通览所有的数据,它只能根据计算机的“比较”操作,在同一时间内对两个队员进行比较,算法 将”比较”的行为视为一个反复出现的问题,在人类看来是非常简单的事情,但程序算法 却只能一步一步得解决具体问题 和遵循一些简单的规则。

    算法的本质就是拆分问题,按照最简单的规则,把问题拆分为一步一步交给计算机执行。


    看上去这么简单,对吗:

    1. 比较两个数据项
    2. 交换两个数据项,或复制其中一项


    重复这两步循环执行,直到全部有序为止。

    不要轻视算法,因每种算法具体实现的细节有所不同。

    BUBBLE 冒泡排序



    冒泡排序算法运行起来非常慢,但概念上它是排序算法中最简单的,适合刚开始研究算法技术时的入门。


    首先由一组无序的数字:

    这里写图片描述

    我录制了一段冒泡排序的执行过程(需要1-2秒的缓冲):

    这里写图片描述

    耐心观看完后,我们可以总结出冒泡排序的规则:

    1. 比较两个数字
    2. 如果左边的数字大,则交换两个数字的位置
    3. 向右移动一个位置,比较下两个数字

      沿着这个顺序比较下去,一直比较到最右端,虽然没有把所有的数字排好序,但是,数字中最大的那一个已经排放在最右边了,这个是一轮比较下来 可以确定的结果。

      下一轮,我们继续从最左边开始。

      这也是这个算法被称为冒泡排序的原因:因为在算法执行的时候,最大的数据项 总是 “冒泡”到数组的顶端【数组的排列规则,从左到右0-N】。


    效果这么棒,如何开始我们的第一行代码呢?

    首先封装一个BUBLE数组对象

    class ArrayBub
    {
        private long[] a;//定义一个数组
        private int nElems;//数据的个数
    //-------------------------------------
        public ArrayBub(int max){   //构造函数
            a =new long[max];   //创建数组 
            nElems=0;   //还没有添加数据
        }
    //-------------------------------------
        public void insert(long value){   //向数组中添加元素
        a[nElems] = value;  //插入数据
        nElems++;  //数据个数+1
        } 
    //-------------------------------------
        public void display(){
            for(int j=0 ; j<nElems ; j++){   //遍历数组中每一个元素
                System.out.print(a[j]+" ");   //展示
                System.out.println("");  
            }
        }
    //-------------------------------------
        public void bubbleSort(){
            int out ,in;
            for(out=nElems-1;out>1;out--){  //外循环  每一轮都是从左到右 向后进行的
                for(in=0;in<out;in++){   //内循环  每一次循环,都是把小的那一个数据放在前面
                    if(a[in] >a[in+1] ){
                        swap(in,in+1);
                        }
                    }
            }//end bubblesort()
        }
    //-------------------------------------
    
        private void swap(int one,int  two){
            long temp =a[one]
            a[one] = a[two];
            a[two] = temp;
        }
    
    }


    接着测试我们的代码:

    class BubbleSortAPP{
    
        public static void main(String args){
    
        int maxSize=100;              //数组的长度
        ArrayBub arr;                 //声明我们封装的Bub数组对象
        arr=new ArrayBub(maxSize);    //初始化数组
    
        arr.insert(77);               //插入10个数据
        arr.insert(22);
        arr.insert(44);
        arr.insert(66);
        arr.insert(88);
        arr.insert(11);
        arr.insert(33);
        arr.insert(77);
        arr.insert(77);
        arr.insert(77);
    
        arr.display();                 //展示数据
    
        arr.bubbleSort();              //对数组中的数据 执行排序操作
    
        arr.display();                 //展示排序后的数据
        }  //end main()
    }//end class BubbleSortAPP

    核心代码 bubbleSort()方法只有四行(大括号可以缩进):

    for(out=nElems-1;out>1;out--){  //外循环  每一轮都是从左到右 向后进行的
                for(in=0;in<out;in++){   //内循环  每一次循环,都是把小的那一个数据放在前面
                    if(a[in] >a[in+1] ){  //比较大小
                        swap(in,in+1);   //交换
                        }
                    }
            }//end bub


    这个算法的思路是要将最小的数据项放在数组的最开始(数组下标为0),并将最大的数据项放在ishuzu的最后(数组下标为nElems-1),外层循环的计数器out,从数组最后开始,即out=nElems-1,每经过一次循环out减1,下标大于out的数据项都已经排好序了,变量out在没完成一次内部循环(计数器为in)后就左移一位,因此算法就不再处理那些已经排好序的数据了。

    内循环计数器in从数组的最开始算起,in=0,没弯沉过一次内部循环循环体加1,当它等于out时 结束一次循环,在内存for循环中,数组下标为 in 和in+1的两个数据项比较,如果下标为 in 的数据项大于下标为in+1的数据项,则交换两个数据项。

    不变性


    在许多算法中,有些条件在算法执行时,是不变的,这些条件称为不变性。认识不变性对理解算法是游泳的,在一定的情况下对调试也有用,可以反复得检查不变性是否为真,如果不是得话 就标记出错。

    在上述的bubbleSort.java中,不变性是指 out 右边的所有数据项为有序,在算法的整个运行过程中,这个条件始终为真。(在第一轮排序开始前,尚未排序,而out开始时在数据项的最右边,它已经是最右了,没有数据项在out的右边)

    冒泡排序的效率


    通过 考察10个数据项,第一轮比较了9次第二轮比较了8次,以此类推 9+8+7+6+5+4+3+2+1=45

    小学隔壁家的孩子,高斯同学就已经归纳出这种序列的求和公式:N*(N-1)/2 ;

    再运用大学高等数学的 “等价无穷小”定理,在N无限大的情况下, 2和 -1可以忽略不计,从而推导出算法作了N²次比较,而交换次数是小于比较次数的,而且如果数据是随机的,那么大概有一半数据需要交换,交换的次数也是N²,所以我们认为冒泡排序的运行需要O(N²)时间级别,从我录制的gfit原理图来看,冒泡排序的速度是很慢的,

    无论何时,只要看到循环嵌套在另一个循环里,就可以怀疑这个算法的运行时间为O(N²)级,

    SELECT 选择排序



    选择排序改进了冒泡排序,将必要的交换次数从O(N²)减少到O(N)。看上去非常棒了,不幸的时候比较次数仍保持为 O(N²),不要遗憾,选择排序仍然为大量的排序做出了一个非常重要的改进:

    因为izhexie大量的记录 需要在内存中移动,这就使得交换的时间和比较的时间相比,交换的时间更为重要(一般来说,在Java语言中不是这种情况,Java中只是改变了引用位置,而内存中世纪对象的位置并没有发生改变)

    理解一下选择排序的原理


    一组数据,

    这里写图片描述

    选择排序的原理,

    这里写图片描述

    * 使用选择排序算法对老詹的队友们排序,*


    在选择排序中,不再比较两个相邻的队员,因此,需要记录下某个指定队员的高;可以用记事本记下队员的身高,同时还需要准备好一条紫红色的毛巾(不是搞基)。

    进行选择排序 就是把所有的队员扫描一遍,从中选择出最矮的一个队员,最矮的这个队员和站在队列最左端的队员交换位置,即占到0号位置,现在最左端的队员是有序的了,不再需要交换位置。注意,在这个算法中有序的队员都排在队列的最左边(数组中较小的下标值),而冒泡排序则是优先排列在队列的右边。

    排序从最左边开始,记录本上写下最左端球员的身高,并且在他的脖子上挂上红色毛巾,于是开始用下一个球员的身高和记录本上记录的值比较,如果下一个球员更矮,则在本子上划掉第一个球员的身高,记录第二个队员的身高,同时把红色毛巾从第一个球员的脖子上拿下来,挂在第二个队员的脖子上,继续沿着队列走下去,

    一轮下来,毛巾就会落在最矮的队员面前,接着,唯一拥有红毛巾的队员和队列最左边的队员交换位置,现在已经对一个队员排好序了,这期间做了N-1次比较,淡只进行了一次交换。

    嗯,老詹对你的建议很满意。

    选择排序的代码实现

    class ArraySelect{
        private long[] a;
        private int nElems;
    //--------------------------------
        public ArraySelect(int max){
        a = new long[max];
        nElems = 0;
        }
    //--------------------------------
        public void insert(long value){
        a[nElems] = value;
        nElems++;
        }
    //----------------------------------
        public void display(){
        for(int j=0; j<nElems; j++)
         System.out.print(a[j]+" ");
         System.out.println("");
        }
    //----------------------------------
        public void selectionSort(){
            int out,in,min;
            for(out=0;out<nElems-1;out++){  //外循环
                min=out;   //用红毛巾记录最小值
                for(in=out+1;in<nElems;in++){  //最小值
                    if(a[in]<a[min]){   //如果是最小值
                        min=in;   //就把红毛巾递给最下的
                        swap(out,min);
                    }
                }
            }//end for(out)
        }//end selectionSort
    //-----------------------------------
        private void swap(int one,int two){
            long temp=a[one];
            a[one] = a[two];
            a[two] = temp;
        }
    //------------------------------------
    
    
    }


    接着测试我们的选择排序吧:

    class SelectSortApp{
        public static void main(String[] args){
        int maxSize = 100;
        ArraySel arr;
        arr = new ArraySel(maxSize)
    
        arr.insert(88);
        arr.insert(81);
        arr.insert(33);
        arr.insert(87);
        arr.insert(38);
        arr.insert(22);
        arr.insert(11);
        arr.insert(44);
        arr.insert(77);
        arr.insert(99);
    
        arr.display();
    
        arr.selectionSort();
    
        arr.display();
    
      }//end main()
    
    }//end class

    不变性


    在此例程序中,下标小于或等于out的位置 数据项总是有序的。

    选择排序的效率


    此例当中,对于10个数据项,需要45次比较,而10个数据项只需要10次交换,扩大数量级,对于100个数据项,需要4950次比较,但只有100次交换,运用高等数学“等价无穷小”定理,N值越大,比较次数是主要的,所以结论是选择排序和冒泡排序一样 都是O(N²)的效率,但选择排序无疑更快,因为它交换的次数更少。

    所以,不要小瞧选择排序。

    INSERT 插入排序


    在大多数情况下,插入排序比冒泡排序,选择排序要好的多。虽然插入排序仍然需要O(N²)的时间,但是在一般的情况下,它要比冒泡排序快一倍,比选择排序快一点,尽管它比冒泡排序算法和选择排序算法都更麻烦一些,但它也并不复杂,它经常被用在教复杂的排序算法的最后阶段,例如快速排序

    插入排序原理


    一段数据:

    这里写图片描述

    我录制了一段原理展示:

    这里写图片描述

    用插入排序提醒老詹吧


    插入排序之前,队员随机站好。从排序过程的中间开始,可以更好地理解插入排序,这时队列已经排好了一半。

    局部有序

    此时,队友中间有一个作为标记的队员,还是用紫红色毛巾作标记吧,这个作为标记的队员的左边的所有队员已经是局部有序了。这意味着这一部分人之间是按顺序排列的:每个人比他左边的人都搞,然而这些队员在队列中最终的位置还没有确定,因为,当没有被排过序的队员要插入到他们中间的时候,他们的位置还要变动。

    注意,局部有序在冒泡排序和选择排序中是不会出现的。在这两个算法中,一组数据项在某个时刻是完全有序的:在插入排序中,一组数据仅仅是局部有序的。

    被标记的队员

    作为标记的队员,称为“被标记的队员”,他和他右边所有的队员都是未排序的

    如图:
    这里写图片描述


    下面价格要做的是在局部的 有序组中适当的位置 插入被标记的队员,然而要做到这一点,需要把部分已排序的队员右移腾出空间,为了提供移动所需的空间,就先让被标记的队员出列(在程序中,这个出列的行为,是该数据项被存储在一个临时变量中)

    现在移动已经排过序的队员来腾出空间,将局部有序中最高的队员移动到原来被标记队员所在位置,次高的队员移动到原来最高的队员所在位置,以此类推。

    局部有序的部分里多了一个队员,而未排序的部分少了一个队员,作为标记的球员,向右移动一个位置,所以他仍然放在未排序部分的最左边的队员勉强,重复这个过程,直到所有未排序的队员都被插入到局部有序队列中的合适位置。

    插入排序的核心代码:

    public void insertionSort(){
        int in,out;
        for(out=left+1;out<nElems;out++){ //外循环是分界线
            long temp=a[out];   //删除被标记的数据
            in = out ;   //srat shifts at  out
            while(in>0&&a[in-1]>=temp){  //until one is smaller
                a[in] = a[in-1];  //shift item right,
                --in;   //go left one position
            }
            a[in] =temp;   //insert marked item
        }// end for
    }//end insertionSort()

    插入排序的完整代码改日补上


    在外层的for循环中,out变量从1开始,向右移动,它标记了未排序部分的最左端的数据,而在内层的while循环中,in变量从out变量开始,向左移动,直到temp变量小于 in 所指的数组数据项,或者它已经不能再往左移动,while 循环的每一轮循环都向右移动了一个已排序的数据项。

    插入排序中的不变性


    在每轮结束时,在标记的位置项插入后,比outer变量下标号小的数据项都是有序的

    插入排序的效率(有趣)


    这个算法需要多少次比较和复制呢?在第一轮排序中,它最多比较一次,在第二轮最多比较两次,以此类推

    1+2+3+…+N-1=N*(N-1)/2 次比较;

    复制的次数,大致等于比较的次数,然而,一次复制与一次交换的时间耗费不同,相对于 随机顺序的数据这个算法比冒泡排序快一倍,比选择排序略快,

    在任意情况下,插入排序的时间复杂度也为O(N²)。

    有趣的是

    对于已经有序或者基本有序的数据来说,插入排序要好得多,当数据有序的时候,while循环的条件总是false吗所以它成为了外层循环中的一个简单语句,执行N-1此,算法运行只需要O(N)的时间。这对一个基本有序的文件进行排序是一个简单而有效的方法。


    然而,对于逆序排列的数据,每次比较和移动都会执行,在这种情况下,插入排序 并不比冒泡排序快。

    MERGE 归并排序


    直接上手归并排序?NO!


    我们首先得了解递归的知识:

    1. 限于篇幅和时间,点击这里了解递归
    2. 以后会自己写一篇递归相关的博文,敬请关注

    感受归并排序

    一组随机数据:

    这里写图片描述

    归并排序流程:

    这里写图片描述

    详解归并排序


    1. 归并排序有那么厉害吗?
    冒泡排序,插入排序和选择排序要用O(N²),而归并排序只要O(N*log
    N)
    如果数据项N=10000,那么N²就是100000000,而N*logN只是40000,如果为这么多数据排序,
    选择归并排序的话需要40秒,
    选择插入排序?需要将近28个小时!

    2. 归并排序优点

    容易实现,比快排容易理解

    3. 归并排序的缺点

    它需要在存储器中有另一个大小等于被排序的数据项 长度的数组,如果初始数组几乎占满整个存储器,那么归并排序不会执行,但是如果有足够的内存,归并排序是一个很好的选择。

    归并有两个有序数组

    归并算法的中心 是归并两个 已经有序的数组,归并两个有序数组 A和B,就生成了第三个数组C,数组C包含数组A和B的所有数据项,并且使他们有序的排列在数组C中,

    学习的步骤: 首先理解归并的过程,再去理解它是如何在排序中使用的。

    假设有两个有序数组,不要求有相同的大小,假设数组A有4个数据,B有6个数据,它们被归并到数组C中,C初始化的时候就拥有10个存储空间

    如图:

    这里写图片描述

    在这个图中,带圈的数组显示了把数组A和B中的数据项转移到数组C中的顺序

    接着下图表示了必要的比较,由此来决定复制那个数据项到表C中,再每一次比较之后,较小的数据项被复制到数组A中
    这里写图片描述

    这里写图片描述

    由于数组B在第八步以后是空的,所以不需要再去比较了,只要把数组A中所有剩余的数据项复制到数组C即可。

    我们直接上代码 解释一下归并的代码:

    注意,这只是理解归并排序的序曲,并不是归并的程序

    class  MergeApp{
    //-------------------------------------
        public static void main(String[] args){
            int[] arrayA = {23,47,81,95};
            int[] arrayB = {7,14,39,55,62,74};
            int[] arrayC = new int[10];
            merge(arrayA,4,arrayB,6,arrayC);
        display(arrayC,10);
        }// end main()
    //---------------------------------------
                                        //归并A和B 的数据 到C中                             
        public static void merge(int[] arrayA,int sizeA,
                                int[] arrayB,int sizeB, 
                                int[] arrayC){
            int aDex=0,bDex=0,cDex=0;
    
            while(aDex <sizeA && bDex<sizeB){   //非空数组
                    if(arrayA[aDex] <arrayB[bDex]){
                        arrayc[cDex++]=arrayA[aDex++];
                    }else{
                        arrayC[cDex++]=arrayB[bDex++];
                    }
                }
            }
    
            while(aDex<sizeA){   //数组B如果为空
              arrayC[cDex++]=arrayA[aDex++]  //但数组A不为空
            }
    
            while(bDex<sizeB){ //数组A如果为空
                arrayC[cDex++]=arrayB[bDex++]   //数组B不为空
            }
    }//end merage
    
    
    public static  void display(int[] theArray,int size){
        for(int j=0;j<size;j++){
            System.out.print(theArray[j]+" ");
        System.out.println("");
        }
    }//end class 

    在main()中创建数组 arrayA,arrayB,和数组arrayC;然后调用merge()方法把数组A,B归并到数组C中。

    merge()方法有三个while循环,第一个whie循环是沿着数组arrayA和arrayB走,比较它们的循环,并且复制它们中较小的数据项到arrayC。

    第二个和第三while循环处理的是类似的情况,即,当两个数组arrayB,arrayA中任意一个为空,就把剩下的一个数组归并到arrayC中。

    通过归并进行排序

    归并排序的思想是把一个数组分成两半,排序每一半,然后用merge()方法把数组的两半归并成一个有序的数组。

    那么问题来了,如何为每一部分排序呢?答案是递归:把每一半都分成两个四分之一,对每个四分之一部分排序,然后把 它们归并成一个有序的一半。

    类似的,每一对八分之一 归并成一个有序的四分之一部分,每一对十六分之一部分归并成一个有序的八分之一部分,依次类推,反复地分割数组,直到得到的字数组只含有一个数据项。这就是归并的基本条件:假设只有一个数据项的数组是有序的。

    前面已经看到,递归方法在每次调用自身方法的时候,通常某个参数的大小会减小,而且方法每次返回时,参数值又恢复到以前,在mergeSort()方法中,每一次这个方法调用自身的时候 都会被分成两部份,而且,每一次返回时都会把两个较小的数组合并成一个更大数组。

    当mergeSort()发现两个只有一个数据项的数组时,它就返回,把这两个数据项归并到一个有两个数据项的有序数组中,每个生成的一对两个数据项的数组又被合并成一个有4个数据项的有序数组,这个过程一直持续下去,数组越来越大直到整个数组有序,当初始的数组大小 是二的乘方的时候,最容易看明白:

    【归并越来越大的数组】

    这里写图片描述

    首先一定确保自己理解前面所讲的“归并”的概念。

    从上往下看,整幅图就非常直白了,

    当数组的小不是2的乘方,也容易理解 图:

    这里写图片描述

    那么所有的这些子数组都存放在存储器的什么地方?

    在这个算法中,创建了一个和初始数组一样大小的工作空间数组,这些子数组存储在这个工作空间数组中,也就是之前说的“原始数组中的子数组被复制到工作空间数组对应的空间上”。在每一次归并之后,工作数组的内容 就被复制回原来的数组中。

    注意力集中

    马上就会看到完整的mergeSort程序,首先,关掉手机,关掉音乐,屏蔽一切打扰,把注意力集中到执行归并排序的方法。下面就是它的程序代码:

    private void recMergeSort(long[] workSpace,int lowerBound,
                                            int upperBound){
        if(lowerBound ==upperBound)  //如果只排列一个元素,那么不用排序,直接返回
             return;
        else{
            int mid=(lowerBound+upperBound)//找到最中间的元素,
    
            recMergeSort(workSpace,lowerBound,mid); //sort low half
    
            recMergeSort(workSpace,mid+1,upperBoud);   //sort high half
    
            merge(workSpace,lowerBound,mid+1,upperBound);//对每一半进行归并
        }//end else
    }end recMergeSort

    正如上面看到的一样,除了基本条件外,这个方法只有四条语句,一句是计算中间位置的,还有两个递归,调用recMergeSort(每一个对应数组的一半),最后一句是merge(),用它来归并两个有序的部分。当这个范围只包含一个数组数据项(lowerBound==upperBound)的时候符合基本条件,立即返回。

    在我们的mergeSort.java中,mergeSort实际上只用来创建数组workSpace[],然后调用递归的程序recMergeSort()来执行排序,workSpace数组的创建不放在recMergeSort()的原因?因为递归操作重复创建数组,效率太低。

    下面显示完整的归并排序:

    class DArray{
        private long[] theArray;
        private int nElems;
        //-----------------------------
        public DArray(int max){   //构造函数
            theArray=new long[max];//创建数组
            nElems=0;
        }
        //-----------------------------
        public void insert(long value){   //添加元素
            theArray[nElems] =value;
            nElems++;   //数组下标+1
        }
        //------------------------------
        public void display(){
            for(int j=0;j<nElems;j++){
                System.out.print(theArray[j]+" ");
                System.out.println(" ");
            }
        }
        //-------------------------------
        public void mergeSort(){  //被main()回调
            long[] workSpace=new long[nElems];   //创造一个数组作为工作空间
            recMergeSort(workSpace,0,nElems-1);
        }
        //--------------------------------
        private void recMergeSort(long[] workSpace,int lowerBound,
                                                int upperBound){
            if(lowerBound==upperBound)
                return;
            else{
                intmid=(lowerBound+upperBound)/2;
    
                recMergeSort(workSpace,lowerBound,mid);
    
                recMergeSort(workSpace,mid+1lupperBound);
    
                merge(workSpace,lowerBound,mid+1,upperBound);  //归并
            }
        }
        //----------------------------------
        private void merge(long[] workSpace,int lowPtr
                            int highPtr,int upperBound){
            int j=0;   //工作区下标
            int lowerBound=lowPtr;
            int mid=highPtr-1;
            int n=upperBound-lowerBound+1;  //# of items
    
            while(lowPtr<=mid&& highPtr<=upperBound)
            {
                if(theArray[lowPtr]<theArray[highPtr])
                    workSpace[j++]=theArray[lowPtr++]
                else
                    workSpace[j++]=theArray[highPtr++];
            }//end while
    
            while(lowPtr<=mid)
                workSpace[j++]=theArray[lowPtr++]
    
            while(highPtr<=upperBound)
                workSpace[j++]=theArray[highPtr++];
    
            for(j=0;j<n;j++)
            {
                theArray[lowerBound+j]=workSpace[j];
            }
        }//end merge();
        //------------------------------------------------
    
    }//end class DArray
    class MergeSortApp
    {
        public static void main(String[] args)
        {
            int maxSize=100;   //定义数组的长度
            DArray arr;        
            arr=new DArray(maxSize);  //创建数组
    
            arr.insert(94);
            arr.insert(64);
            arr.insert(33);
            arr.insert(65);
            arr.insert(65);
            arr.insert(55);
            arr.insert(77);
            arr.insert(11);
            arr.insert(38);
            arr.insert(99);
            arr.insert(25);
            arr.insert(15);
    
            arr.display();
    
            arr.mergeSort();
    
            arr.display();
    
        }//end main();
    
    }//end class MergeSortApp

    如果在recMergeSort()方法中添加一些额外输出语句,就可以观察排序过程中的执行过程。请自行书写。

    归并排序的效率

    正如前面提到的那样归并排序的运行时间O(N*logN),

    QUICK 快速排序


    毫无疑问,快速排序是最流行的排序算法,在大多数情况下,快速排序都是最快的,执行时间为O(N*logN)级

    先了解划分算法

    划分是快速排序的根本机制,加上划分本身也是一个有用的操作,所以在讲解快速排序之前,我们先要了解划分算法。

    划分数据就是把数据分为两组,使所有关键字大于特定值的数据在一组,使所有关键字小于特定值的数据项在另一组。

    这里写图片描述

    很容易想象数据的划分结果:比如将学生分成平均成绩高于3.5和低于3.5的两组,

    另外,在算法中,通常称这个特定的值为枢纽pivot;

    划分是如何执行的呢?

    划分过程的partition.java
    
    class ArrayPar{
        private long[] theArray;
        private int nElems;
        //---------------------------
        public ArrayPar(int max){
            theArray=new long[max];
            nElems=0;
        }
        //---------------------------
        public void insert(long value){
            theArray[nElems] =value;
            nElems++;
        }
        //----------------------------
        public int size(){
            return nElems;
        }
        //----------------------------
        public void display(){
            System.out.print("A=");
            for(int j=0;j<nElems;j++)
                System.out.print(theArray[j]+" ");
            System.out.println(" ");
        }
        //----------------------------
        public int partitionIt(int left,int right,long pivot){
            int leftPtr=left-1;
            int rightPtr=right+1;
    
            while(true)
            {
                while(leftPtr<right && theArray[++leftPtr]<pivot)//找出更大一个
                    ;//no 
                while(rightPtr>left &&theArray[--rightPtr]>pivot)
                    ;//no
                if(leftPtr>=rightPtr)  //如果超过了规定的值,就跳出,执行划分
                    break;
                else                   //没有超过规定的值,交换元素下标
                    swap(leftPtr,rightPtr);     
            }//end while
            return leftPtr;
        }//end partitionIt()
    
        //--------------------------------------------
        public void swap(int dex1,int dex2)
        {
            long temp;
            temp=theArray[dex1];
            theArray[dex1]=theArray[dex2];
            theArray[dex2]=temp;
        }//end swap();
    }//end class

    接着在main函数中执行

    class PartitionApp
    {
        public static void main(String[] args)
        {
            int maxSize =16;
            ArrayPar arr;
            arr=new ArrayPar(maxSize);
            for(int j=0;j<maxSize;j++)
            {
                long n=(int)(Math.random()*199);
                arr.insert(n);
            }
            arr.display();
    
            long pivot=99;//枢纽值,
    
            System.out.println("Pivot is "+pivot);
    
            int size=arr.size();
    
            int partDex=arr.partitionIt(0,size-1,pivot);
    
            System.out.println("Partition is at index "+partDex);
    
            arr.display();
        }//end  app
    }

    划分算法

    划分算法由两个指针开始工作,分别为leftPtr和rightPtr,这里的指针只是代表数据项,而不是C++中说的指针。

    实际上,leftPtr初始化时是在第一个数据项的左边一位,rightPtr是在最后一个数据项的右边一位,这是因为zai它们工作之前,它们都要分别的加一和减一。

    1. 停止和交换

    当leftPtr遇到比枢纽小的数据项时,它继续右移,因为这个数据项的位置已经处在数组的正确的位置。

    但是,当遇到比枢纽大的数据项时,它就停下来。

    类似的,当rightPtr遇到大于枢纽的数据项,继续左移,当发现比枢纽小的数据项,它停下来。

    两个内层的while循环,一个用于leftPtr,一个用于rightPtr。

    只有当指针推出while循环的时候,它才停止移动,下面是一段代码,描述了一个不再适当位置的数据项,是如何被执行的:

    while(theArray[++leftPtr]<pivot)
            ;//no
    while(theArray[++rightPtr]>pivot)
            ;//no
    swap(leftPtr,rightPtr);

    第一个while循环发现比枢纽大的数据项时推出,第二个循环在发现比枢纽小的数据项时推出。当这两个循环都推出之后,leftPtr,和rightPtr,指针都指向两个错误位置的数据项,所以要交换位置。

    ok,似乎明白了点什么。

    当两个指针相遇的时候,整个数组划分完毕,breat跳出!

    2. 处理异常数据

    为什么会发生异常?
    如果所有的数据都小于枢纽,leftPtr变量将会便利整个数组,徒劳地寻找大于数据的数据项,然后跑出数组的最右端,产生数组越界异常。类似的情况也会发生在rightPtr上。

    为了避免数组越界异常,
    要在第一个循环中加上leftPtr

    while(theArray[++leftPtr]<pivot)
            ;//no
    while(theArray[++rightPtr]>pivot)
            ;//no

    while循环中的代码相当精巧,

    3. 划分算法的效率

    划分算法的运行时间为O(N)

    快速排序

    1. 基本的快速排序算法

    public void recQuickSort(int left,int right)
    {
        if(right-left<=0)  //size==1 不排序
            return;
        esle
        {
            int partition=partitionIt(left,right);
            recQuickSort(left,partition-1); //对枢纽的左边排序
            recQuickSort(partition+1,right);  //对枢纽的右边排序
        }
    }

    正如大家所看,有三个基本步骤:

    1. 把数组或者子数组划分成左边和右边
    2. 调用自身对左边的一组排序
    3. 调用自身对右边的一组排序。

    每一次划分,所有左边的子数组的数据项都小于右边字数组的数据项,只要对左边数组和右边数组分别排序,整个数组就是有序的了。

    如何对子数组进行排序呢? 通过递归调用排序算法自身就可以。

    如果不是理想状态,数组包含两个或者更多的数据项,算法就需要调用partitionIt()方法对这个数组进行划分。方法返回枢纽的下标值,它指向右边较大的 子数组最左端的数据项,划分标记给 出两个子数组

    如图所示:

    这里写图片描述

    2. 快速排序性能极差的情况:性能为O(N²)

    对100个逆序的数据排序,会发现数据极其缓慢,而且需要划分更多更大的数组,这是为什么?

    问题出在枢纽的选择上。理想状态下,应该选择数据项中的中值 作为枢纽,也就是说,应该有一半的数据项大于枢纽,一半的数据项小于枢纽,这会使数组被划分成两个大小相等子数组。可是如果没有选择好枢纽,那么快排的结果,就是划分为一大一小两个子数组进行排序,这样会降低算法的效率,因为较大的子数组要被划分更多次。

    极端情况是,逆序排列的数据,一个子数组只有一个数据项,另一个字数组含有N-1个数据项,而且对于N-1的分割,所有的子数组都是1 和X-1的结果,很明显,划分所带来的好处没有了,算法的效率降低到O(N²)

    快排以O(N²)运行的时候,除了慢还有另外一个潜在问题,当划分的次数增加,递归方法的调用也增加了,每一次调用都在申请工作栈,极端情况,可以能回内存溢出,导致程序挂掉。

    所以,选择一个恰当的枢纽值,是实现快速排序的重点。

    3. 三数取中法

    人们已经设计出很多更好的枢纽选择方法,方法都是为了避免枢纽选择最大或者最小的值。

    有一种这种的方法,我翻译为“三数取中法”(median-of-three) 如图:

    这里写图片描述
    三数取中法除了选择枢纽更为有效之外,还有一个额外的好处:可以在第二个内部while循环中取消rightPtr>left的测试,略微提高了算法的执行速度。

    你心里一定很疑惑,这是怎样实现的呢?

    因为在选择的过程中使用三数取中的方法不仅选择了枢纽,而且还对三个数据进行了排序,当三个数据项已经排好序,并且已经选择中值数据项作为枢纽后,此时就可以保证数组最左端的数据项小于等于枢纽,最右端的数据项大于等于枢纽,

    三数取中法的另一个好处就是,对左端,中间,以及右端的数据排序之后,划分过程就不再考虑这三个数据项了,划分可以从left+1和right-1开始,因为left和right已经被有效的划分了。

    不理解划分? 请倒回去看划分算法部分

    这样,三数取中的划分方法不但避免了 执行效率低至O(N²)的可能,而且也提高了划分算法内部循环的执行速度。

    完整的快速排序代码:

    class ArrayIns
    {
        private long[] theArray;
        private int nElems;
        //-------------------------------
        public ArrayIns(int max)
        {
        theArray=new ArrayIns(max);
        nElems=0;
        }
        //--------------------------------
        public void insert(long value)
        {
        theArray[nElesm]=value;
        nElems++;
        }
        //--------------------------------
        public void display()
        {
            System.out.print("A=");
            for(int j=0;j<nElems;j++)
            { 
                System.out.print(theArray[j]+" ");
                System.out.println("");
            }
        }
        //---------------------------------
        public void quickSort() //被main函数调用
        {
            recQuickSort(0,nElems-1);
        }
        //---------------------------------
        public void recQuickSort(int left,int right)
        {
            int size=right-left+1;
            if(size<=3)
                manulSort(left,right);  //如果数据项个数小,正常排序
            else   //数据项个数多,进行快速排序
            {
                long median=mediaOf3(left,right);    //三数取中
                int partition=partitionIt(left,right,median);
                recQuickSort(left,partition-1);   //划分
                recQuickSort(partion+1,right);   ///划分
            }
        }//end recQuicSort()
        //---------------------------------------
        public long medianOf3(int left,int right)
        {
            int center=(left+right)/2;
    
            if(theArray[left]>theArray[center])
                swap(left,center);
            if(theArray[left]>theArray[right])
                swap(left,right);
            if(theArray[center]>theArray[right])
                swap(center,right);
    
            swap(center,right-1);   //把枢纽值放在右边
            return theArray(right-1);   //返回中值
        }
        //----------------------------------------
        public void swap(int dex1,int dex2)
        {
            long temp;
            temp=theArray[dex1];
            theArray[dex1]=theArray[dex2];
            theArray[dex2]=temp;
        }
        //-----------------------------------------
        public int partitionIt(int left,int right,long pivot)
        {
            int leftPtr=left;
            int rightPtr=right-1; //枢纽左边的值
    
            while(true)
            {
                while(theArray[++leftPtr]<pivot)
                    ;//no
                while(theArray[--rightPtr]>pivot)
                    ;//no
    
                if(leftPtr>=rightPtr)
                    break;
                else
                    swap(leftPtr,rightPtr);
            }//end while
            swap(leftPtr,right-1);  //重新存储枢纽的值
            return leftPtr;
        }//end partitionIt()
        //------------------------------------------
        public void manualSort(inr left,int right)
        {
            int size=right-left+1;
            if(size<=1)  //不用排序
                return;
            if(size==2)
                {
                    if(theArray[left]>theArray[right])
                        swap(left,right);   
                    return
                }else   //size==3
                {
                    if(theArray[left]>theArray[right-1])
                        swap(left,right-1);
                    if(theArray[left]>theArray[right])
                        swap(left,right);
                    if(theArray[right-1]>theArray[right])
                        swap(right-1,right);
                }
        }//end manualSort()
    }//end class

    接着我们在main函数中执行

    class QuickSortApp
    {
        public static void main(String args)
        {
            int maxSize=16;
            ArrayIns arr;
            arr=new ArrayIns(maxSize);
            for(int j=0;j<maxSize;j++)
            {
            long n=(int)(Math.random()*99);
            arr.insert(n);
            }
    
            arr.display();
            arr.quickSort();
            arr.display
        }
    
    }

    用插入排序取代三数取中法

    如果使用三数取中法,则必须遵循快速排序中数据不能执行少于等于三个数据的规则,但这显然不是最好的划分方法。

    好在我们还有插入排序:

    处理小划分的另一个选择是使用插入排序,不用再去限制3,可以把界限定位10,20,或者任意数字。实验不同的枢纽点来提高执行效率。在这种算法下,最好的枢纽值取决于计算机,操作系统,编译器等,Knuth建议这种情况下的枢纽使用9。

    class ArrayIns
    {
        private long[] theArray;
        private int nElems;
        //-------------------------------
        public ArrayIns(int max)
        {
        theArray=new ArrayIns(max);
        nElems=0;
        }
        //--------------------------------
        public void insert(long value)
        {
        theArray[nElesm]=value;
        nElems++;
        }
        //--------------------------------
        public void display()
        {
            System.out.print("A=");
            for(int j=0;j<nElems;j++)
            { 
                System.out.print(theArray[j]+" ");
                System.out.println("");
            }
        }
        //---------------------------------
        public void quickSort() //被main函数调用
        {
            recQuickSort(0,nElems-1);
            //insertion(0,nElems-1);
        }
        //---------------------------------
        public void recQuickSort(int left,int right)
        {
            int size=right-left+1;
            if(size<=10)
                insertionSort(left,right);
            else   //数据项个数多,进行快速排序
            {
                long median=mediaOf3(left,right);    //三数取中
                int partition=partitionIt(left,right,median);
                recQuickSort(left,partition-1);   //划分
                recQuickSort(partion+1,right);   ///划分
            }
        }//end recQuicSort()
        //---------------------------------------
        public long medianOf3(int left,int right)
        {
            int center=(left+right)/2;
    
            if(theArray[left]>theArray[center])
                swap(left,center);
            if(theArray[left]>theArray[right])
                swap(left,right);
            if(theArray[center]>theArray[right])
                swap(center,right);
    
            swap(center,right-1);   //把枢纽值放在右边
            return theArray(right-1);   //返回中值
        }
        //----------------------------------------
        public void swap(int dex1,int dex2)
        {
            long temp;
            temp=theArray[dex1];
            theArray[dex1]=theArray[dex2];
            theArray[dex2]=temp;
        }
        //-----------------------------------------
        public int partitionIt(int left,int right,long pivot)
        {
            int leftPtr=left;
            int rightPtr=right-1; //枢纽左边的值
    
            while(true)
            {
                while(theArray[++leftPtr]<pivot)
                    ;//no
                while(theArray[--rightPtr]>pivot)
                    ;//no
    
                if(leftPtr>=rightPtr)
                    break;
                else
                    swap(leftPtr,rightPtr);
            }//end while
            swap(leftPtr,right-1);  //重新存储枢纽的值
            return leftPtr;
        }//end partitionIt()
        //------------------------------------------
        public void insertionSort(){
            int in,out;
            for(out=left+1;out<nElems;out++){ //外循环是分界线
                long temp=theArray[out];   //删除被标记的数据
                in = out ;   //srat shifts at  out
                while(in>0&&theArray[in-1]>=temp)
                {  //until one is smaller
                theArray[in] = a[in-1];  //shift item right,
                --in;   //go left one position
                }
                theArray[in] =temp;   //insert marked item
            }// end for
        }//end insertionSort()
    
    }//end class
    class Quick2SortApp
    {
        public static void main(String args)
        {
            int maxSize=16;
            ArrayIns arr;
            arr=new ArrayIns(maxSize);
            for(int j=0;j<maxSize;j++)
            {
            long n=(int)(Math.random()*99);
            arr.insert(n);
            }
    
            arr.display();
            arr.quickSort();
            arr.display
        }
    
    }

    这个特别的算法中,对小的子数组使用插入排序被证实为最快的方法,但不绝对比三数取中的枢纽法 快,总的来说没有明显的节省时间。

    很多专家还提倡使用:
    对数组整个使用快速排序,不考虑界限划分的排序。当快速排序结束时,数组基本有序,然后对整个数组进行插入排序,插入排序对基本有序的数组 执行效率高。

    代码有待勘察,改日补上

    快速排序的效率

    快速排序的时间复杂度为O(N*logN)

    参考并感谢

    1. 翻译 java数据结构和算法(英文版)

    2. 参考 java数据结构和算法( 中文版 )

    3. 了解递归

    展开全文
  • c语言五大排序算法

    2011-10-19 00:43:33
    选择排序算法: 算法基本原理: 一次选定数组中的每一个数,记下当前位置并假设它是从当前位置开始后面数中的最小数min=i,从这个数的下一个数开始扫描直到最后一个数,并记录下最小数的位置min,扫描结束后如果...
     
    

    一.选择排序算法:

    算法基本原理:
    一次选定数组中的每一个数,记下当前位置并假设它是从当前位置开始后面数中的最小数min=i,从这个数的下一个数开始扫描直到最后一个数,并记录下最小数的位置min,扫描结束后如果min不等于i,说明假设错误,否则交换min与i位置上数。

    算法实现:
    #include <stdio.h>
    //选择排序,如果第一个数字小于后面的则向后移动,依次类推
    该排序时不稳定的,时间复杂度是N平方
    void main()
    {
    int array[10] = {112,4,2,3,5,33,6,7,8,9};//定义一个数组
    int length = sizeof(array)/sizeof(array[0]);//得到数组的长度
    int k=0, s=0, i=0, j=0;//k保存临时结果,s,i,j为循环变量

    //选择排序开始
    for(i=0;i<length;i++)
    {
    for(j=i+1;j<length;j++)
    {
    if(array[i]>array[j])
    {
    k=array[i];
    array[i]=array[j];
    array[j]=k;
    }
    }
    }
    //选择排序结束,输出显示排序的结果
    for(s=0; s<length; s++)
    {
    printf("%d \n",array[s]);
    }
    }

     

    二.冒泡排序

    算法基本原理:

    对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序(与欲排顺序相反),若逆序就交换这两元素,经过第一轮比较排序后便可把最大(或最小)的元素排好,然后再用同样的方法把剩下的元素逐个进行比较,就得到了你所要的顺序。

    算法实现:
    #include <stdio.h>
    //冒泡排序,开始的时候两个数进行比较,大的向后小的向前,第一次比较很容易的就把最大的一个数字放到了最后小的呢,继续向前,第二次当然也找到了第二个大的,放到倒数第二的位置,如此下去便可。这个是优化的冒泡排序方法,让k=j保存最后的那个数的下标,这样k后面的数都是排序好的了,这个排序是稳定的,时间复杂度是N平方
    void main()
    {
    int array[10] = {1,2,11,22,33,4,23,234,4,6};
    int length = sizeof(array)/sizeof(array[0]);
    int k=0, s=0, i=0, j=0, m=0;
    //冒泡排序开始
    for(i = length-1;i>0;i=k)
    {
    for(j=0, k=0;j<i;j++)
    {
    if(array[j]>array[j+1])//把比较出来大的数据向后移动
    {
    m=array[j];
    array[j]=array[j+1];
    array[j+1]=m;
    k=j;
    }
    }
    }
    //冒泡排序结束,输出显示排序的结果
    for(s=0; s<length; s++)
    {
    printf("%d \n",array[s]);
    }
    }

    三.快速排序

    算法基本原理:

    快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    算法实现:

    #include <stdio.h>
    //快速排序开始,使用递归方法,取其中一个数(任意基本上都是以第一个为准),先从后面比较,如果这个数比后面的大交换之,如果不大继续比较直到大为止,如果大,则交换之,再到前面比较,如果前面的比这个数小交换之再和后面的比较,第一趟下来比它小的就在前面了,比它大的就在后面喽,然后再把该数组分成两部分使用递归,直到最后排序完成
    void paixu(int array[], int low, int hight)
    {
    int i,j,t,m;
    if(low<hight)
    {
    i = low;
    j = hight;
    t = array[low];
    while(i<j)
    {
    while(i<j && array[j]>t)//开始和后面的比较,如果后面的比他大继续,如果后面的比它小交换之
    {
    j--;
    }
    if(i<j)//在没有越界(i是从前面开始,j是从后面开始)的情况下进行交换
    {
    m=array[i];
    array[i]=array[j];
    array[j]=m;
    i++;//让前面的向后移动一个继续比较
    }
    while(i<j && array[i]<=t)//和前面的比较,如果前面的小于等于该关键数据继续,如果大于交换之
    {
    i++;
    }
    if(i<j)
    {
    m=array[j];
    array[j]=array[i];
    array[i]=m;
    j--;
    }
    }
    array[i]=t;//第一次比较结束,把i放到中间的位置,也即在i前面都比i小,在i后面都比i大
    paixu(array, low, i-1);//前面部分实现递归
    paixu(array, i+1, hight);//后面部分实现递归
    }
    }

    void main()
    {
    int s=0;
    int array[] = {10,22,3,21,45,67,2,11,110,453};
    int length = sizeof(array)/sizeof(array[0]);
    paixu(array,s,length-1);
    for(s=0;s<length;s++)
    {
    printf("%d \n",array[s]);
    }
    }

     

     

    四.插入排序

    概述:

    有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为⊙(㎡)。是稳定的排序方法。

      插入算法(insertion sort)把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外,而第二部分就只包含这一个元素。在第一部分排序后,再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。

    包括:直接插入排序,折半插入排序,链表插入排序,Shell排序

    算法基本原理:

    假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[1…k]是局部有序的,保证了插入过程的正确性.

    算法描述:

      一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

      1. 从第一个元素开始,该元素可以认为已经被排序

      2. 取出下一个元素,在已经排序的元素序列中从后向前扫描

      3. 如果该元素(已排序)大于新元素,将该元素移到下一位置

      4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

      5. 将新元素插入到该位置中

      6. 重复步骤2

      如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。

     

    算法实现:

    #include <stdio.h>
    void main()
    {
    int array[] = {9,43,567,1,45,23,123,54,234,987};
    int length = sizeof(array)/sizeof(array[0]);
    int i,j,t,m;
    //插入排序开始
    for(i=1;i<length;i++)//默认下标为0的已经是排序好的,所以从1开始
    {
    t = array[i];
    j=i;
    while((j>0)&&(array[j-1]>t))//如果前面的数比它大交换之
    {
    m=array[j-1];
    array[j-1]=array[j];
    array[j]=m;
    j--;//交换完毕继续比较
    }
    }
    //插入排序结束
    for(i=0;i<length;i++)
    {
    printf("%d \n",array[i]);
    }
    }

     

    五.希尔排序

    希尔排序是基于插入排序的一种算法,在此算法基础之上增加了一个新的特性,提高了效率。希尔排序的时间复杂度为 O(N*(logN)2), 没有快速排序算法快 O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是最优选择。但是比O(N2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏的情况下执行的效率会非常差。专家门提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快,再改成快速排序这样更高级的排序算法. 本质上讲,希尔排序算法的一种改进,减少了其复制的次数,速度要快很多。原因是,当N值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。当N值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。

     

    在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。
    ­
    下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,
    以后每次减半,直到增量为1。
    希尔排序是不稳定的。
     

    算法实现:

    #include <stdio.h>

    void main()
    {
    int array[] = {1,445,754,77,35,123,754,876,54,3};
    int length = sizeof(array)/sizeof(array[0]);

    int i,j,k,t,m;
    for(i=length/2;i>0;i=i/2)//控制增量
    {
    for(j=i;j<length;j++)//下面的就是直插排序
    {
    t = array[j];
    for(k=j-i;(k>=0 && t<array[k]);k=k-i)
    {
    m = array[k+i];
    array[k+i]=array[k];
    array[k]=m;
    }
    array[k+i]=t;
    }
    }

    for(i=0;i<length;i++)
    {
    printf("%d \n",array[i]);
    }
    }

    展开全文
  • 冒泡,选择,插入,Shell,快速排序算法与实例
  • 选择排序算法: 算法基本原理: 一次选定数组中的每一个数,记下当前位置并假设它是从当前位置开始后面数中的最小数min=i,从这个数的下一个数开始扫描直到最后一个数,并记录下最小数的位置min,扫描结束后如果...

    一.选择排序算法:

    算法基本原理:
    一次选定数组中的每一个数,记下当前位置并假设它是从当前位置开始后面数中的最小数min=i,从这个数的下一个数开始扫描直到最后一个数,并记录下最小数的位置min,扫描结束后如果min不等于i,说明假设错误,否则交换min与i位置上数。

    算法实现:
    #include <stdio.h>
    //选择排序,如果第一个数字小于后面的则向后移动,依次类推
    该排序时不稳定的,时间复杂度是N平方
    void main()
    {
    int array[10] = {112,4,2,3,5,33,6,7,8,9};//定义一个数组
    int length = sizeof(array)/sizeof(array[0]);//得到数组的长度
    int k=0, s=0, i=0, j=0;//k保存临时结果,s,i,j为循环变量

    //选择排序开始
    for(i=0;i<length;i++)
    {
    for(j=i+1;j<length;j++)
    {
    if(array[i]>array[j])
    {
    k=array[i];
    array[i]=array[j];
    array[j]=k;
    }
    }
    }
    //选择排序结束,输出显示排序的结果
    for(s=0; s<length; s++)
    {
    printf("%d \n",array[s]);
    }
    }

     

    二.冒泡排序

    算法基本原理:

    对尚未排序的各元素从头到尾依次比较相邻的两个元素是否逆序(与欲排顺序相反),若逆序就交换这两元素,经过第一轮比较排序后便可把最大(或最小)的元素排好,然后再用同样的方法把剩下的元素逐个进行比较,就得到了你所要的顺序。

    算法实现:
    #include <stdio.h>
    //冒泡排序,开始的时候两个数进行比较,大的向后小的向前,第一次比较很容易的就把最大的一个数字放到了最后小的呢,继续向前,第二次当然也找到了第二个大的,放到倒数第二的位置,如此下去便可。这个是优化的冒泡排序方法,让k=j保存最后的那个数的下标,这样k后面的数都是排序好的了,这个排序是稳定的,时间复杂度是N平方
    void main()
    {
    int array[10] = {1,2,11,22,33,4,23,234,4,6};
    int length = sizeof(array)/sizeof(array[0]);
    int k=0, s=0, i=0, j=0, m=0;
    //冒泡排序开始
    for(i = length-1;i>0;i=k)
    {
    for(j=0, k=0;j<i;j++)
    {
    if(array[j]>array[j+1])//把比较出来大的数据向后移动
    {
    m=array[j];
    array[j]=array[j+1];
    array[j+1]=m;
    k=j;
    }
    }
    }
    //冒泡排序结束,输出显示排序的结果
    for(s=0; s<length; s++)
    {
    printf("%d \n",array[s]);
    }
    }

    三.快速排序

    算法基本原理:

    快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    算法实现:

    #include <stdio.h>
    //快速排序开始,使用递归方法,取其中一个数(任意基本上都是以第一个为准),先从后面比较,如果这个数比后面的大交换之,如果不大继续比较直到大为止,如果大,则交换之,再到前面比较,如果前面的比这个数小交换之再和后面的比较,第一趟下来比它小的就在前面了,比它大的就在后面喽,然后再把该数组分成两部分使用递归,直到最后排序完成
    void paixu(int array[], int low, int hight)
    {
    int i,j,t,m;
    if(low<hight)
    {
    i = low;
    j = hight;
    t = array[low];
    while(i<j)
    {
    while(i<j && array[j]>t)//开始和后面的比较,如果后面的比他大继续,如果后面的比它小交换之
    {
    j--;
    }
    if(i<j)//在没有越界(i是从前面开始,j是从后面开始)的情况下进行交换
    {
    m=array[i];
    array[i]=array[j];
    array[j]=m;
    i++;//让前面的向后移动一个继续比较
    }
    while(i<j && array[i]<=t)//和前面的比较,如果前面的小于等于该关键数据继续,如果大于交换之
    {
    i++;
    }
    if(i<j)
    {
    m=array[j];
    array[j]=array[i];
    array[i]=m;
    j--;
    }
    }
    array[i]=t;//第一次比较结束,把i放到中间的位置,也即在i前面都比i小,在i后面都比i大
    paixu(array, low, i-1);//前面部分实现递归
    paixu(array, i+1, hight);//后面部分实现递归
    }
    }

    void main()
    {
    int s=0;
    int array[] = {10,22,3,21,45,67,2,11,110,453};
    int length = sizeof(array)/sizeof(array[0]);
    paixu(array,s,length-1);
    for(s=0;s<length;s++)
    {
    printf("%d \n",array[s]);
    }
    }

     

     

    四.插入排序

    概述:

    有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,但要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为⊙(㎡)。是稳定的排序方法。

      插入算法(insertion sort)把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外,而第二部分就只包含这一个元素。在第一部分排序后,再把这个最后元素插入到此刻已是有序的第一部分里的正确位置中。

    包括:直接插入排序,折半插入排序,链表插入排序,Shell排序

    算法基本原理:

    假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后,可以保证a[1…k]是局部有序的,保证了插入过程的正确性.

    算法描述:

      一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

      1. 从第一个元素开始,该元素可以认为已经被排序

      2. 取出下一个元素,在已经排序的元素序列中从后向前扫描

      3. 如果该元素(已排序)大于新元素,将该元素移到下一位置

      4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

      5. 将新元素插入到该位置中

      6. 重复步骤2

      如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。

     

    算法实现:

    #include <stdio.h>
    void main()
    {
    int array[] = {9,43,567,1,45,23,123,54,234,987};
    int length = sizeof(array)/sizeof(array[0]);
    int i,j,t,m;
    //插入排序开始
    for(i=1;i<length;i++)//默认下标为0的已经是排序好的,所以从1开始
    {
    t = array[i];
    j=i;
    while((j>0)&&(array[j-1]>t))//如果前面的数比它大交换之
    {
    m=array[j-1];
    array[j-1]=array[j];
    array[j]=m;
    j--;//交换完毕继续比较
    }
    }
    //插入排序结束
    for(i=0;i<length;i++)
    {
    printf("%d \n",array[i]);
    }
    }

     

    五.希尔排序

    希尔排序是基于插入排序的一种算法,在此算法基础之上增加了一个新的特性,提高了效率。希尔排序的时间复杂度为 O(N*(logN)2), 没有快速排序算法快 O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是最优选择。但是比O(N2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏的情况下执行的效率会非常差。专家门提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快,再改成快速排序这样更高级的排序算法. 本质上讲,希尔排序算法的一种改进,减少了其复制的次数,速度要快很多。原因是,当N值很大时数据项每一趟排序需要的个数很少,但数据项的距离很长。当N值减小时每一趟需要和动的数据增多,此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。

     

    在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。
    下面的函数是一个希尔排序算法的一个实现,初次取序列的一半为增量,
    以后每次减半,直到增量为1。
    希尔排序是不稳定的。
     

    算法实现:

    #include <stdio.h>

    void main()
    {
    int array[] = {1,445,754,77,35,123,754,876,54,3};
    int length = sizeof(array)/sizeof(array[0]);

    int i,j,k,t,m;
    for(i=length/2;i>0;i=i/2)//控制增量
    {
    for(j=i;j<length;j++)//下面的就是直插排序
    {
    t = array[j];
    for(k=j-i;(k>=0 && t<array[k]);k=k-i)
    {
    m = array[k+i];
    array[k+i]=array[k];
    array[k]=m;
    }
    array[k+i]=t;
    }
    }

    for(i=0;i<length;i++)
    {
    printf("%d \n",array[i]);
    }
    }

    展开全文
  • 大排序算法 一、直接插入 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 二、希尔排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 三、简单选择 - 1.基本思路 - 2.代码实现 - 3.时间复杂度...
    
    
    
    

    八大排序算法

    一、直接插入

    1.基本思路

    在要排序的一组数中,假设前面(n-1) [n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序。

    2.代码实现

    • 1.遍历数组,每次循环从第二个数字往前插入
    • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
    • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。
    public static void insertSort(int[] data) {
        int temp;
        for(int i = 1;i < data.length; i++){// 取第i个数,插入前边的有序的序列
            temp = data[i];
            int j;
            for(j = i - 1; j>=0; j--) {// 从第i-1的位置上开始比较
                if(data[j] > temp) {// 若前面的数大,则往后挪一位
                    data[j+1] = data[j];
                } else {
                    break;// 否则,说明要插入的数比较大
                }
            }
            data[j+1] = temp;// 找到这个位置,插入数据
        }
    }
    

    3.时间复杂度和空间复杂度

    直接插入排序的平均复杂度为O(n²),最坏时间复杂度:O(n²),空间复杂度:O(1),没有分配内存。

    二、希尔排序

    针对直接插入排序下的效率问题,有人对此进行了改进与升级,这就是现在的希尔排序。希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

    1.基本思路

    • 1.数的个数为length,i=length/2,将下标差值为i的数分为一组,构成有序序列。

    • 2.再取i=i/2 ,将下标差值为i的数分为一组,构成有序序列。

    • 3.重复第二步,直到k=1执行简单插入排序。

    思路:

    • 1.希尔排序(shell sort)这个排序方法又称为缩小增量排序,是1959年D·L·Shell提出来的。该方法的基本思想是:设待排序元素序列有n个元素,首先取一个整数increment(小于n)作为间隔将全部元素分为increment个子序列,所有距离为increment的元素放在同一个子序列中,在每一个子序列中分别实行直接插入排序。然后缩小间隔increment,重复上述子序列划分和排序工作。直到最后取increment=1,将所有元素放在同一个子序列中排序为止。
    • 2.由于开始时,increment的取值较大,每个子序列中的元素较少,排序速度较快,到排序后期increment取值逐渐变小,子序列中元素个数逐渐增多,但由于前面工作的基础,大多数元素已经基本有序,所以排序速度仍然很快。

    希尔排序举例:
    在这里插入图片描述

    2.代码实现

    • 1.遍历数组,每次循环从第二个数字往前插入
    • 2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
    • 3.从最后一个数开始向前循环,如果插入数小于当前数,就将当前数向后移动一位。

    (1)首先确定每一组序列的下标的间隔,循环每次需要的间隔:int i = length/2; i >0 ; i /= 2

    (2)然后将每一组序列中元素进行插入排序,第二组第一个插入的数字是第一组第一个插入数字之后的那个数组,从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列,不是一个一个子序列循环,而是在一个循环中for (int j=i;j<length;j++)完成所有子序列的插入排序。

    (3)直到i=0为止。

    public static void shellSort(int[] array) {
        int length = array.length;
        for (int i = length / 2; i > 0; i /= 2) {//序列的间隔,一直到间隔为一,这时候就只有一个子序列
            for (int j = i; j < length; j++) {//从i之后每个数字都要进行插入排序,就是插入的序列是各自不同的序列
                int temp = array[j];//里面就是直接插入算法
                int k;
                for (k = j - i; k >= 0; k -= i) {//实现各个数字插入排序到不同的序列中,直到间隔为1的时候,只有一个序列,就是完全的一个直接插入排序
                    if (temp < array[k]) {
                        array[k + i] = array[k];
                    } else {
                        break;
                    }
                }
                array[k + i] = temp;//把数字插入到位置上
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    希尔排序的平均时间复杂度为O(n²),空间复杂度O(1) 。

    三、简单选择

    1.基本思路

    基本原理如下:对于给定的一组记录,经过第一轮比较后得到最小的记录,然后将该记录的位置与第一个记录的位置交换;接着对不包括第一个记录以外的其他记录进行第二次比较,得到最小记录并与第二个位置记录交换;重复该过程,直到进行比较的记录只剩下一个为止。

    2.代码实现

    • 1.确定要插入最小值的位置,从0开始到最后int i = 0; i <len ; i++
    • 2.将每次开始位置上的数字暂定为最小值min,从开始数字之后一个个和min比较,再把最小值存放到min
    • 3.将最小值所在位置上的数字和开始位置上的数字交换
    public static void selectSort(int[] array) {
        int len = array.length;
        for (int i = 0; i < len; i++) {//确定每次开始的位置
            int min = array[i];//设定开始数字为最小的值最小值
            int flag = i;
            for (int j = i + 1; j < len; j++) {//把最小值存放到min,从开始数字向后一个个和min比较,再把最小值存放到min
                if (min > array[j]) {
                    min = array[j];
                    flag = j;
                }
            }
            if (flag != i) {
                array[flag] = array[i];
                array[i] = min;
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    简单选择排序的时间复杂度为O(n²)

    四、堆排序

    1.基本思路

    • 1.若array[0,…,n-1]表示一颗完全二叉树的顺序存储模式,则双亲节点指针和孩子结点指针之间的内在关系如下:
    任意一节点指针 i:
    父节点:i==0 ? null : (i-1)/2
    左孩子:2*i + 1
    右孩子:2*i + 2
    
    • 2.堆得定义
    n个关键字序列array[0,...,n-1],当且仅当满足下列要求:(0 <= i <= (n-1)/2)
    ① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]; 称为小根堆;
    ② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]; 称为大根堆;
    
    • 3.建立大顶堆

    n个节点的完全二叉树array[0,…,n-1],最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整,使该子树称为堆。

    对于大根堆,调整方法为:若【根节点的关键字】小于【左右子女中关键字较大者】,则交换。

    之后向前依次对各节点((n-2)/2 - 1)~ 0为根的子树进行调整,看该节点值是否大于其左右子节点的值,若不是,将左右子节点中较大值与之交换,交换后可能会破坏下一级堆,于是继续采用上述方法构建下一级的堆,直到以该节点为根的子树构成堆为止。

    反复利用上述调整堆的方法建堆,直到根节点。

    • 4.堆排序(大顶堆)
    ①将存放在array[0,...,n-1]中的n个元素建成初始堆;
    ②将堆顶元素与堆底元素进行交换,则序列的最大值即已放到正确的位置;
    ③将数组中array[0,...,n-1]前n-1个元素再次形成大根堆,再重复第②③步,直到堆中仅剩下一个元素为止。
    

    2.代码实现

    
    /**
        *  大顶堆排序
        * @param array
        */
    public static void maxHeapSort(int[] array) {
        int i;
        int len = array.length;
        // 构建大顶堆
        for (i = len / 2 - 1; i >= 0; i--) {
            adjustMaxHeap(array, i, len);
        }
        // 堆顶是最大值,交换堆顶和最后一个数,再重新调整最大堆,下一次循环   i--
        for (i = len - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            adjustMaxHeap(array, 0, i);
        }
        System.out.println(Arrays.toString(array));
    }
    
    private static void adjustMaxHeap(int[] a, int pos, int len) {
        int temp;
        int child;
        for (temp = a[pos]; 2 * pos + 1 < len; pos = child) {
            // 数组从0开始,r(i)>=r(2i) r(i)>=r(2i+1)  对应 pos => 2 * pos + 1 和 2 * pos +2
            child = 2 * pos + 1;
            // 有右孩子,且右孩子数值更大
            if (child + 1 < len && a[child] < a[child + 1]) {
                child++;
            }
            // 最大的孩子大于根节点
            if (a[child] > temp) {
                a[pos] = a[child];
            } else {
                break;
            }
        }
        a[pos] = temp;
    }
    

    3.时间复杂度和空间复杂度

    时间复杂度:建堆:o(n),每次调整o(log n),故最好、最坏、平均情况下:o(n*logn);

    五、冒泡排序

    1.基本思路

    一次冒泡将序列中从头到尾所有元素两两比较,将最大的放在最后面。

    将剩余序列中所有元素再次两两比较,将最大的放在最后面。

    重复第二步,直到只剩下一个数。

    2.代码实现

    /**
     * @author fupeng
     * 冒泡排序优化第二版
     * 第一版优化增加flag标记,没有数字交换直接return,最优时间复杂度O(n)
     * 第二版优化,增加tempPostion记录内循环最后一次交换的位置,来缩减内循环的次数
     */
    public static void bubbleSort(int[] array) {
        int len = array.length - 1;
        // 开辟一个临时空间, 存放交换的中间值
        int temp;
        // 记录最后一次交换的位置
        int tempPostion = 0;
        // 要遍历的次数
        for (int i = 0; i < array.length - 1; i++) {
            int flag = 1; // 设置一个标志位
            // 依次比较相邻两个数的大小,遍历一次后,会将前面没有排好序的最大值放到后面位置
            for (int j = 0; j < len; j++) {
                // 比较相邻的元素,如果前面的数大于后面的数,交换
                if (array[j] > array[j + 1]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    // 发生交换,标志位置0
                    flag = 0;
                    // 记录交换的位置
                    tempPostion = j;
                }
            }
            // 把最后一次交换的位置给len,来缩减内循环的次数
            len = tempPostion;
            // 如果没有交换过元素,则已经有序
            if (flag == 1) {
                System.out.println(Arrays.toString(array));
                return;
            }
        }
        System.out.println(Arrays.toString(array));
    }
    

    3.时间复杂度和空间复杂度

    冒泡排序的最好时间复杂度为O(n),最坏时间复杂度为O(n²),平均时间复杂度为O(n²),空间复杂度为O(1),它是一种稳定的排序算法。

    六、快速排序

    1.基本思路

    快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

    • 1.从数列中挑出一个元素,称为"基准"(pivot)。
    • 2.重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
    • 3.递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    2.代码实现

    public static void quickSort(int[] array) {
        sort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
    
    private static void sort(int[] a, int low, int high) {
        int i = low;
        int j = high;
        if (a.length <= 1) {
            return;
        }
        if (i >= j) {
            return;
        }
        int index = a[i];
        while (i < j) {
            while (i < j && a[j] >= index)
                j--;
            if (a[j] < index)
                a[i++] = a[j];
            while (i < j && a[i] <= index)
                i++;
            if (a[i] > index)
                a[j--] = a[i];
        }
        a[i] = index;
        sort(a, low, i - 1);
        sort(a, i + 1, high);
    }
    

    3.时间复杂度和空间复杂度

    虽然 快排的时间复杂度达到了 O(n²),但是在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。

    七、归并排序

    1.基本思路

    归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

    • 1.分而治之
      在这里插入图片描述

    可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

    • 2.合并相邻有序子序列
      再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

    在这里插入图片描述
    在这里插入图片描述

    2.代码实现

    public static void mergeSort(int[] array) {
        int[] temp = new int[array.length];// 在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
        mergeSort(array, 0, array.length-1, temp);
        System.out.println(Arrays.toString(array));
    }
    
    private static void mergeSort(int[] arr, int left, int right, int []temp) {
        if(left < right) {
            int mid = (left+right) / 2;
            mergeSort(arr, left, mid, temp);// 左边归并排序,使得左子序列有序
            mergeSort(arr, mid+1, right, temp);// 右边归并排序,使得右子序列有序
            merge(arr, left, mid, right, temp);// 将两个有序子数组合并操作
        }
    }
    
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;// 左序列指针
        int j = mid+1;// 右序列指针
        int t = 0;// 临时数组指针
        while (i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while(i <= mid) {// 将左边剩余元素填充进temp中
            temp[t++] = arr[i++];
        }
        while(j <= right) {// 将右序列剩余元素填充进temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        // 将temp中的元素全部拷贝到原数组中
        while(left <= right) {
            arr[left++] = temp[t++];
        }
    }
    

    3.时间复杂度和空间复杂度

    归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

    八、基数排序

    1.基本思路

    • 1.基数排序的思想就是先排好各位,然后排好各位的基础上排十位,以此类推,直到遍历最高位 次,排序结束(仔细理解最后一句话)
    • 2.基数排序不是比较排序,而是通过分配和收集的过程来实现排序
    • 3.初始化10个桶(固定的),桶下标为0-9
    • 4.通过得到待排序数字的个十百等位的数字,把这个数字对应的item放到对应的桶中
    • 5.基数排序有两种排序方式:LSD和MSD,最小位优先(从右边开始)和最大位优先(从左边开始)

    在这里插入图片描述

    2.代码实现

    public static void radixSort(int[] array) {
        ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
        for (int i = 0; i <10 ; i++) {
            queue.add(new ArrayList<>());// 创建一个基数从0---9 每个数字上都是一个list
        }
        // 找到最大值,并判断最大值是几位数
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
        }
        int time = 0;
        while (max > 0) {
            max /= 10;
            time++;
        }
        for (int i = 0; i < time; i++) {// 循环每一个位数(个位、十位、百位)
            for (int j = 0; j < array.length; j++) {// 循环数组,取每一个值
                int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
                ArrayList<Integer> queue3 = queue.get(x);
    
                queue3.add(array[j]);
                queue.set(x, queue3);
            }
            int count = 0;
            for (int k = 0; k < 10; k++) {
                while (queue.get(k).size() > 0) {
                    ArrayList<Integer> queue4 = queue.get(k);
                    array[count] = queue4.get(0);
                    queue4.remove(0);
                    count++;
                }
            }
        }
    }
    

    3.时间复杂度和空间复杂度

    归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

    总结

    在这里插入图片描述

    引用:

    https://www.cnblogs.com/mensan/p/10570050.html

    https://www.cnblogs.com/jyroy/p/11248691.html

    https://www.cnblogs.com/chengxiao/p/6194356.html

    https://www.jianshu.com/p/8340dfaea3af

    展开全文
  • 算法学习总结(2)——温故十大经典排序算法

    万次阅读 多人点赞 2019-08-29 14:57:51
    一、什么是排序算法 1.1、排序定义 对一序列对象根据某个关键字进行排序。 1.2、排序术语 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b...
  • 大排序算法之()冒泡排序

    万次阅读 2017-10-15 16:55:22
    冒泡排序算法原理:比较相邻的元素。如果第一个比第二个,就交换他们两个。对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。针对所有的元素重复以上的步骤,...
  • 目录排序的概念十大内部排序算法算法的五大特征冒泡排序练习 排序的概念 十大内部排序算法 算法的五大特征 冒泡排序 练习 public class ArrayExer2 { public static void main(String[] args) { int[] arr =...
  • 大排序算法总结

    万次阅读 多人点赞 2015-02-15 13:35:47
    大排序算法实现 插入排序算法实现 希尔排序算法实现 选择排序算法实现 冒泡排序算法实现 归并排序算法实现 快速排序算法实现 堆排序算法实现 基数排序算法实现
  • 排序算法

    千次阅读 2018-11-18 12:47:39
    版权声明:本文为博主原创文章,未经博主允许不得转载。 ... 排序方法 插入排序 直接插入排序 希尔排序 交换排序 冒泡排序 快速排序 选择排序 简...
  • 选择排序算法: 算法基本原理: 一次选定数组中的每一个数,记下当前位置并假设它是从当前位置开始后面数中的最小数min=i,从这个数的下一个数开始扫描直到最后一个数,并记录下最小数的位置min,扫描结束后如果...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 190,284
精华内容 76,113
关键字:

五大排序算法