Chapter7. Sorting

排序的分类

插入型排序

遍历列表,将元素依次插入已经排好序的字序列中。Leetcode: 147

Demo: 4 2 1 3

1: 2 4 1 3
2: 1 2 4 3
3: 1 2 3 4

简单插入排序 ——> 希尔排序

选择型排序

每一趟(第 i 趟)在后面 n - i + 1 个待排元素中选择最值元素,成为有序子序列的第 i 个元素。Leetcode:

简单选择排序 ——> 堆排序

Demo: 4 2 1 3

1: 1 2 4 3
2: 1 2 4 3
3: 1 2 3 4
4: 1 2 3 4

交换型排序

冒泡排序 ——> 快速排序

排序的稳定性

选择排序(Demo: 2, 2, 1),希尔排序,堆排序,快速排序(后3个都是高效排序算法,有得必有失)都是不稳定的。