计算之魂 task3 打卡

1.4 关于排序的讨论

  1. 问题

    假定序列有N个元素,存于一个数组a[N]中, 现在需要将它从小到大排序。

  2. 选择排序

    它每一次从序列中挑出一个最大值,放在序列的最后,这样重复多次扫描序列后,整个序列就排序完毕。

    1. 从头到尾(即i=1~N)比较相邻的两个元素a[i]和a[i+1]。如果a[i]≤a[i+1],不做任何处理;反之,将a[i]和a[i+1]元素值互换,也就是说,小的放前面,大的放后面。这样一个一个互换,到了数组的末尾时,最后一个一定是最大的。这个元素就如同水中的气泡一样,不断上升,直到冒出头。这一遍从头到尾的扫描,进行了N−1次的比较和少于N−1次的互换。

    2. 步骤2,我们再从头到倒数第二个元素,即第N−1个元素,重复上述过程。每一次扫描,会从剩余的元素中找到其中最大的。当我们完成第K遍扫描时,最后K个元素已经排好序了。因此,对于有N个元素的数组,我们只需要扫描N次,每一次比之前少一个元素。

    3. 这样整个算法的复杂度就是 O(N^2)

    这里有很多次多余的比较和数据的移动

    1. 选择排序将所有数字都两两比较一次,但这是没有必要的。因为如果已经比较出X<Y、Y<Z,那么可以直接得出X<Z,无需进行X和Z的比较。

    2. 选择排序做了很多无谓的位置互换,举一个极端的例子,如果数组a已经逆序排好了,也就是说a[1]最大,a[2]次之,a[N]最小,a[1]和a[2]的有效移动都应该是往后移。但是,第一遍扫描时,先将a[2]往前移到了第一个位置,这是个无用功。

      比如说我的目标是向前走十步,我只要每次向前走一步,走十次就可以了。但你现在告诉我我需要先后退一步再前进两步,走二十次到达目的地,就很蠢。

  3. 插入排序

    1. 对于未排序数组,我们不断从后向前扫描,对于每一个元素,我们找到相应的位置插入。最后所有的元素扫描一遍,全部插入相应的位置,也就实现了排序。

    2. 每个元素只扫描了一次,但每个元素可能造成N次移动。

      首先,我们把最后一个元素a[N]拿出来,和第一个元素a[1]比较,比a[1]小就放在a[1]的前面,比a[1]大就放在a[1]的后面,成为数组中的第二个元素。这时,这两个元素排好了序。不过,上述操作在完成之前需要做一个准备工作,就是在a[1]之前,或者a[1]和a[2]之间给新插进来的元素a[N]留一个空位。

      比如说排队,每有一个人插队,这个人之后的所有人都需要向后移动,插队的人越多,插队的位置越靠前,就会有越多的人向后移动,所以不要插队!

    3. 插入排序时间复杂度也是O(N^2)

  4. 归并排序

    要理解归并排序算法,我们就需要摆脱常人的思维方式,倒过来想问题。

    1. 首先我们假设序列a[1…N]前后两部分都是排好序的,它们分别存在B和C两个子序列中,每个子序列都有N/2个元素,也就是说b[1],b[2],…,b[N/2]和c[1],c[2],…, c[N/2]都是有序的。

    2. 采用一步归并操作,把这两个有序的子序列合并起来

      如果b[1]<c[1],就把b[1]送回A序列中,即a[1]=b[1],否则就让a[1]=c[1],如此迭代,直到b或者c为空,假设b为空,那么c剩下的部分都比a中的元素大并且c剩下部分是排好序的,只需将c剩下部分拼接在a上就可得出合并的数组。

    3. 时间复杂度为O(NlogN)

  5. 常见高效排序算法对比

image

Q1.赛跑问题(GS)。

假定有25名短跑选手比赛争夺前三名,赛场上有五条赛道,一次可以有五名选手同时比赛。比赛并不计时,只看相应的名次。假设选手的发挥是稳定的,也就是说如果约翰比张三跑得快,张三比凯利跑得快,约翰一定比凯利跑得快。最少需要几次比赛才能决出前三名?

最少7次

  1. 平均分为5组A~E,每组5人决出前3名,按排名编号为A1~E3,此时比了5场

  2. 因为第一名一定在这五组的第一名里,所以先让A1,B1,C1,D1,E1比赛,假设A1最快,B1第二,以此类推。此时比赛六场。

  3. 因为D1和E1都比A1,B1,C1慢,所以前三名不在D组和E组里。

  4. 此时A1必是第一名,那么前三名还有两个名额,此时B3, C2, C3必不在前三名中。

  5. 只剩下A2,A3,B1,B2,C1有可能是前三名,此时进行最后一场比赛,前两名和A1为最后的前三名。此时比赛七场。

  6. 综上,最少比赛七场可找出前三名。

浙ICP备19012682号