冒泡排序

　　这个算法的名字由来是因为更小（大）的元素会经由交换逐步“浮”到数组的顶端（升序或降序排列)。

　　冒泡排序逻辑：首先冒出整个数组最大的一个，放到数组尾部。然后从头开始，依次比较相邻的两个数，将小数放前，大数放后。即在第一趟：首先比较第1个数和第2个数，将小数放前，大数放后；然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后，这样换到最后一个数必然是最大的一个。然后再从头开始冒泡次大的那个数，使倒数第2个数成为次大。如此重复，直至全部数组排序完成。

　　冒泡排序的时间复杂度（平均）为O(n²)、空间复杂度为O(1)，为稳定性排序算法。

　　比如：待排序数组arr=[6,3,8,2,9,1]，用冒泡排序算法对这个数组进行排序的图解分析如下图所示。

　　程序代码：

　　运行结果：

　　练习题１：下面是几个同学的数学成绩，请用冒泡排序编程，按高分到低分的顺序排序，然后每行一个人打印出来。

李小明  94，

霍顺高  97，

张飞鹏  88，

李华峰  99，

史大维  90，

黄芬诗  97。

　　选择排序

　　选择排序的逻辑：初始时在序列中找到最小元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。如果是倒序，就查找最大元素，方法一样。

　　选择排序与冒泡排序的区别，冒泡排序通过依次交换相邻两个顺序不合适的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

　　选择排序的时间复杂度（平均）为O(n²)、空间复杂度为O(1)，为不稳定性排序算法。

　　比如，待排序数组arr=[49,27,65,97,76,12,38]，用选择排序算法对这个数组进行排序的图解分析如下图所示。

　　程序代码：

　　运行结果：

　　练习题２：上一练习题改用选择排序完成。

　　插入排序

　　简单地说，就是把待排序的记录按其值的大小逐个插人到一个已经排好序的有序序列中，一个数组中，第1个元素算是已经排好的有序序列，用第2个元素和第1个元素比较，如果比它大，就在它后面，如果比它小，第2个元素就和第1个元素换位，于是前1,2两个元素构成了一个有序数组；然后第3个元素向这个序列中插人，先和第2个元素比较，比它大就停在后面，比它小就和它替换，然后继续和第1个元素比较，比它小则替换，比它大就停止；这样前3个元素又构成一个有序数组，以此类推，完成整个数组的排序。

　　插入排序的时间复杂度（平均）是O(n²)、空间复杂度是O(1)，为稳定性排序算法。

　　比如，待排序数组arr=[7,3,15,1,23,6]，用插入排序算法对这个数组排序的图解分析如下图所示。

　　程序代码：

　　运行结果：

　　练习题３：用插入排序完成练习题１。

　　半分插入排序

　　插入排序中把一个数插入有序数组中时，使用类似冒泡排序的办法，如果有序数组较大，操作的次数可能很多。既然是有序数组，当然可以用半分法直接定位插入位置，然后整体移动该位置及其后的元素，把要插入的元素放到那个位置里。时间复杂度、空间复杂度和稳定性都不变。注意：和半分搜索法不一样的地方是必须要先检查头尾元素。

　　程序代码：

　　练习题４：用半分插入排序完成练习题１。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社