常用排序算法_牛客博客

一、常用排序算法的平均复杂度和最坏复杂度

1. 插入排序：遍历数组(n)，如果发现元素比前一个元素值小，那么就将元素暂存，逐一与之前元素比较，如果比该元素大，就后移一位（n）

平均：O(n²)
最坏：O(n²)
最好：O(n)（不移动，只遍历）

模拟：

12 30 9 100 1 3 10

9 12 30 100 1 3 10

1 9 12 30 100 3 10

1 3 9 12 30 100 10

1 3 9 10 12 30 100

2. 冒泡排序：双层循环，外层从后往前，里层从前往后，如果后面比前面小，就交换。

平均：O(n²)
最坏：O(n²)
最好：O(n²)

模拟：

1 3 2 7 5 6 9 8 4

1 2 3 5 6 7 8 4 9

1 2 3 5 6 7 4 8 9

1 2 3 5 6 4 7 8 9

1 2 3 5 4 6 7 8 9

1 2 3 4 5 6 7 8 9

3. （简单）选择排序：从本位开始，找到后面最小的交换

平均：O(n*log₂n)
最坏：O(n²)
最好：O(n²)

模拟：

1 3 2 7 5 6 9 8 4

1 2 3 7 5 6 9 8 4

1 2 3 4 5 6 9 8 7

1 2 3 4 5 6 7 8 9

4. 快排：思想是，一趟挑出1个数，将数组分成左右两部分，左边小于该数，右边大于该数。维护有两个索引（low, high)，随机将数组中一个数定为“基准”，先从high右往左找到第一个比基准小的与基准交换，更新low和high，再从low左往右找第一个大于基准的与基准交换，更新low和high。直到low == high。进行下一趟，一般三趟足以。（第一堂完成后左边再选一个，右边再选一个即可。）

平均：O(n*log₂n)
最坏：O(n²)

模拟：

1 3 2 7 5 6 9 8 4

4 3 2 7 5 6 9 8 1

4 3 2 1 5 6 9 8 7

（一趟结束）

5. 堆排序：对所给数组进行建小顶堆(如果降序，建大顶堆)，得到堆顶元素就是最小值，写入新数组；再整理剩下元素再建立小顶堆，再写入堆顶元素，如此类推，直到堆中没有元素。

平均：O(n*log₂n)
最坏：O(n*log₂n)

6.归并排序：将原始数组分成若干个子序列，两两合并排序，再合并排序......直到合并完成。

平均：O(n*log₂n)
最坏：O(n*log₂n)

（同数量级排序方法中性能最好的---又快又稳定）

模拟：

1 3 2 7 5 6 9 8 4

[1 3] [2 7] [5 6] [8 9] [4]

[1 2 3 7] [5 6 8 9] [4]

[1 2 3 5 6 8 9] [4]

[1 2 3 4 5 6 7 8 9]

7. 希尔排序：要选步长，每隔一个步长选定一个元素，对选定的序列排序，再选一次再排；完成后换步长再排。步长的选取很重要，但没有好的选取方法。

一位大佬的总结：https://www.cnblogs.com/wskwbog/p/11236136.html