回顾上节课的内容 二分 有序 堆 平方级排序算法简单介绍 交换排序 冒泡排序 插入排序 选择排序.

Presentation on theme: "回顾上节课的内容 二分 有序 堆 平方级排序算法简单介绍 交换排序 冒泡排序 插入排序 选择排序."— Presentation transcript:

1

2 回顾上节课的内容 二分 有序 堆

3 平方级排序算法简单介绍 交换排序 冒泡排序 插入排序 选择排序

4 堆排序 回顾一下堆的内容 堆可以很容易地求出最大值 / 最小值，同时，维护堆的 性质的操作复杂度为 O(logn) 。 利用这一性质，我们可以先将所有元素放入堆中，然 后按顺序取出堆顶元素，最后就得到了一个有序队列 。

5

6 归并排序 首先，如果给定了两个有序的序列 list1 、 list2 ，如何将 其合并成一个有序序列？ 1671314 238910

7 归并排序 分别用指针 i 、 j 指向这两个序列， i 指向 list1 ， j 指向 list2 注意：这里的指针并不是 C 语言的指针，而是一个索 引，可以是数组下标，也可以是其它。（这里我们把 它们用作数组下标） 预设一个空的数组 ans 保存结果。 比较 i 、 j 两指针指向的元素的大小，如果 list1[i]<list2[j] 则将 list1[i] 加入 ans ，并使 i++ ，否则将 list2[j] 加入 ans ，使 j++ 。 重复上述过程，直到两个序列都为空。

8 归并排序 1671314 238910 i j

9 归并排序 1671314 238910 1 i j

10 归并排序 1671314 238910 12 i j

11 归并排序 1671314 238910 123 i j

12 归并排序 1671314 238910 1236 i j

13 归并排序 1671314 238910 12367 i j

14 归并排序 1671314 238910 123678 i j

15 归并排序 1671314 238910 1236789 i j

16 归并排序 1671314 238910 1236789 i j

17 归并排序 1671314 238910 1236789 13 i j

18 归并排序 1671314 238910 1236789 1314 i j

19 归并排序 二分 我们可以将数组分成左右两部分，分别排序，然后再 把这两部分合并即可。

20 归并排序 复杂度分析 在整个算法中，我们所做的就是将数列一分为二，然后 再收集起来。 每一层我们都做了 n 次操作，总共有 log(n) 层，所以算法 的总体复杂度位 O(nlogn)

21 求逆序数 在一个排列中，如果一对数的前后位置与大小顺序相 反，即前面的数大于后面的数，那么就称为一个逆序 。 我们发现一个很好的性质，在归并排序过程中，如果 左序列指针 i 指向的某个数大于右序列指针 j 指向的数 ，那么，左序列中剩下的都是右序列中这个数的逆序 数。而且这个次数不会被重复计算或者过度计算。

22

23 快速排序 在归并排序的过程中，我们将一列无序的数一分为二 。在子序列有序的情况下进行合并 与归并排序类似的是，快速排序也将序列一分为二， 分成的两列数 list1 、 list2 的特点是， list1 中所有的数都 小于 list2 中的数。 经过上一步的划分， list1 和 list2 有大小关系，但各自的 内部还是无序的。而这个问题又归结到将一列无序的 数变得有序这样的问题上，也就是子问题与当前问题 结构类似。可见，这一过程可以被递归。

24 快速排序 用伪代码来描述上述过程就是

25 快速排序 通过上述分析，很容易看出快速排序的思想。 下面 要解决的就是，如何将这列数一分为二，使得小 的数在左边，大的数在右边，即上面伪代码的 partiton 函数。

26 快速排序 Partiton 1 、任选一个基准（这里为了方便，我们选取这列数中 最靠右的元素） 2, 、维护两个指针 i,j ，分别指向这列数的左端点和右端 点。 3 、 i 指针向右滑动，直到遇到第一个大于等于基准的数 时停止。 j 指针向左滑动，直到遇到第一个小于基准的数 时停止。 4 、交换 i,j 指向的两个数 5 、重复 3 、 4 ，直到 i>=j

27 快速排序 28713564 i j 4

28 28713564 i j 4

29 28713564 ij 4

30 28713564 ij 4

31 28713564 ij 4

32 23718564 ij 4

33 23718564 ij 4

34 23178564 ij 4

35 23178564 ij 4

36 23178564 ij 4

37 23148567 ij 4

38 实现

39 快速排序 利用快速排序求第 K 大 有时我们只关心排名第 K 的人是谁，而不关心整个数 据集的顺序关系。 算法思想 前面的分析中，第一次递归过程中，过得基准的位置为 p ，如果 p 等于 k ，问题解决。如果 p 大于 k ，那么 k 一定在 左区间，否则一定在右区间

40 学长教你偷懒 C++STL Sort 函数

41