4.6.2排序（三）冒泡排序与简单选择排序算法
文章目录
- 冒泡排序
- 简单选择排序
冒泡排序
冒泡排序每趟逐一比较邻近2个元素的大小，并在排序不正确时进行位置交换，经过一趟趟排序后，如果再无交换发生（或进行了n-1趟冒泡），则表示排序完成。当序列有序时，只需要进行一趟完整的比较，无需移动元素，即可完成排序。当完全逆序时，则每趟需要进行多次位置交换。
图例中，每趟冒泡时，黄色底标注的元素是当前进行比较，且可能做位置交换的元素。从图例中关键码48的排序情况看，冒泡排序属于稳定排序。
简单选择排序
简单选择排序每趟都可保证1个元素排到正确的位置。一定会进行n-1趟简单选择排序，每趟排序时，比较关键码i与其后n-i个关键码，从中选出（以非递减排序为例）关键码最小的元素，与i进行交换。
图例中，每趟排序里，黄色底标注的是参与比较、位置交换的元素。可以看到，随着排序的进行，问题的规模在不断缩小。从关键码48的排序结果看，简单选择排序是一种不稳定排序。