文档介绍：: .
各种排序算法总结
排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不 同的表现，我们需要对各种排序算法熟练才能将它们应用到实际当中， 才能更好
地发挥它们的优势。今天，来总结下各种排序算法。
下面这个表格总结了各种排序算法的复杂度与稳定性：
Si册序
O(n2)
O(T?)
O(n^)
0(^}
O⑴
0(n2)
0(n2}
0(1)
0(^)
O(loffn)
丁诵走
0并沪
O(nlntjn)
O(l|
O(nlcffn)
OfnfiD^Ti)
0(1)
卜绽
昨;网E呼
O(mj) 1
0(1)
下號
O(lngaB)
0(吨朋)
二受枉1扌丰带
O(n/ogn)
<?(T1】
谢走
O(rt + k\ 11
O(n + k}
O(n - k)
冒泡排序
冒泡排序可谓是最经典的排序算法了，
它是基于比较的排序算法，
时间复杂度为
0(nA2)，其优点是实现简单，n较小时性能较好。
*算法原理
相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来， 最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数 据排序完成
• C++代码实现
1.
void
bubble_sort(
int arr[],
int len)
2.
{
3.
for ( int
i = 0; i < len -
1; i++)
4.
{
5.
for (
int j = len -
1; j >= i; j--)
6.
{
7.
if (arr[j] < arr[j -
1])
8.
{
9.
int
temp =
=arr[j];
10.
arr[j]=
=arr[j -
1];
11.
arr[j -
1 ] = temp;
12. }
13. }
14. }
15. }
选择排序
*算法原理
先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然 后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序 列的末尾。以此类推，直到所有元素均排序完毕。
* C++代码实现
1.
void
selec
;t_sort(
int arr[], int
len)
2.
{
3.
for
(int
i = 0; i < len; i++)
4.
{
5.
int
in dex = i;
6.
for
(int j = i + 1; j <
len; j++)
7.
{
8.
if (arr[j] < arr[i ndex])
9.
in dex =
j;
10.
}
11.
if
(in dex != i)
12.
{
13.
int temp = arr[i];
14.
arr[i] = arr[i ndex];
15.
arr[in dex] = temp;
16.
}
17. }
18. }
插入排序
*算法原理
将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元 素，依次将无序的元素插入到有序部分， 直到所有元素有序。插入排序又 分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排 序。它是稳定的排序算法，时间复杂度为 0(n A2)
・C++代码实现
1.
void
in sert_sort(
int arr[],
int len)
2.
3.
for
(int i = 1; i < len; i ++)
4.
5.
int j = i -
1；
6.
7.
while
(j > - 1 && k < arr[j])
8.
9.
arr[j +
1] = arr[j];
10.
11.
12.
arr[j +
1] = k;