冒泡排序

1. 依次比较相邻两个元素大小。
2. 如果前一个元素大于后一个元素，则交换位置。
3. ...
4. 在剩下的元素中，重复上述过程。

平均速度O(n²),最坏速度O(n²)
每次排序都会把子数组中的一个最大值放到最终位置。

选择排序

1. 从原始数组中选择一个最小的元素与数组第一个元素交换。
2. 从剩下的元素中选择一个次小的元素与数组第二个元素交换。
3. ...
4. 重复上述过程。

平均速度O(n²),最坏速度O(n²)

插入排序

1. 将数组前面两个元素顺序排好。
2. 将第三个元素与前面排好的两个数比较，并插入合适的位置。
3. 将第四个元素与前面排好的三个数比较，并插入合适的位置。
4. ...
5. 重复上述过程。

平均速度O(n²),最坏速度O(n²)

Shell排序（希尔排序，缩小增量排序）

最后一步是选择排序
平均速度O(n^3/2),最坏速度O(n²)

快速排序

平均速度O(nlogn),最坏速度O(n²)

堆排序

平均速度O(nlogn),最坏速度O(nlogn)

合并排序

平均速度O(nlogn),最坏速度O(nlogn)