2023CSP初赛备考复习 || 排序

排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列

稳定性

稳定排序

排序后 2 个相等键值的顺序和排序之前它们的顺序相同

不稳定

排序后 2 个相等键值的顺序和排序之前它们的顺序不相同

排序前

排序后

稳定

排序后

不稳定

常见的排序算法

冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序

冒泡排序 （Bubble Sort）

冒泡排序是一种简单直观的排序算法，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排

示例

5 4 8 9 7

1 第1趟

最大数9交换到最右边

2 第2躺

剩下数字中最大数8交换到最右边

3 第3躺

剩下数字中最大数7交换到最右边

4 第4趟

剩下数字中最大数5交换到最右边

动图

动图可查看如下链接

http://image.61coding.cn/img/072201.gif

示例代码

时间复杂度

平均时间复杂度

冒泡排序，每次两两比较，循环比较一遍，一趟找到最大/最小数 一趟比较次数(1~n-1)

冒泡需要n-1 趟

冒泡排序时间复杂的O(n^2)

最好时间复杂度

如果在其中一趟发现都是排序好的，则可以提前退出，不走下一趟

因此，如果序列本身是排好序的，需要一趟比较即可

此时时间复杂的为O(n)

最坏时间复杂度

O(n^2)

稳定性

稳定

排序后 2 个相等键值的顺序和排序之前它们的顺序相同

选择排序

选择排序是一种简单直观的排序算法

1 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3 重复第二步，直到所有元素均排序完毕

示例

5 4 8 9 7

动图

动图可查看如下链接

http://image.61coding.cn/img/072202.gif

示例代码

时间复杂度

O(n^2)

稳定性

不稳定

排序后 2 个相等键值8的顺序和排序之前它们的顺序不相同

插入排序

插入排序是一种最简单直观的排序算法

1 整个序列分2部分，已排好序列和未排序序列

2 从未排序序列中取第1个，插入到已排序的序列中

3 类似打扑克牌，每次摸一张牌，插入到手中已排好顺序的合适位置

示例

5 4 8 9 7

动图

http://image.61coding.cn/img/072203.gif

示例代码

时间复杂度

平均时间复杂度

O(n^2)

最好时间复杂度

O(n)

已经排好序的情况，每次去一个元素放到已排序的最后

最坏时间复杂度

O(n^2)

稳定性

稳定

排序后 2 个相等键值的顺序和排序之前它们的顺序相同。

2023暑假班数学思维大纲

●高斯算法    ●图中填数    ●算式谜语    ●平均数问题        ●植树问题

●妙算技巧    ●拆数技巧    ●页码问题    ●高级鸡兔同笼     ●年龄问题

●行程问题    ●行走路线问题    ●组合图形   ●工程问题   ●整除与剩余问题

●周期问题    ●天平问题     ●买卖问题    ●非十进制    ●牛吃草

说明:实际课程根据上课进度略有调整。