系列文章目录
1.高精度的计算
2.排序（1）
目录
一、什么是排序
? ? ? ? 排序就是将一个无序的数列按照一定规则排列成一个有序数列，常见的排序规则有从小到大和从大到小两种。数列0、32、53、12、34、2、1、90按常用规则排序后为：
| 排序规则 | 排序后数列 |
|---|---|
| 从小到大 | 0、1、2、12、32、34、53、90 |
| 从大到小 | 90、53、34、32、12、2、1、0 |
二、用什么方法排序
? ? ? ? 目前常用的排序方法有插入排序、选择排序、冒泡排序等八大排序，这些排序时间复杂度各异。下面，我将列举这八大排序的时间、空间复杂度：
| 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | |
|---|---|---|---|
| 插入排序 | O(n^2) | O(n^2) | O(1) |
| 选择排序 | O(n^2) | O(n^2) | O(1) |
| 冒泡排序 | O(n^2) | O(n^2) | O(1) |
| 希尔排序 | O(n^s)，1<s<2 | O(n log n) | O(1) |
| 快速排序 | O(n^2) | O(n log n) | O(log n) |
| 堆排序 | O(n log n) | O(n log n) | O(1) |
| 归并排序 | O(n log n) | O(n log n) | O(n) |
| 系统函数 | O(n log n) | O(n log n) | 不详 |
? ? ? ? 本章将会讲解基本一些的排序方法，其他的将会在以后讲解。
三、怎样排序
? ? ? ? 接下来我会详细讲解一些排序算法，所有代码均为从小到大的排序代码。
3.1 冒泡排序
排序特点：每一个数值都会像水底的泡泡一样不断上升，直到到达合适的位置。
排序原理：就近比较两个数的值，如果前数大于后数，则交换两数，使数列逐渐变得有序。
代码示例：
for (int i=n;i>=1;i--)
for (int j=1;j+1<=i;j++)
if (a[j]>a[j+1])
swap(a[j],a[j+1]);输入样例：
5
3 2 5 4 1
输出效果截图：
算法评估：时间复杂度为O(n^2)，有些大。
3.2 插入排序
排序特点：每次交换两个的值，对于求得最少交换次数有一定帮助。
排序原理：从最前一个数向后枚举，与后面的数进行比较
代码示例：
for (int i=n;i>=1;i--)
for (int j=1;j<i;j++)
if (a[j]>a[i])
swap(a[j],a[i]);输入样例：
7
10 3 7 6 2 3 1
输出效果截图：
算法评估：?时间复杂度为O(n^2)，有些大，但是对于求得最少交换次数有一定帮助。
3.3 系统函数
排序原理：运用快速排序的优化，使得其在快排的基础上更加稳定。
函数原型：
sort(排序首地址,排序尾地址,排序规则函数);
前两个参数是必要的，最后一个可有可无，代码示例：
sort(a+1,a+1+n);算法评估：时间复杂度低，适用性强。
总结
? ? ? ? 排序算法千千万，唯有sort万人迷。插入排序时间慢，希尔排序不稳定 。
? ? ? ? 快速排序虽然快，但是要求特别高。堆排归排固然好，理解起来可复杂。
? ? ? ? 再见！