精华内容
下载资源
问答
  • 《数据结构》-第八章 排序(习题)
    千次阅读
    2021-08-28 22:20:18

    第八章 排序

          排序作为各类数据结构的相应的运算的一种,在很多领域中都有广泛的应用。主要的排序方法有插入排序、交换排序、选择排序、二路归并排序、基数排序、外部排序等各类排序方法。堆排序、快速排序和归并排序是本章的重难点,应深入掌握各种排序算法的思想、排序过程(能动手模拟)和特征(初态的影响、复杂度、稳定性、适用性等)。

         本章同样作为考察重点章节,通常以选择题的形式考查不同算法之间的对比。此外,对于一些常用排序算法的关键代码,要达到熟练编写的程度:看到某特定序列,读者应具有选择最优排序算法的能力。

    一、选择题

    1. 从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法,称为( )。

        A.归并排序         B.冒泡排序            C.插入排序             D.选择排序

       【答案】D。

    2. 快速排序在下列( )情况下最易发挥其长处。

        A.被排序的数据中含有多个相同排序码        B.被排序的数据已基本有序

        C.被排序的数据完全无序                            D.被排序的数据中的最大值和最小值相差悬殊

       【答案】C 。B 选项是快速排序的最坏情况。

     3. 堆是一种( )排序。

        A.插入            B.选择                C.交换                 D.归并

        【答案】B。 

    4. 下述几种排序方法中,要求内存最大的是( )。

        A.希尔排序            B.快速排序             C.归并排序            D.堆排序

       【答案】C 。堆排序、希尔排序的空间复杂度为 O(1) ,快速排序的空间复杂度为 O(log 2n),归并排序的空间复杂度为 O(n) 。

    5. 数据表中有 10000 个元素,如果仅要求求出其中最大的 10 个元素,则采用 ( )算法最节省时间。

        A.冒泡排序            B.快速排序            C.简单选择排序             D.堆排序

       【答案】D。

    6. 下列排序算法中,( )不能保证每趟排序至少能将一个元素放到其最终的位置上。

        A.希尔排序             B.快速排序            C.冒泡排序               D.堆排序

      【答案】A。快速排序的每趟排序能将作为枢轴的元素放到最终位置;冒泡排序的每趟排序能将最大或最小的元素放到最终位置;堆排序的每趟排序能将最大或最小的元素放到最终位置。

    7. 对任意7个关键字进行基于比较的排序,至少要进行(  )次关键字之间的两两比较。

        A.13                B. 14               C.15                D. 6

      【答案】A。对于任意序列进行基于比较的排序,求最少的比较次数应考虑最坏情况。对任意n个关键字排序的比较次数至少为「log2(n!)]。将n=7代入公式,答案为13。

    8. 在下列算法中,( ) 算法可能出现下列情况:在最后一趟开始之前,所有元素都不在最终位置上。

        A.堆排序             B.冒泡排序            C.直接插入排序            D. 快速排序

      【答案】C。在直接插入排序中,若待排序列中的最后一个元素应插入表中的第一个位置, 则前面的有序子序列中的所有元素都不在最终位置上。

    9.用希尔排序方法对一个数据序列进行排序时,若第1趟排序结果为9, 1,4,13, 7,8, 20,23, 15,则该趟排序采用的增量(间隔)可能是( )。

        A.2                B.3                C.4                D. 5

    【答案】B。首先,第二个元素为1,是整个序列中的最小元素,因此可知该希尔排序为从小到大排序。然后考虑增量问题,若增量为2,则第1 +2个元素4明显比第1个元素9要小,A排除;若增量为3,则第,i+3,i+6 (i=1, 2, 3)个元素都为有序序列,符合希尔排序的定义:若增量为4,则第1个元素9比第1+4个元素7要大,C排除:若增量为S,则第1个元素9比第1+5个元素8要大,D排除,选B.

    10. 折半插入排序算法的时间复杂度为(  )。

        A. O (n)               B. O(nlog2n)                C. O (n2)                D. O(n3)

    【答案】C。虽然折半插入排序是对直接插入排序的改进,但它改进的只是比较的次数,而移动次数未发生变化,时间复杂度仍为O(n2)。

    11. 用某种排序方法对线性表{25, 84, 21, 47, 15, 27, 68, 35, 20}进行排序时,元素序列的变化情况如下:1) 25, 84,21, 47, 15, 27, 68, 35, 20

           2) 20, 15, 21,25, 47,27, 68,35, 84

           3) 15, 20,21,25, 35, 27, 47, 68, 84

           4) 15, 20,21, 25, 27,35, 47, 68, 84,则所采用的排序方法是( )。

        A.选择排序                B.插入排序                C.2路归并排序                D.快速排序

    【答案】D。选择排序在每趟结束后可以确定一个元素的最终位置, 不对。插入排序,第i趟后前i+ 1个元素应该是有序的,不对。第2趟{20, 15}和{21, 25}是反序的,因此不是归并排序。快速排序每趟都将基准元素放在其最终位置,然后以它为基准将序列划分为两个子序列。观察题中的排序过程,可知是快速排序。

    12. 快速排序算法在(   )情况下最不利于发挥其长处。

        A.要排序的数据量太大                   B.要排序的数据中含有多个相同值

        C.要排序的数据个数为奇数            D.要排序的数据已基本有序

    【答案】D。当待排序数据为基本有序时,每次选取第n个元素为基准,会导致划分区间分配不均匀,不利于发挥快速排序算法的优势。相反,当待排序数据分布较为随机时,基准元素能将序列划分为两个长度大致相等的序列,这时才能发挥快速排序的优势。

    13. 数据序列F= {2,1,4,9, 8, 10, 6, 20}只能是下列排序算法中的( ) 两趟排序后的结果。

        A.快速排序            B.冒泡排序            C.选择排序            D.插入排序.

    【答案】A。若为插入排序,则前三个元素应该是有序的,显然不对。而冒泡排序和选择排序经过两趟排序后应该有两个元素处于最终位置(最左/右端),无论是按从小到大还是从大到小排序,数据序列中都没有两个满足这样的条件的元素,因此只可能选A。

    14. 对下列关键字序列用快排进行排序时,速度最快的情形是( ), 速度最慢的情形是( ).

        A. {21, 25,5, 17, 9, 23, 30}                 B. {25, 23, 30, 17,21,5,9}

        C. {21,9, 17, 30, 25, 23, 5}                 D. {5,9, 17,21, 23, 25, 30}

    【答案】A、D。由考点精析可知,当每次的枢轴都把表等分为长度相近的两个子表时,速度是最快的;当表本身已经有序或逆序时,速度最慢。选项D中的序列已按关键字排好序,因此它是最慢的,而A中第一趟枢轴值21将表划分为两个子表{9, 17, 5}和{25, 23, 30},而后对两个子表划分时,枢轴值再次将它们等分,所以该序列是快速排序最优的情况,速度最快。其他选项可以类似分析。

    15. 下列序列中,( )可能是执行第一趟快速排序后所得到的序列。

        I. {68, 11,18, 69, 23, 93, 73}                    II. {68, 11, 69, 23, 18, 93, 73}

        II,{93, 73, 68, 11, 69, 23, 18}                IV. {68, 11, 69, 23, 18, 73, 93}

        A.I、IV                    B.Il、III                       C.III、IV                    D.只有IV

    【答案】C。显然,若按从小到大排序,则最终有序的序列是{11, 18, 23, 68, 69, 73, 93};若按从大到小排序,则最终有序的序列是{93, 73, 69, 68, 23, 18, 11}。对比可知1、I中没有处于最终位置的元素,故I、II都不可能。III 中73和93处于从大到小排序后的最终位置,而且73将序列分割成大于73和小于73的两部分,故m是有可能的。IV中73和93处于从小到大排列后的最终位置,73也将序列分割成大于73和小于73的两部分。

    16.下列选项中,不可能是快速排序第2趟排序结果的是(  )。

        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

    【答案】C。快排的阶段性排序结果的特点是,第i趟完成时,会有i个以上的数出现在它最终将要出现的位置,即它左边的数都比它小,它右边的数都比它大。题目问第二趟排序的结果,即要找不存在两个这样的数的选项。A选项中2,3, 6, 7, 9均符合,所以A排除; B选项中,2,9 均符合,所以B排除; D选项中5, 9均符合,所以D排除;最后看C选项,只有9一个数符合,所以C不可能是快速排序第二趟的结果。

    17. 对n个关键字进行快速排序,最大递归深度为( ), 最小递归深度为( )。

        A. 1                        B. n                    C. log2n                    D. nlog2n

    【答案】B、C。快速排序过程构成一个递归树,递归深度即递归树的高度。枢轴值每次都将子表等分时,递归树的高为log2n;枢轴值每次都是子表的最大值或最小值时,递归树退化为单链表,树高为n。

    18. 排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中,不可能是快速排序第二趟结果的是( )。

        A.5,2, 16, 12, 28, 60, 32, 72                B.2, 16.5, 28, 12, 60, 32, 72

        C.2, 12, 16, 5, 28,32, 72, 60                D.5,2, 12, 28, 16, 32, 72, 60

    【答案】D。要理解清楚排序过程中一“趟”的含义,题干也进行了解释_--对 尚未确定最终位置的所有元素都处理一遍才是一趟,所以此时要对前后两块子表各做一次快速排序才是一 “趟”快速排序,如果只对一块子表进行了 排序,而未处理另-块子表,就不能算是完整的一趟。选项A,第一趟匹配72,只余一块无序序列,第二趟匹配28,A可能。选项B,第一趟匹配2,第二趟匹配72, B可能。选项C,第一趟匹配2,第二趟匹配28或32, C可能。选项D,无论是先匹配12还是先匹配32,都会将序列分成两块,那么第二趟必须有两个元素匹配,所以D不可能,故选D.

    19. 简单选择排序算法的比较次数和移动次数分别为( )。

        A. O (n), O(log2n)                    B. O(log2n), O (n2)

        C. O (n2), O(n)                        D. O(nlog2n), O(n)

    【答案】C。

    20.设线性表中每个元素有两个数据项k和k2,现对线性表按以下规则进行排序:先看数据项k, k值小的元素在前,大的元素在后;在k值相同的情况下,再看k,kz值小的在前,大的元案在后,满足这种要求的排序方法是()。

        A.先按k1进行直接插入排序,再按k2进行简单选择排序 

        B.先按k2进行直接插入排序,再按k1进行简单选择排序

        C.先按k1进行简单选择排序,再按k2进行直接插入排序

        D.先按k2进行简单选择排序,再按k1进行直接插入排序

      【答案】D。首先应确定k1、k2的排序顺序,若先排k1再排k2,则排序结果不符合题意,排除选项A、C。再考虑算法的稳定性,当k2排好序后,再对k1排序,若对k1排序采用的算法是不稳定的,则对于k1相同而k2不同的元素可能会改变相对次序,从而不一定能满足题干中的条件“在k1值相同的情况下,k2值小的元素在前,大的元素在后”。直接插入排序算法是稳定的,而简单选择排序算法是不稳定的,故只能选D。

    21. 向具有n个结点的堆中插入一个新元素的时间复杂度为( ), 删除一个元素的时间复杂度为( )。

        A. O (1)               B. O(n)                C. O (log2n)                D. O(nlog2n)

      【答案】C、C。在向有n个元案的堆中插入一个新元素时,需要调用一个向上调整的算法,比较次数最多等于树的高度减1,由于树的高度为Llog2nJ+ 1,所以堆的向.上调整算法的比较次数最多等于Llog2nJ。此处需要注意,调整堆和建初始堆的时间复杂度是不一样的。

    22. 构建n个记录的初始堆,其时间复杂度为( ); 对n个记录进行堆排序,最坏情况下其时间复杂度为( )。

        A. O(n)                B. O (n2)                C. O(log2n)                D. O(nlog2n)

      【答案】A、D。建堆过程中,向下调整的时间与树高h有关,为O(h).每次向下调整时,大部分结点的高度都较小。因此,可以证明在元素个数为n的序列上建堆,其时间复杂度为0(n)。无论是在最好情况下还是在最坏情况下,堆排序的时间复杂度均为o(nlog2n)o。

    23.巳知小根堆为8, 15, 10, 21,34, 16, 12,删除关键字8之后需重建堆,在此过程中,关键字之间的比较次数是( )。

        A.1                    B.2                        C.3                   D.4

      【答案】C。删除8后,将12移动到堆项,第一次是15和10比较,第二次是10和12比较并交换,第三次还需比较12和16,故比较次数为3。

    24. 以下排序算法中,( )不需要进行关键字的比较。

        A.快速排序            B.归并排序            C.基数排序            D.堆排序

      【答案】C。基数排序是基于关键字各位的大小进行排序的,而不是基于关键字的比较进行的。

    25. 在下列排序算法中,平均情况下空间复杂度为O(n)的是(    ); 最坏情况下空间复杂度为O(n)的是(    )。

        I.希尔排序        I.堆排序        II.冒泡排序        IV.归并排序        V.快速排序        VI.基数排序

        A. I、IV、VI             B. II、V            C. IV、V                D. IV

      【答案】D、C。归并排序算法在平均情况下和最坏情况下的空间复杂度都会达到O(n),快速排序只在最坏情况下才会达到O(n),平均情况下为O(log2n)。所以归并排序算法可视为本章所有算法中占用辅助空间最多的排序算法。

    26. 2路归并排序中,归并趟数的数量级是( ).

        A. O(n)             B. O (log2n)            C. O(nlogzn)            D. O (n2)

      【答案】B。对N个元素进行k路归并排序时,排序的趟数m满足k"=N,所以m = ⌈ logN ⌉,本题中即为⌈ log2n ⌉.

    27. 将两个各有N个元素的有序表合并成一个有序表,最少的比较次数是(      ), 最多的比较次数是(      )。

        A. N                B.2N-1                C.2N                D.N-1

      【答案】A、B。注意到当一个表中的最小元素比另一个表中的最大元素还大时,比较的次数是最少的,仅比较N次;而当两个表中的元素依次间隔地比较时,即a1<b1<a2<b2<...<an<bn 时,比较的次数是最多的,为2N-1次。

    28. 对{05 46, 13, 55, 94, 17, 42}进行基数排序,一趟排序的结果是(   )。

        A.05, 46, 13, 55, 94, 17, 42                 B.05, 13, 17, 42, 46, 55, 94

        C.42, 13, 94, 05, 55, 46, 17                 D. 05, 13, 46, 55, 17, 42, 94

      【答案】C。比较各数的个位数,按各数的个位数进行排序,可知选C。

    29. 排序趟数与序列的原始状态无关的排序方法是( )。

        I. 直接插入排序        II.简单选择排序        II.冒泡排序        IV.基数排序

        A.I、III                     B. I、II、IV              C. I、II、III            D. I、IV

     【答案】B。交换类的排序,其趟数和原始序列状态有关,故冒泡排序与初始序列有关。直接插入排序:每趟排序都插入一个元素,所以排序趟数固定为n-1;简单选择排序:每趟排序都选出一个最小(或最大)的元素,所以排序趟数固定为n-1;基数排序:每趟排序都要进行“分配”和“收集”,排序趟数固定为d。

    30. 置换-选择排序的作用是( )。

        A.用于生成外部排序的初始归并段

        B.完成将一个磁盘文件排序成有序文件的有效的外部排序算法

        C.生成的初始归并段的长度是内存工作区的2倍

        D.对外部排序中输入/归并/输出的并行处理

      【答案】A。置换选择排序是外部排序中生成初始归并段的方法,用此方法得到的初始归并段的长度是不;等长的,其长度平均是传统等长初始归并段的2倍,从而使得初始归并段数减少到原来的近二分之一。但是,置换选择排序不是一-种 完整的生成有序文件的外部排序算法。

    31. 在下列关于外部排序过程输入/输出缓冲区作用的叙述中,不正确的是( )。

        A.暂存输入/输出记录                     B.内部归并的工作区

        C.产生初始归并段的工作区            D.传送用户界面的消息

      【答案】D。在外部排序过程中输入/输出缓冲区就是排序的内存工作区,例如做m路平衡归并需要m个输入缓冲区和1个输出缓冲区,用以存放参加归并的和归并完成的记录。在产生初始归并段时也可用作内部排序的工作区。它没有传送用户界面的消息的任务。

    32. 在做m路平衡归并排序的过程中,为实现输入内部归并/输出的并行处理,需要设置( ① )个输入缓冲区和( ② )个输出缓冲区。

        ①A.2              B. m              C. 2m- 1               D.2m

        ②A.2              B. m              C.2m- 1                D.2m

      【答案】D、A。在做m路平衡归并排序的过程中,为实现输入/内部归并/输出的并行处理,需要设置2m个输入缓冲区和2个输出缓冲区,以便在执行内部归并时,能同时进行输入/输出操作。若仅设置m个输入缓冲区,则仅能进行串行操作,无法并行处理。

    二、填空题

    1. 设 T 为一棵平衡树,在其中插入一个结点 n,然后立即删除该结点后得到 T1,则 T 与 T1 必定相同。( )

      【答案】×。平衡树在插入结点后,如果平衡被破坏,则需进行调整,在进行删除结点后,T与T1则不相同。

    2. 在9阶B-树中,除叶子以外的任意结点的分指数介于5和9之间。( )

      【答案】×。未指出根至少有两个结点。

    3. B-树的插入算法中,通过结点的向上“分裂”,代替了专门的平衡调整。( )

      【答案】√。多路平衡树就是这样。

    4. 堆肯定是一棵平衡二叉树。( )

      【答案】×。堆是二叉树。而平衡二叉树要求左右子树遵循左小右大的规律,而堆不能保证该规律。

    5. 在执行某个排序算法过程中,出现了排序码朝着最终排序序列位置相反方向移动,则该算法是不稳定的。( )

      【答案】×。相同关键字的位置。

    三、综合应用题

    1. 设待排序的关键字序列为 {12 , 2, 16 , 30 , 28, 10, 16* , 20 , 6, 18} ,试分别写

    出使用以下排序方法,每趟排序结束后关键字序列的状态。

        ① 直接插入排序        ② 折半插入排序        ③ 希尔排序(增量选取 5, 3, 1) 

        ④ 冒泡排序               ⑤ 快速排序               ⑥ 简单选择排序

        ⑦ 二路归并排序

      【答案】①直接插入排序,过程如下:

                        [2 12] 16 30 28 10 16* 20 6 18  

                        [2 12 16] 30 28 10 16* 20 6 18

                        [2 12 16 30] 28 10 16* 20 6 18

                        [2 12 16 28 30] 10 16* 20 6 18

                        [2 10 12 16 28 30] 16* 20 6 18

                        [2 10 12 16 16* 28 30] 20 6 18

                        [2 10 12 16 16* 20 28 30] 6 18

                        [2 6 10 12 16 16* 20 28 30] 18

                        [2 6 10 12 16 16* 18 20 28 30]

        ② 折半插入排序 排序过程同①;

        ③ 希尔排序(增量选取 5, 3, 1),过程如下:

                        10 2 16 6 18 12 16* 20 30 28 (增量选取 5)

                        6 2 12 10 18 16 16* 20 30 28 (增量选取 3)

                        2 6 10 12 16 16* 18 20 28 30 (增量选取 1) 

        ④ 冒泡排序,过程如下:

                        2 12 16 28 10 16* 20 6 18 [30]

                        2 12 16 10 16* 20 6 18 [28 30]

                        2 12 10 16 16* 6 18 [20 28 30]

                        2 10 12 16 6 16* [18 20 28 30]

                        2 10 12 6 16 [16* 18 20 28 30]

                        2 10 6 12 [16 16* 18 20 28 30]

                        2 6 10 [12 16 16* 18 20 28 30]

                        2 6 10 12 16 16* 18 20 28 30]

        ⑤ 快速排序,过程如下:

                       12 [6 2 10] 12 [28 30 16* 20 16 18]

                       6 [2] 6 [10] 12 [28 30 16* 20 16 18 ]

                       28 2 6 10 12 [18 16 16* 20 ] 28 [30 ]

                       18 2 6 10 12 [16* 16] 18 [20] 28 30

                       16* 2 6 10 12 16* [16] 18 20 28 30  

                       左子序列递归深度为 1,右子序列递归深度为 3

        ⑥ 简单选择排序,过程如下:

                       2 [12 16 30 28 10 16* 20 6 18]

                       2 6 [16 30 28 10 16* 20 12 18]

                       2 6 10 [30 28 16 16* 20 12 18]

                       2 6 10 12 [28 16 16* 20 30 18]

                       2 6 10 12 16 [28 16* 20 30 18]

                       2 6 10 12 16 16* [28 20 30 18]

                       2 6 10 12 16 16* 18 [20 30 28]

                       2 6 10 12 16 16* 18 20 [28 30]

                       2 6 10 12 16 16* 18 20 28 [30]

       ⑦二路归并排序,过程如下:

                       2 12 16 30 10 28 16 * 20 6 18

                       2 12 16 30 10 16* 20 28 6 18

                       2 10 12 16 16* 20 28 30 6 18

                       2 6 10 12 16 16* 18 20 28 30

    2. 给出如下关键字序列{ 321 , 156 , 57 , 46 , 28 , 7, 331 , 33, 34 , 63},试按链式基数排序方法,列出每一趟分配和收集的过程。

    【答案】

        按最低位优先法 → 321 → 156 → 57 → 46→ 28 → 7→ 331→ 33 → 34→ 63

        分配 [0]      [1]      [2]      [3]      [4]      [5]      [6]      [7]      [8]      [9]

                        321               33       34               156      57      28

                        331               63                           46        7

        收集 → 321→ 331 → 33 → 63→ 34→ 156→ 46 → 57→ 7→ 28

    3. 对输入文件( 101 , 51 , 19, 61 , 3, 71 , 31, 17, 19 , 100, 55 , 20,9, 30 , 50 ,6, 90 );当 k=6 时,使用置换 - 选择算法,写出建立的初始败者树及生成的初始归并段。

    【答案】初始败者树,如图所示:

        初始归并段: R1:  3,19,31,51,61,71,100,101

                             R2:  9,17,19,20,30,50,55,90

                             R3 :  6

    4. 给出关键字序列{50, 26, 38, 80, 70, 90, 8, 30, 40, 20}的希尔排序过程(取增量序列为d= {5,3, 1}, 排序结果为从小到大排列)。

      【答案】原始序列:50, 26, 38, 80, 70, 90, 8, 30, 40, 20

            第一趟(增量5): 50, 8, 30, 40, 20, 90, 26, 38, 80, 70

            第二趟(增量3): 26, 8, 30, 40, 20, 80, 50, 38, 90, 70

            第三趟(增量1): 8, 20, 26, 30, 38, 40, 50, 70, 80, 90

    四、算法题

    1. 试以单链表为存储结构,实现简单选择排序算法。

    2. 有 n 个记录存储在带头结点的双向链表中, 现用双向冒泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。

    3. 编写算法,对 n 个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录排在关键字为非负值的记录之前,要求:

        ① 采用顺序存储结构,至多使用一个记录的辅助存储空间;

        ② 算法的时间复杂度为 O(n) 。

    【注】所有题目的代码不唯一,如需参考答案可私信。

    更多相关内容
  • 【SPSS03】排序题分析

    2021-05-23 19:57:54
    排序题分析排序题背景说明数据说明 &...在每个运动员只有4名裁判给出得分的情况下,很难有足够的证据说明每个运动员的得分变量服从正态分布(而小样本情形下检验变量正态性的K-S法,也需要变量的样本量至少达到5分)

    排序题背景说明

    数据说明 & 分析目的

    在这里插入图片描述
    如图,数据为7个运动员获得4个裁判的评分
    分析目的:运动员之间的水平是否有差异

    使用分析方法的原因阐述

    由于单方差因素分析法,除了因变量必须为计量资料以外,还要求变量必须服从正态分布。
    在每个运动员只有4名裁判给出得分的情况下,很难有足够的证据说明每个运动员的得分变量服从正态分布(而小样本情形下检验变量正态性的K-S法,也需要变量的样本量至少达到5分)
    对于数值有实际意义的,使用Friedman方法进行检验

    Friedman检验

    原假设:k个相关的变量来自同一个总体。
    分析步骤:
    在这里插入图片描述

    检验结果

    在这里插入图片描述
    p值为0.004,拒绝原假设,认为运动员之间的得分有差异。

    展开全文
  • 问卷排序题应该怎样分析?

    千次阅读 2020-07-27 12:24:00
    排序题的特殊格式,让很多人犯了,究竟怎么分析排序题才好? 今天就和大家分享下如何分析排序题。 01.排序题录入 (1)如何手动录入 在分析之前首先要确保数据录入格式正确,排序题录入方法与多选题相似...

    在一般的问卷调研中,除了常见的单选题、多选题,还有一类题型受到问卷设计者的偏爱。

    这就是排序题,排序题不仅可以直观展现答题者对每个选项的态度,还能按照应答频次与重要程度对选项进行排名。

    但设计问卷一时爽,事后分析火葬场。排序题的特殊格式,让很多人犯了难,究竟怎么分析排序题才好?

    今天就和大家分享下如何分析排序题。

     

     

    01.排序题录入

    (1)如何手动录入

    在分析之前首先要确保数据录入格式正确,排序题录入方法与多选题相似。

     

    例:(排序题)“请对大学生综合素质指标重要程度做出排序”

     

    A.学习成绩   B.所获荣誉  C.交际能力   D.外形相貌

    E.卫生习惯   F.礼貌修养  G.表达能力  H.实践创新能力

    根据重要程度从高到低排序(最多选四项)_________________________

     

     

    案例中共有8个选项,最多选择4项。第一列ID代表样本编号。

    2~9列为排序题备选项,有几个选项就需要录入几列。

    按照排序的顺序填写,比如第一个人认为学习成绩最重要,就计为1;交际能力第二重要,计为2,以此类推。没有选中的选项,计为0。

     

    (2)数据导入

    如果数据是从问卷星导入到SPSSAU,每个选项会独立显示成一个标题,有几个选项就有几行标题。

     

     

     

    问卷星的格式会把所有没有被选中的选项设置为“-2”,因此在分析前需要先处理这些异常值,才能保证分析结果的准确性。

     

    02.数据处理

    数据导入后,首先对数据进行异常值处理,即检查数据中是否有异常值。

     

    处理方法:SPSSAU数据处理>异常值功能

     

     

    Shift+左键:全选中题项,勾选“缺失数字”、“数字<0”,设置异常值处理项为Null,确定处理。

     

     

    03.排序题分析

    排序题分析时,一般可以从两方面说明:一是对被调查的人选择哪些选项以及各项的选择比例情况进行描述,二是根据排序结果给出重要性排名

     

    (1)频数分析

    通过频数分析可以看到每一选项的具体选择情况,分析时可罗列出各项选择结果,重点描述选择人数较多项。

     

     

    (2)重要性排名

     

    频数分析中,虽然了解到各选项的选择情况,但还无法确定各因素的重要性排名,因此还需要进一步分析。

     

    ①权重赋值

    由于选择顺序不同,其重要程度也不一样。所以在分析时,需要给每个数值赋值一个加权数,即排名第一位的数值权重>第二位权重>第三位权重>第四位权重。

     

    最常规的赋值方法为,对数据进行反向计分:例如共选四项排名,排第一位计4分,排第二位计3分,排第三位计2分,排第四位计1分。

     

    处理方法: SPSSAU数据处理>数据编码功能

     

    选中所有备选项,设置分数,确认编码。

     

    (建议选择不覆盖原数据)

     

     

    设置成功后,可以看到新生成的数据,简单将题目修改标准,设置好变量标签。

     

    ②描述分析

    处理完编码后,可使用描述分析查看数据的综合得分,即平均值得分。

     

     

    所得的平均值可代表题项被选中的顺序,平均值越大,该指标的排序就越靠前,按数值大小进行排列,得到最终的排名顺序。

     

     

     

    总结

    (1)排序题一般很少作为核心题项进行研究,虽然排序题可能包含更多信息,但可使用的分析方法较少,因而建议避免大量使用。

     

    (2)权重确定的方法不只一个,除了上面提到的赋值权重的方法,常见的权重计算方法还有AHP层次分析法、优序图法等,这些方法在SPSSAU中也可直接使用(问卷研究>权重),建议使用前阅读相关帮助手册进行了解。登录SPSSAU官网了解更多内容。

    展开全文
  • 这样说起来可能很难理解,于是给出一张我画的图。 这里显示了归并排序的第一步,将数组按照middle进行递归拆分,最后分到最细之后再将其使用对两个有序数组进行排序的方法对其进行排序。 两个有序数组排序的方法则...
  • 思考了一会发现也不是很难,假如数组是正序排列的,可以同时遍历2个数组,将小的值进行排序,最后会遍历完一个数组,留下一个非空数组,而且剩下的值肯定大于等于已经排好序的最大值. PHP代码: <?php function sort_...
  • 十大排序算法

    万次阅读 多人点赞 2021-08-20 13:37:46
    冒泡排序 从数组头开始,比较相邻的元素。如果第一个比第二个大(小),就交换它们两个 对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数 重复步骤1~2,重复次数...

    推荐几个动画演示的网站:

    冒泡排序

    1. 从数组头开始,比较相邻的元素。如果第一个比第二个大(小),就交换它们两个
    2. 对每一对相邻元素作同样的工作,从开始第一对到尾部的最后一对,这样在最后的元素应该会是最大(小)的数
    3. 重复步骤1~2,重复次数等于数组的长度,直到排序完成

    image-20210728113340011

    代码实现

    对下面数组实现排序:{24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9}

    代码实现

    public class BubbleSort {
    
        public static final int[] ARRAY = {24, 7, 43, 78, 62, 98, 82, 18, 54, 37, 73, 9};
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    
        public static int[] sort(int[] array) {
            if (array.length == 0) {
                return array;
            }
            for (int i = 0; i < array.length; i++) {
                //array.length - 1 -i 已经冒泡到合适位置无需在进行排序,减少比较次数
                for (int j = 0; j < array.length - 1 -i; j++) {
                    //前面的数大于后面的数交换
                    if (array[j + 1] < array[j]) {
                        int temp = array[j + 1];
                        array[j + 1] = array[j];
                        array[j] = temp;
                    }
                }
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    }
    

    时间复杂度

    对于上面12个数据项,从第一个元素开始,第一趟比较了11次,第二趟比较了10次,依次类推,一直到最后一趟,就是:

    11 + 10 + 9 + 8 + 7 + 6 + 5  + 4 + 3  + 2 + 1  =  66次
    

    若有n个元素,则第一趟比较为(n-1)次,第二趟比较为(n-2)次,依次类推:

    (n-1) + (n-2) + (n-3) + ...+ 2 + 1 = n * (n-1)/2
    

    在大O表示法中,去掉常数系数和低阶项,该排序方式的时间复杂度为:O(n2)

    算法稳定性

    假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。——百度百科

    在代码中可以看到,array[j + 1] = array[j]的时候,我们可以不移动array[i]array[j],所以冒泡排序是稳定的

    选择排序

    1. 找到数组中最大(或最小)的元素
    2. 将它和数组的第一个元素交换位置(如果第一个元素就是最大(小)元素那么它就和自己交换)
    3. 在剩下的元素中找到最大(小)的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。

    image-20210728144443166

    代码实现

    对下面数组实现排序:{87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9}

    动图演示

    选择排序

    代码实现

    public class SelectionSort {
    
        public static final int[] ARRAY = {87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9};
    
        public static int[] sort(int[] array) {
            if (array.length == 0) {
                return array;
            }
            for (int i = 0; i < array.length; i++) {
                //最小数的下标,每个循环开始总是假设第一个数最小
                int minIndex = i;
                for (int j = i; j < array.length; j++) {
                    //找到最小索引
                    if (array[j] < array[minIndex]) {
                        //保存最小索引
                        minIndex = j;
                    }
                }
                //最小索引的值
                int temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    很明显,和冒泡排序相比,在查找最小(或最大)元素的索引,比较次数仍然保持为O(n2)

    ,但元素交换次数为O(n)

    算法稳定性

    选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果一个元素比当前元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。举个例子,数组5,8,5,2,9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中两个5的相对前后顺序就被破坏了,所以选择排序是一个不稳定的排序算法

    image-20210728144637093

    插入排序

    当我们在玩扑克牌的时候,总是在牌堆里面抽取最顶部的一张然后按顺序在手中排列。

    插入排序是指在待排序的元素中,假设前面n-1(其中n>=2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。

    1. 对于未排序数据(一般取数组的二个元素,把第一个元素当做有序数组),在已排序序列中从左往右扫描,找到相应位置并插入。
    2. 为了给要插入的元素腾出空间,需要将插入位置之后的已排序元素在都向后移动一位。

    image-20210728162127494

    代码实现

    对下面数组实现排序:{15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}

    动图演示

    插入排序

    代码实现

    public class InsertionSort {
    
        public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1};
    
        public static int[] sort(int[] array) {
            if (array.length == 0) {
                return array;
            }
            //待排序数据,改数据之前的已被排序
            int current;
            for (int i = 0; i < array.length - 1; i++) {
                //已被排序数据的索引
                int index = i;
                current = array[index + 1];
                //将当前元素后移一位
                while (index >= 0 && current < array[index]) {
                    array[index + 1] = array[index];
                    index--;
                }
                //插入
                array[index + 1] = current;
            }
            return array;
        }
    
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    在上面图示中,第一趟循环比较一次,第二趟循环两次,依次类推,则最后一趟比较n-1次:

    1 + 2 + 3 +… + n-1 = n*(n-1)/2
    

    也就是说,在最坏的情况下(逆序),比较的时间复杂度为O(n2)

    在最优的情况下,即while循坏总是假的,只需当前数跟前一个数比较一下就可以了,这时一共需要比较n-1次,时间复杂度为O(n)

    算法稳定性

    在比较的时候,过两个数相等的话,不会进行移动,前后两个数的次序不会发生改变,所以插入排序是稳定的

    希尔排序

    一种基于插入排序的快速的排序算法。简单插入排序对于大规模乱序数组很慢,因为元素只能一点一点地从数组的一端移动到另一端。例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要n-1次移动。

    希尔排序为了加快速度简单地改进了插入排序,也称为缩小增量排序。

    希尔排序是把待排序数组按一定的数量分组,对每组使用直接插入排序算法排序;然后缩小数量继续分组排序,随着数量逐渐减少,每组包含的元素越来越多,当数量减至 1 时,整个数组恰被分成一组,排序便完成了。这个不断缩小的数量,就构成了一个增量序列,这里的数量称为增量。

    image-20210729135834646

    代码实现

    public class ShellSort {
    
        public static final int[] ARRAY = {12, 9, 6, 11, 5, 1, 14, 2, 10, 4, 8, 7, 13, 3};
    
        public static int[] sort(int[] array) {
            int len = array.length;
            if (len < 2) {
                return array;
            }
            //当前待排序数据,该数据之前的已被排序
            int current;
            //增量
            int gap = len / 2;
            while (gap > 0) {
                for (int i = gap; i < len; i++) {
                    current = array[i];
                    //前面有序序列的索引
                    int index = i - gap;
                    while (index >= 0 && current < array[index]) {
                        array[index + gap] = array[index];
                        //有序序列的下一个
                        index -= gap;
                    }
                    //插入
                    array[index + gap] = current;
                }
                //int相除取整
                gap = gap / 2;
            }
            return array;
        }
    
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    希尔排序的复杂度和增量序列有关。

    在先前较大的增量下每个子序列的规模都不大,用直接插入排序效率都较高,尽管在随后的增量递减分组中子序列越来越大,由于整个序列的有序性也越来越明显,则排序效率依然较高。

    从理论上说,只要一个数组是递减的,并且最后一个值是1,都可以作为增量序列使用。有没有一个步长序列,使得排序过程中所需的比较和移动次数相对较少,并且无论待排序列记录数有多少,算法的时间复杂度都能渐近最佳呢?但是目前从数学上来说,无法证明某个序列是最好的。

    常用的增量序列:

    • 希尔增量序列 :{n/2, (n / 2)/2, …, 1},其中N为原始数组的长度,这是最常用的序列,但却不是最好的
    • Hibbard序列:{2k-1, …, 3,1}
    • Sedgewick序列:{… , 109 , 41 , 19 , 5,1} 表达式为9 * 4i- 9 * 2i + 1,i = 0,1,2,3,4…

    算法稳定性

    由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,如数组5,2,2,1,第一次排序第一个元素5会和第三个元素2交换,第二个元素2会和第四个元素1交换,原序列中两个2的相对前后顺序就被破坏了,所以希尔排序是一个不稳定的排序算法

    image-20210729165300142

    归并排序

    归并,指合并,合在一起。归并排序(Merge Sort)是建立在归并操作上的一种排序算法。其主要思想是分而治之。什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总。即“分”就是把一个大的通过递归成若干个小的,“治”就是将分后的结果在在一起。

    若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并。

    image-20210730115340519

    怎么分

    • 对于排序最好的情况来讲,就是只有两个元素,这时候比较大小就很简单,但是还是需要比较
    • 如果拆分为左右各一个,无需比较即是有序的。

    怎么治

    借助一个辅助空数组,把左右两边的数组按照大小比较,按顺序放入辅助数组中即可。

    以下面两个有序数组为例:

    归并排序

    代码实现

    public class MergeSort {
        public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
    
        public static int[] sort(int[] array) {
            if (array.length < 2) return array;
            int mid = array.length / 2;
            //分成2组
            int[] left = Arrays.copyOfRange(array, 0, mid);
            int[] right = Arrays.copyOfRange(array, mid, array.length);
            //递归拆分
            return merge(sort(left), sort(right));
        }
    
        //治---合并
        public static int[] merge(int[] left, int[] right) {
            int[] result = new int[left.length + right.length];
            //i代表左边数组的索引,j代表右边
            for (int index = 0, i = 0, j = 0; index < result.length; index++) {
                if (i >= left.length) {//说明左侧的数据已经全部取完,取右边的数据
                    result[index] = right[j++];
                } else if (j >= right.length) {//说明右侧的数据已经全部取完,取左边的数据
                    result[index] = left[i++];
                } else if (left[i] > right[j]) {//左边大于右边,取右边的
                    int a = right[j++];
                    result[index] = a;
                } else {//右边大于左边,取左边的
                    result[index] = left[i++];
                }
            }
            return result;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    归并排序方法就是把一组n个数的序列,折半分为两个序列,然后再将这两个序列再分,一直分下去,直到分为n个长度为1的序列。然后两两按大小归并。如此反复,直到最后形成包含n个数的一个数组。

    归并排序总时间 = 分解时间 + 子序列排好序时间 + 合并时间
    

    无论每个序列有多少数都是折中分解,所以分解时间是个常数,可以忽略不计,则:

    归并排序总时间 = 子序列排好序时间 + 合并时间
    

    假设处理的数据规模大小为 n,运行时间设为:T(n),则T(n) = n,当 n = 1时,T(1) = 1

    由于在合并时,两个子序列已经排好序,所以在合并的时候只需要 if 判断即可,所以n个数比较,合并的时间复杂度为 n。

    • 将 n 个数的序列,分为两个 n/2 的序列,则:T(n) = 2T(n/2) + n
    • 将 n/2 个数的序列,分为四个 n/4 的序列,则:T(n) = 4T(n/4) + 2n
    • 将 n/4 个数的序列,分为八个 n/8 的序列,则:T(n) = 8T(n/8) + 3n
    • 将 n/2k 个数的序列,分为2k个 n/2k 的序列,则:T(n) = 2kT(n/2k) + kn

    当 T(n/2k) = T(1)时, 即n/2k = 1(此时也是把n分解到只有1个数据的时候),转换为以2为底n的对数:k = log2n,把k带入到T(n)中,得:T(n) = n + nlog2n

    使用大O表示法,去掉常数项 n,省略底数 2,则归并排序的时间复杂度为:O(nlogn)

    算法稳定性

    从原理分析和代码可以看出,为在合并的时候,如果相等,选择前面的元素到辅助数组,所以归并排序是稳定的。

    快速排序

    快速排序是对冒泡排序的一种改进,也是采用分治法的一个典型的应用。JDK中Arrays的sort()方法,具体的排序细节就是使用快速排序实现的。

    从数组中任意选取一个数据(比如数组的第一个数或最后一个数)作为关键数据,我们称为基准数(pivot,或中轴数),然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,也称为分区(partition)操作。

    问题

    若给定一个无序数组 [8, 5, 6, 4, 3, 1, 7, 2],并指定一个数为基准,拆分数组使得左侧的数都小于等于它 ,右侧的数都大于它。

    基准的选取最优的情况是基准值刚好取在无序区数值的中位数,这样能够最大效率地让两边排序,同时最大地减少递归划分的次数,但是一般很难做到最优。基准的选取一般有三种方式:

    • 选取数组的第一个元素
    • 选取数组的最后一个元素
    • 以及选取第一个、最后一个以及中间的元素的中位数(如4 5 6 7, 第一个4, 最后一个7, 中间的为5, 这三个数的中位数为5, 所以选择5作为基准)。

    思路

    1. 随机选择数组的一个元素,比如 6 为基准,拆分数组同时引入一个初始指针,也叫分区指示器,初始指针指向 -1
    2. 将数组中的元素和基准数遍历比较
    3. 若当前元素大于基准数,不做任何变化
    4. 若当前元素小于等于基准数时,分割指示器右移一位,同时
      • 当前元素下标小于等于分区指示器时,当前元素保持不动
      • 当前元素下标大于分区指示器时,当前元素和分区指示器所指元素交换

    快速排序

    荷兰国旗问题

    荷兰的国旗是由红白蓝三种颜色构成,如图:

    若现在给一个随机的图形,如下:

    image-20210803151023780

    把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,这类问题称作荷兰国旗问题。

    对应leetcode:颜色分类

    给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
    

    分析:

    假如给定一个数组[8, 3, 6, 2, 5, 1, 7, 5],做如下操作:

    1. 随机选择数组的一个元素,比如 5 为基准,拆分数组同时引入一个左分区指示器,指向 -1,右分区指示器指向基准数(注:此时的基准数为尾元素)

    2. 若当前元素大于基准数,右分区指示器左移一位,当前元素和右分区指示器所指元素交换,

      索引保持不变

    3. 若当前元素小于等于基准数时,左分区指示器右移一位,索引右移

      • 当前元素大于等于左分区指示器所指元素,当前元素保持不动
      • 当前元素小于左分区指示器所指元素,交换

    简单来说就是,左分区指示器向右移动的过程中,如果遇到大于或等于基准数时,则停止移动,右分区指示器向左移动的过程中,如果遇到小于或等于主元的元素则停止移动。这种操作也叫双向快速排序

    345345

    代码实现

    public class QuickSort {
    
        public static final int[] ARRAY = {8, 5, 6, 4, 3, 1, 7, 2};
    
        public static final int[] ARRAY2 = {8, 3, 6, 2, 5, 1, 7, 5};
    
        private static int[] sort(int[] array, int left, int right) {
            if (array.length < 1 || left > right) return null;
            //拆分
            int partitionIndex = partition(array, left, right);
            //递归
            if (partitionIndex > left) {
                sort(array, left, partitionIndex - 1);
            }
            if (partitionIndex < right) {
                sort(array, partitionIndex + 1, right);
            }
            return array;
        }
    
        /**
         * 分区快排操作
         *
         * @param array 原数组
         * @param left  左侧头索引
         * @param right 右侧尾索引
         * @return 分区指示器  最后指向基准数
         */
        public static int partition(int[] array, int left, int right) {
            //基准数下标---随机方式取值,也就是数组的长度随机1-8之间
            int pivot = (int) (left + Math.random() * (right - left + 1));
            //分区指示器索引
            int partitionIndex = left - 1;
            //基准数和尾部元素交换
            swap(array, pivot, right);
            //按照规定,如果当前元素大于基准数不做任何操作;
            //小于基准数,分区指示器右移,且当前元素的索引大于分区指示器,交换
            for (int i = left; i <= right; i++) {
                if (array[i] <= array[right]) {//当前元素小于等于基准数
                    partitionIndex++;
                    if (i > partitionIndex) {//当前元素的索引大于分区指示器
                        //交换
                        swap(array, i, partitionIndex);
                    }
                }
            }
            return partitionIndex;
        }
    
        /**
         * 双向扫描排序
         */
        public static int partitionTwoWay(int[] array, int left, int right) {
            //基准数
            int pivot = array[right];
            //左分区指示器索引
            int leftIndex = left - 1;
            //右分区指示器索引
            int rightIndex = right;
            //索引
            int index = left;
            while (index < rightIndex) {
                //若当前元素大于基准数,右分区指示器左移一位,当前元素和右分区指示器所指元素交换,索引保持不变
                if (array[index] > pivot) {
                    swap(array, index, --rightIndex);
                } else if (array[index] <= pivot) {//当前元素小于等于基准数时,左分割指示器右移一位,索引右移
                    leftIndex++;
                    index++;
                    //当前元素小于等于左分区指示器所指元素,交换
                    if (array[index] < array[leftIndex]) {
                        swap(array, index, leftIndex);
                    }
                }
            }
            //索引和 L 指向同一个元素
            swap(array, right, rightIndex);
            return 1;
        }
    
        //交换
        private static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY, 0, ARRAY.length - 1));
            System.out.println("====================双向排序==================");
            print(ARRAY2);
            System.out.println("============================================");
            print(sort(ARRAY2, 0, ARRAY2.length - 1));
        }
    }
    

    时间复杂度

    在拆分数组的时候可能会出现一种极端的情况,每次拆分的时候,基准数左边的元素个数都为0,而右边都为n-1个。这个时候,就需要拆分n次了。而每次拆分整理的时间复杂度为O(n),所以最坏的时间复杂度为O(n2)。什么意思?举个简单例子:

    在不知道初始序列已经有序的情况下进行排序,第1趟排序经过n-1次比较后,将第1个元素仍然定在原来的位置上,并得到一个长度为n-1的子序列;第2趟排序经过n-2次比较后,将第2个元素确定在它原来的位置上,又得到一个长度为n-2的子序列;以此类推,最终总的比较次数:

    C(n) = (n-1) + (n-2) + … + 1 = n(n-1)/2

    所以最坏的情况下,快速排序的时间复杂度为O(n^2)

    而最好的情况就是每次拆分都能够从数组的中间拆分,这样拆分logn次就行了,此时的时间复杂度为O(nlogn)。

    而平均时间复杂度,则是假设每次基准数随机,最后算出来的时间复杂度为O(nlogn)

    参考:快速排序的时间复杂度与空间复杂度

    算法稳定性

    通过上面的分析可以知道,在随机取基准数的时候,数据是可能会发生变化的,所以快速排序有不是稳定的情况。

    堆排序

    这里的堆并不是JVM中堆栈的堆,而是一种特殊的二叉树,通常也叫作二叉堆。它具有以下特点:

    • 它是完全二叉树
    • 堆中某个结点的值总是不大于或不小于其父结点的值

    知识补充

    二叉树

    树中节点的子节点不超过2的有序树

    image-20210804135913978

    满二叉树

    二叉树中除了叶子节点,每个节点的子节点都为2,则此二叉树为满二叉树。

    image-20210804140132004

    完全二叉树

    如果对满二叉树的结点进行编号,约定编号从根结点起,自上而下,自左而右。则深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。

    特点叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。需要注意的是,满二叉树肯定是完全二叉树,而完全二叉树不一定是满二叉树。

    image-20210804144904950

    二叉堆

    二叉堆是一种特殊的堆,可以被看做一棵完全二叉树的数组对象,而根据其性质又可以分为下面两种:

    • 大根堆:每一个根节点都大于等于它的左右孩子节点,也叫最大堆
    • 小根堆:每一个根节点都小于等于它的左右孩子节点,也叫最小堆

    如果把一个数组通过大根堆的方式来表示(数组元素的值是可变的),如下:

    image-20210804180209118

    由此可以推出:

    • 对于位置为 k 的节点,其子节点的位置分别为,左子节点 = 2k + 1右子节点 = 2(k + 1)

      如:对于 k = 1,其节点的对应数组为 5

      左子节点的位置为 3,对应数组的值为 3

      右子节点的位置为 4,对应数组的值为 2

    • 最后一个非叶子节点的位置为 (n/2) - 1,n为数组长度

      如:数组长度为6,则 (6/2) - 1 = 2,即位置 2 为最后一个非叶子节点

    给定一个随机数组[35,63,48,9,86,24,53,11],将该数组视为一个完全二叉树:

    image-20210804190655494

    从上图很明显的可以看出,这个二叉树不符合大根堆的定义,但是可以通过调整,使它变为最大堆。如果从最后一个非叶子节点开始,从下到上,从右往左调整,则:

    image-20210804224254053

    通过上面的调整,该二叉树为最大堆,这个时候开始排序,排序规则:

    • 将堆顶元素和尾元素交换
    • 交换后重新调整元素的位置,使之重新变成二叉堆

    image-20210804234843626

    代码实现

    public class HeapSort {
    
        public static final int[] ARRAY = {35, 63, 48, 9, 86, 24, 53, 11};
    
        public static int[] sort(int[] array) {
            //数组的长度
            int length = array.length;
            if (length < 2) return array;
            //首先构建一个最大堆
            buildMaxHeap(array);
            //调整为最大堆之后,顶元素为最大元素并与微元素交换
            while (length > 0) {//当lenth <= 0时,说明已经到堆顶
                //交换
                swap(array, 0, length - 1);
                length--;//交换之后相当于把树中的最大值弹出去了,所以要--
                //交换之后从上往下调整使之成为最大堆
                adjustHeap(array, 0, length);
            }
            return array;
        }
    
        //对元素组构建为一个对应数组的最大堆
        private static void buildMaxHeap(int[] array) {
            //在之前的分析可知,最大堆的构建是从最后一个非叶子节点开始,从下往上,从右往左调整
            //最后一个非叶子节点的位置为:array.length/2 - 1
            for (int i = array.length / 2 - 1; i >= 0; i--) {
                //调整使之成为最大堆
                adjustHeap(array, i, array.length);
            }
        }
    
        /**
         * 调整
         * @param parent 最后一个非叶子节点
         * @param length 数组的长度
         */
        private static void adjustHeap(int[] array, int parent, int length) {
            //定义最大值的索引
            int maxIndex = parent;
            //parent为对应元素的位置(数组的索引)
            int left = 2 * parent + 1;//左子节点对应元素的位置
            int right = 2 * (parent + 1);//右子节点对应元素的位置
            //判断是否有子节点,再比较父节点和左右子节点的大小
            //因为parent最后一个非叶子节点,所以如果有左右子节点则节点的位置都小于数组的长度
            if (left < length && array[left] > array[maxIndex]) {//左子节点如果比父节点大
                maxIndex = left;
            }
            if (right < length && array[right] > array[maxIndex]) {//右子节点如果比父节点大
                maxIndex = right;
            }
            //maxIndex为父节点,若发生改变则说明不是最大节点,需要交换
            if (maxIndex != parent) {
                swap(array, maxIndex, parent);
                //交换之后递归再次调整比较
                adjustHeap(array, maxIndex, length);
            }
        }
    
        //交换
        private static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    堆的时间复杂度是 O(nlogn)

    参考:堆排序的时间复杂度分析

    算法稳定性

    堆的结构为,对于位置为 k 的节点,其子节点的位置分别为,左子节点 = 2k + 1右子节点 = 2(k + 1),最大堆要求父节点大于等于其2个子节点,最小堆要求父节点小于等于其2个子节点。

    在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(最大堆)或者最小(最大堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1,n/2-2,… 1 这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

    参考:排序的稳定性

    思考

    对于快速排序来说,其平均复杂度为O(nlogn),堆排序也是O(nlogn),怎么选择?如下题:

    leetcode:数组中的第K个最大元素

    此题的意思是对于一个无序数组,经过排序后的第 k 个最大的元素。

    我们知道快速排序是需要对整个数组进行排序,这样才能取出第 k 个最大的元素。

    如果使用堆排序,且是最大堆的方式,则第k次循环即可找出第 k 个最大的元素,并不需要吧整个数组排序。

    所以对于怎么选择的问题,要看具体的场景,或者是两者都可。

    计数排序

    一种非比较排序。计数排序对一定范围内的整数排序时候的速度非常快,一般快于其他排序算法。但计数排序局限性比较大,只限于对整数进行排序,而且待排序元素值分布较连续、跨度小的情况。

    如果一个数组里所有元素都是整数,而且都在0-k以内。对于数组里每个元素来说,如果能知道数组里有多少项小于或等于该元素,就能准确地给出该元素在排序后的数组的位置。

    如给定一个0~5范围内的数组[2,5,3,0,2,3,0,3],对于元素5为其中最大的元素,创建一个大小为(5-0+1 = 6)的计数数组,如果原数组中的值对应计数数组的下标,则下标对应计数数组的值加1。

    image-20210806112939098

    问题

    上面是通过数组的最大值来确定计数数组的长度的,但如果需要对学生的成绩进行排序,如学生成绩为:[95,93,92,94,92,93,95,90],如果按照上面的方法来处理,则需要一个大小为100的数组,但是可以看到其中的最小值为90,那也就是说前面 0~89 的位置都没有数据存放,造成了资源浪费。

    如果我们知道了数组的最大值和最小值,则计数数组的大小为(最大值 - 最小值 + 1),如上面数组的最大值为99,最小值为90,则定义计数数组的大小为(95 - 90 + 1 = 6)。并且索引分别对应原数组9095的值。我们把090的范围用一个偏移量来表示,即最小值90就是这个偏移量。

    image-20210806121018728

    代码实现

    public class CountSort {
    
        public static final int[] ARRAY = {2, 5, 3, 0, 2, 3, 0, 3};
        public static final int[] ARRAY2 = {95,93,92,94,92,93,95,90};
    
        //优化前
        private static int[] sort(int[] array) {
            if (array.length < 2) return array;
            //找出数组的最大值
            int max = array[0];
            for (int i : array) {
                if (i > max) {
                    max = i;
                }
            }
            //初始化一个计数数组且值为0
            int[] countArray = new int[max + 1];
            for (int i = 0; i < countArray.length; i++) {
                countArray[i] = 0;
            }
            //填充计数数组
            for (int temp : array) {
                countArray[temp]++;
            }
            int o_index = 0;//原数组下标
            int n_index = 0;//计数数组下标
            while (o_index < array.length) {
                //只要计数数组的下标不为0,就将计数数组的值从新写回原数组
                if (countArray[n_index] != 0) {
                    array[o_index] = n_index;//计数数组下标对应元素组的值
                    countArray[n_index]--;//计数数组的值要-1
                    o_index++;
                } else {
                    n_index++;//上一个索引的值为0后开始下一个
                }
            }
            return array;
        }
    
        //优化后
        private static int[] sort2(int[] array) {
            if (array.length < 2) return array;
            //找出数组中的最大值和最小值
            int min = array[0], max = array[0];
            for (int i : array) {
                if (i > max) {
                    max = i;
                }
                if (i < min) {
                    min = i;
                }
            }
            //定义一个偏移量,即最小值前面0~min的范围,这里直接用一个负数来表示
            int bias = 0 - min;
            //初始化一个计数数组且值为0
            int[] countArray = new int[max - min + 1];
            for (int i = 0; i < countArray.length; i++) {
                countArray[i] = 0;
            }
            for (int temp : array) {
                countArray[temp + bias]++;
            }
            //填充计数数组
            int o_index = 0;//原数组下标
            int n_index = 0;//计数数组下标
            while (o_index < array.length) {
                if (countArray[n_index] != 0) {
                    array[o_index] = n_index - bias;
                    countArray[n_index]--;
                    o_index++;
                } else {
                    n_index++;
                }
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
            System.out.println("=================优化排序====================");
            print(ARRAY2);
            System.out.println("============================================");
            print(sort2(ARRAY2));
        }
    }
    

    时间复杂度

    很明显,在排序过程中,我们至少遍历了三次原始数组,一次计数数组,所以它的复杂度为Ο(n+m)。因此,计数排序比任何排序都要块,这是一种牺牲空间换取时间的做法,因为排序过程中需要用一个计数数组来存元素组的出现次数。

    算法稳定性

    在新建的计数数组中记录原始数组中每个元素的数量,如果原始数组有相同的元素,则在输出时,无法保证元素原来的排序,是一种不稳定的排序算法。

    桶排序

    桶排序是计数排序的升级,计数排序可以看成每个桶只存储相同元素,而桶排序每个桶存储一定范围的元素,通过函数的某种映射关系,将待排序数组中的元素映射到各个对应的桶中,对每个桶中的元素进行排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序),最后将非空桶中的元素逐个放入原序列中。

    桶排序需要尽量保证元素分散均匀,否则当所有数据集中在同一个桶中时,桶排序失效。

    image-20210808133137559

    代码实现

    1. 找出数组中的最大值max和最小值min,可以确定出数组所在范围min~max

    2. 根据数据范围确定桶的数量

      • 若桶的数量太少,则桶排序失效
      • 若桶的数量太多,则有的桶可能,没有数据造成空间浪费

      所以桶的数量由我们自己来确定,但尽量让元素平均分布到每一个桶里,这里提供一个方式

      (最大值 - 最小值)/每个桶所能放置多少个不同数值+1

    3. 确定桶的区间,一般是按照(最大值 - 最小值)/桶的数量来划分的,且左闭右开

    public class BucketSort {
    
        public static final int[] ARRAY = {35, 23, 48, 9, 16, 24, 5, 11, 32, 17};
    
        /**
         * @param bucketSize 作为每个桶所能放置多少个不同数值,即数值的类型
         *                   例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,
         *                   但是容量不限,即可以存放100个3
         */
        public static List<Integer> sort(List<Integer> array, int bucketSize) {
            if (array == null || array.size() < 2)
                return array;
            int max = array.get(0), min = array.get(0);
            // 找到最大值最小值
            for (int i = 0; i < array.size(); i++) {
                if (array.get(i) > max)
                    max = array.get(i);
                if (array.get(i) < min)
                    min = array.get(i);
            }
            //获取桶的数量
            int bucketCount = (max - min) / bucketSize + 1;
            //构建桶,初始化
            List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
            List<Integer> resultArr = new ArrayList<>();
            for (int i = 0; i < bucketCount; i++) {
                bucketArr.add(new ArrayList<>());
            }
            //将原数组的数据分配到桶中
            for (int i = 0; i < array.size(); i++) {
                //区间范围
                bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
            }
    
            for (int i = 0; i < bucketCount; i++) {
                if (bucketSize == 1) {
                    for (int j = 0; j < bucketArr.get(i).size(); j++)
                        resultArr.add(bucketArr.get(i).get(j));
                } else {
                    if (bucketCount == 1)
                        bucketSize--;
                    //对桶中的数据再次用桶进行排序
                    List<Integer> temp = sort(bucketArr.get(i), bucketSize);
                    for (int j = 0; j < temp.size(); j++)
                        resultArr.add(temp.get(j));
                }
            }
            return resultArr;
        }
    
        public static void print(List<Integer> array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()));
            System.out.println("============================================");
            print(sort(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()), 2));
        }
    }
    

    时间复杂度

    桶排序算法遍历了2次原始数组,运算量为2N,最后,遍历桶输出排序结果的运算量为N,初始化桶的运算量为M。

    对桶进行排序,不同的排序算法算法复杂度不同,冒泡排序算法复杂度为O(N^2),堆排序、归并排序算法复杂度为O(NlogN),我们以排序算法复杂度为O(NlogN)进行计算,运算量为N/M * log(N/M) * M

    最终的运算量为3N+M+N/M * log(N/M) * M,即3N+M+N(logN-logM),去掉系数,时间复杂度为O(N+M+N(logN-logM))

    参考:桶排序算法详解

    算法稳定性

    桶排序算法在对每个桶进行排序时,若选择稳定的排序算法,则排序后,相同元素的位置不会发生改变,所以桶排序算法是一种稳定的排序算法。

    基数排序

    常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成。

    基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,同时每一轮排序都基于上轮排序后的结果;当我们将所有的位排序后,整个数组就达到有序状态。基数排序不是基于比较的算法。

    基数是什么意思?对于十进制整数,每一位都只可能是0~9中的某一个,总共10种可能。那10就是它的基,同理二进制数字的基为2;对于字符串,如果它使用的是8位的扩展ASCII字符集,那么它的基就是256。

    基数排序有两种方法:

    • MSD 从高位开始进行排序
    • LSD 从低位开始进行排序

    对于大小范围为0~9的数的组合(若是两位数,就是个位数和十位数的组合),于是可以准备十个桶,然后放到对应的桶里,然后再把桶里的数按照0号桶到9号桶的顺序取出来即可。

    image-20210809173152835

    代码实现

    public class RadixSort {
    
        public static final int[] ARRAY = {82, 50, 21, 5, 66, 48, 43, 79, 14, 37, 25};
    
        public static int[] sort(int[] array) {
            if (array.length < 2) return array;
            //根据最大值算出位数
            int max = array[0];
            for (int temp : array) {
                if (temp > max) {
                    max = temp;
                }
            }
            //算出位数digit
            int maxDigit = 0;
            while (max != 0) {
                max /= 10;
                maxDigit++;
            }
            //创建桶并初始化
            ArrayList<ArrayList<Integer>> bucket = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
                bucket.add(new ArrayList<>());
            }
            //按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,每一轮排序都基于上轮排序后的结果
            int mold = 10;//取模运算
            int div = 1;//获取对应位数的值
            for (int i = 0; i < maxDigit; i++, mold *= 10, div *= 10) {
                for (int j = 0; j < array.length; j++) {
                    //获取个位/十位/百位......
                    int num = (array[j] % mold) / div;
                    //把数据放入到对应的桶里
                    bucket.get(num).add(array[j]);
                }
                //把桶中的数据重新写回去,并把桶的元素清空,开始第二轮排序
                int index = 0;
                for (int k = 0; k < bucket.size(); k++) {
                    //桶中对应的数据
                    ArrayList<Integer> list = bucket.get(k);
                    for (int m = 0; m < list.size(); m++) {
                        array[index++] = list.get(m);
                    }
                    //清除桶
                    bucket.get(k).clear();
                }
            }
            return array;
        }
    
        public static void print(int[] array) {
            for (int i : array) {
                System.out.print(i + "  ");
            }
            System.out.println("");
        }
    
        public static void main(String[] args) {
            print(ARRAY);
            System.out.println("============================================");
            print(sort(ARRAY));
        }
    }
    

    时间复杂度

    计数排序算法的时间复杂度是O(N+M),基数排序算法执行了k次计数排序,所以基数排序算法的时间复杂度为O(K(N+M))。

    算法稳定性

    从上面的分析可以看出,相同元素会按照顺序放进固定的桶内,取出的时候也是按照顺序取出来的,所以基数排序算法是一种稳定的排序算法。

    基数排序 vs 桶排序 vs 计数排序

    这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异

    • 基数排序:根据每一位的关键字来分配桶
    • 桶排序:存储一定范围的值
    • 计数排序:每个桶只存储一个类型值,但是数量不限

    image-20210810001026742

    展开全文
  • 经典算法排序算法

    千次阅读 多人点赞 2019-10-18 12:15:00
    点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午 12:15,一起学算法作者 | 程序员小吴来源公众号 | 五分钟学算法今天分享的一道算法面试来源于 某零2015...
  • 排序练习及的答案.ppt

    2020-06-29 04:04:45
    小学语文句子排序技巧 排序题三字经 排序题,并不;通读题,前后看; 有代词,往前串;同话题,连一连; 找顺序,时空阃;标志词,抓关键 内容上,要映现;排完了,先浏览 不通顺,再换换;对答案,笑开颜 句子排序的技巧 多题目...
  • 代码如下: 以上就是这道的所有代码,代码不多,但是其中的算法思想我觉得真的是很厉害,很难想象出,想到这个方法的是什么人。 核心就在于那个空桶的存在,抹杀很多的可能性。使其最终的答案只可能存在于相邻两个...
  • 【数据结构】十大排序

    万次阅读 多人点赞 2021-08-29 07:26:56
    打开算法大门,从排序开始
  • 数据结构真的很难学?

    千次阅读 2019-08-16 13:41:52
    真的很难吗?其实数据结构只是讲了3部分内容:线性结构、树和图。到底难在哪里呢?我通过调查,了解到数据结构难学大概有以下4个原因。 (1)无法接受它的描述方式。数据结构的描述大多是抽象的形式,我们习惯了...
  • 史上最全Java初中级面试,发现网上多Java初级面试都没有答案,所以花了长时间搜集整理出来了这套Java面试大全,希望对大家有帮助哈~ 本人发现网上虽然有不少Java相关的面试,但第一未必全,第二未必有...
  • MySQL数据库面试(2020最新版)

    万次阅读 多人点赞 2020-03-10 17:20:40
    优化查询过程中的数据访问 优化长的查询语句 优化特定类型的查询语句 优化关联查询 优化子查询 优化LIMIT分页 优化UNION查询 优化WHERE子句 数据库优化 为什么要优化 数据库结构优化 MySQL数据库cpu飙升到500%的...
  • 常见面试题排序算法(二)

    千次阅读 2013-10-14 11:44:11
    常见的排序算法 总结一下常见的排序算法。 排序分内排序和外排序。...内排序的方法有许多种,按所用策略不同,可归纳为五类:插入排序、选择排序、交换排序、归并排序、分配排序和计数排序。 插入排序主要包括直接插入
  • 审题提取有效信息: 最大跳跃长度为k 每次跳完总长度为L 不能连续两次跳跃长度大于等于p 不同的方案有多少种(步数或某个位置不同即可) 审完后看看给出的样例,猪哥很快想到可以使用动态规划来解题,动态规划...
  • Python 面试的时候,会涉及到多的八股文,我结合自己的经验,整理Python 最强面试。 Python 最强面试主要包括以下几方面: Python 基础(已完成) Python 进阶 Python 后台开发 爬虫 机器学习 对每道面试...
  • 简单插入排序的增量优化
  • 蓝桥杯 I.双向排序

    千次阅读 多人点赞 2021-04-29 21:26:43
    第一个操纵为1,我们要将y移动到第一个红线的右端(下图),移动过程中给非红线的部分一次赋值,并k– 最终实现的效果如下: 这就实现了反转的操作 我讲的不是清楚,有什么问题可以评论区里问 代码: 好,代码为...
  • 带你了解有向无环图和拓扑排序

    千次阅读 2020-04-09 19:19:42
    在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(DAG图)。而提到DAG,就差不多会联想到拓扑排序,拓扑排序是指由某个集合上的一个...DAG在区块链中得到广泛的应用哦。
  • (c/c++) sort cmp规则 :日期排序

    千次阅读 多人点赞 2020-07-23 11:21:46
    } */ 但是,C++中STL本身已经提供了性能很好(我们自己编写的算法很难超过他的效率)的sort函数,所以我们只需要去编写对应的小于(cmp)规则即可。 同时注意到输出中是有不足补0的情况的,还需要了解一下cout控制...
  • Java面试大全(2021版)

    万次阅读 多人点赞 2020-11-25 11:55:31
    发现网上多Java面试都没有答案,所以花了长时间搜集整理出来了这套Java面试大全,希望对大家有帮助哈~ 本套Java面试大全,全的不能再全,哈哈~ 一、Java基础知识面试 1、Java概述 ①. 何为编程 ...
  • 1. 写一个方法对任意引用数据类型数组进行排序。具体要求如下: 1) 方法声明为public void sortArr(Object arr[]){ } 2) 方法中首先输出排序前数组内容,然后进行排序,最后输出排序后数组内容。 3) 可以是冒泡...
  • 试题 E: 排序(难度:★★★★)15分 【问题描述】 小蓝最近学习了一些排序算法,其中...小蓝找到了多字符串试图排序,他恰巧碰到一个字符串,需要 100 次交 换,可是他忘了吧这个字符串记下来,现在找不到了。 请
  • C++ 扑克牌排序

    万次阅读 2019-04-28 09:59:53
    ‘3’,‘4’,‘5’,‘6’,‘7’,‘8’,‘9’,‘10’,‘J’,‘Q’,‘K’,‘Joker’,拍序的规则是四个的放一起,三个的放一起,对子放一起,个子放一起,无论是四个、三个、对子还是个子,内部都需按大到小排序,并且...
  • Java面试大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
    发现网上多Java面试都没有答案,所以花了长时间搜集整理出来了这套Java面试大全,希望对大家有帮助哈~ 本套Java面试大全,全的不能再全,哈哈~ 一、Java 基础 1. JDK 和 JRE 有什么区别? JDK:Java ...
  • 前言当你第一眼看到这道面试是不是心里在暗喜,一问算法就比问排序算法,一问排序算法就问快速排序。如果你回答:STL里的sort算法肯定用的是快速排序啊?不成还是冒泡排序么?如果你只是回答快速排序,那么...
  • 这可能最全的操作系统面试

    万次阅读 多人点赞 2021-04-13 09:30:37
    破坏互斥条件 破坏保持等待的条件 破坏不可抢占条件 破坏循环等待条件 死锁类型 两阶段加锁 通信死锁 活锁 饥饿 后记 大家好,我是 cxuan,我之前汇总了一下关于操作系统的面试,最近又重新翻阅了一下发现不是全...
  • 总体来说,汇顶科技的固件开发工程师的笔试卷并不算,中规中矩的一份试卷。试卷12条单选、2条多选、2条填空、1条编程、3条简答。题目从考察的知识点上来讲,C语言基础(没有C++)、单片机基础为主,也...
  • 并发编程面试(2020最新版)

    万次阅读 多人点赞 2020-03-14 17:28:01
    Java面试总结(2021优化版)已发布在个人微信公众号【技术人成长之路】,优化版首先修正了读者反馈的部分答案存在的错误,同时根据最新面试总结,删除了低频问题,添加了一些常见面试,对文章进行了精简优化,欢迎...
  • 数据结构和算法之排序总结

    千次阅读 多人点赞 2021-11-03 19:35:22
    一、排序的概念及应用 ???? 排序的概念 ???? 排序的运用 ... 常见的排序算法 二、常见排序算法的实现 ... 插入排序 1、直接插入排序 2、希尔排序 ... 选择排序 1、直接选择排序 2、堆排序 ...四、概念选择

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,517
精华内容 28,206
关键字:

很难的排序题