排序：
通过排序，实现一串记录按照某一关键字大小按照递增或递减的顺序排列。
排序在日常生活中有很多应用，例如我们点外卖时，可以根据好评数量，价格区间，受欢迎程度选择外卖，这些功能的实现都离不开排序，今天向大家分享几种数据结构中的常见的排序算法。
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 快速排序
- 堆排序
- 归并排序
由于内容较多，所以我会把排序的部分分为好几篇文章分享给大家，今天先和大家分享前三个--冒泡排序、选择排序、插入排序。
1.冒泡排序
此种排序方法的原理正如其名，通过冒泡将最大或者最小的数”冒“至最后，实现记录的有序。以升序排列为例。
思路：n个待排的数，从第一个数和第二个数开始，两两比较，两个数中较大的往后移动，较小的往前移动，即交换，则当最后两个数比较完后，所有数中最大的数已经被移至最末，第一趟冒泡排序完成，此时最后一个数有序，前n-1个数无序，继续按照相同的步骤进行第二次冒泡，第二次冒泡结束后，n个待排数中次大的数被移到倒数第二个位置...每冒一次泡可以使一个数据有序，n个待排数，冒n-1次泡后，n-1个数有序，剩下的一个数自动有序。
下面用图片来展示实现一组整数升序排序一次冒泡的过程。
6个待排的数(要求升序排序），分别是8，20，14，16，6，24，首先第一个数和第二个数比较，较大的往后放，较小的移至前，8和20无需交换即满足，比较下一组。
比较20和14，较大的往后放，较小的移至前，则需要把14移至20前。交换14和20
交换完以后，比较下一组，20和16，较大的往后放，较小的移至前，则需要把16移至20前。交换16和20
16和20交换完以后，比较下一组20和6，较大的往后放，较小的移至前，则需要把6移至20前。交换6和20
16和20交换完以后，比较下一组20和24，较大的往后放，较小的移至前，20和24满足小数在前，大数在后，无需交换。
自此，第一趟冒泡结束，待排数中最大的数被放在了最后一个位置上，n个待排数中，1个数已有序，n-1个待排数无序。
再进行与上述相同的过程，第二次冒泡，第二次冒泡后此大的数被放在倒数第二个位置上，n个待排数中，2个数已有序，n-2个待排数无序。继续进行冒泡，n个待排数中，3个数已有序，n-3个待排数无序。n个待排数中，4个数已有序，n-4个待排数无序...直到n个待排数中，n-1个数已有序，1个待排数无序。此时只剩一个数字，则由于其他的数都已有序，所以剩下的这一个待排数自动有序。至此排序结束，得到一个升序排列的整数序列。
通过以上过程的分析，我们可以得出，每冒一次泡，就能使一个待排数有序，那么要使n个数有序，需要冒n次泡，但是其实在n-1个数有序后，剩下的那1个数就自动有序了，所以我们一共需要冒n-1次泡，每次冒泡的过程都是待排数据的两两比较，根据升序/降序的要求，将较大的/较小的移至前/后，如果有n个数待排，这n个数相邻的两个数之间都要两两比较，以我们刚刚的例子为例（如下图），第一趟冒泡时，6个数待排，两两相邻比较，有5对数据需要比较，第一趟冒泡结束后，1个数有序，5个数待排，有4对数据需要比较，所以如果有n个数待排，这n个数相邻的两个数之间都要两两比较，有n-1对数据需要进行比较，随着冒泡进行，有序的数的个数越来越多，待排的数的个数变少，需要比较的数据的对数也变小。
有n个数待排。
第1趟冒泡，n个待排数相邻的两个数之间都要两两比较，需比较n-1对，第一趟冒泡结束。
第2趟冒泡，1个数有序，n-1个无序待排数相邻的两个数之间都要两两比较，需比较n-2对，第二趟冒泡结束。
第3趟冒泡，2个数有序，n-2个无序待排数相邻的两个数之间都要两两比较，需比较n-3对，第三趟冒泡结束。
第4趟冒泡，3个数有序，n-3个无序待排数相邻的两个数之间都要两两比较，需比较n-4对，第四趟冒泡结束。
.....
第n-1趟冒泡，n-2个数有序，2个无序待排数相邻的两个数之间都要两两比较，需比较1对，第n-1趟冒泡结束。
第n趟冒泡，n-1个数有序，1个无序待排数自动有序，所以无序进行第n趟冒泡。共进行n-1次冒泡。
其实以上的分析过程也就是代码实现冒泡排序的思路，两层循环，第一重循环控制冒泡次数，第二重循环控制每次冒泡需要比较的数据对数。
代码：
void BubbleSort(int* a, int left, int right)//a是待排数组地址，参数也可以传为int a[],对数组a[left,right]区间的元素进行升序排序
{
int n = right - left + 1;//[left,right]区间的元素个数
for (int i = 0; i < n - 1; i++)//冒泡趟数
{
for (int j = left; j < left + n - 1 - i; j++)//每一趟冒泡相邻数据比较交换
{
if (a[j] > a[j + 1])
{
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}代码优化：
冒泡排序的优化是基于对交换的判断来实现的，如果在某一趟冒泡中没有发生数据交换，则说明所有数据已经有序了，则可以直接跳出循环，避免不必要的循环与判断，从而减少时间消耗。
2.选择排序
这种排序是在待排序的数据中选择最大/最小的数放在已有序序列的末尾。
思路：将数据分为有序部分和无序部分，从无序部分选择最大/最小的数与无序区间首个元素交换，交换后变为有序部分的最后一个元素，即有序区间长度增长1。开始时，有n个待排序的数据存储在数组a中，已有序的序列长度为0，则从所有数中选择最大/最小的数放与a[0]交换，有序的序列长度增长为1，则有序区间是[0,0]，无序区间是[1,n-1]，再从无序区间中选择最大/最小的数放与a[1]交换，则有序区间是[0,1]，无序区间是[2,n-1]...继续选择，每次都从无序区间中选出最大/最小的数，尾插在有序序列末尾直至有序区间变为[0,n-1]，则待排的n个数有序。
下面用图片向大家展示选择排序（升序排序）的部分过程。红色框表示有序区间，绿色框表示无序区间。
开始时，有序区间长度为0，无序区间为[0,5]。
在无序区间中找到最小值，与无序区间首个元素交换，则有序区间变为[0,0]，无序区间变为[1,5]。
再从无序区间中找最小值--a[4]，与无序区间首个元素a[1]交换，则有序区间长度增长1，有序区间变为[0,1]，无序区间变为[2,5]。
继续从无序区间中找最小值，与无序区间首个元素交换，使有序区间长度增长1，变为[0,2],无序区间变为[3,5]。
继续按照上述步骤，从无序区间中找最小值，与无序区间首个元素交换后，将无序区间首个元素归到有序区间中，有序区间长度增长1，无序区间长度减少1，直至无序区间长度减小到0，则排序完成。
代码：
void SelectSort(int* a, int left, int right)//对数组a的闭区间[left,right]内的元素升序排序
{
int min =left;
while (left < right)
{
min = left;
for (int i = left; i <= right; i++)
{
if (a[i] < a[min])//找出无序区间的最小值
{
min = i;
}
}
int tmp = a[left];//无序区间最小值与无序区间首个元素交换，实现有序区间长度增1，无序区间长度减1
a[left] = a[min];
a[min] = tmp;
left++;//有序区间长度加1
}
}优化：
我们可以每次从待排序列中同时选出最大和最小值，再把最大最小值与无序区间的首个元素和末尾元素交换，使有序区间从两边开始递增，无序区间向中心靠拢，最终无序区间长度变为0，排序结束。
3.插入排序
每次向有序序列中按照升序/降序插入一个数，直至全部待排数插入，开始时，有序序列长度为1。
可以从日常生活中的例子来理解，类似于我们在打扑克牌的操作，整理牌时，每次摸一张，找到其在有序的牌中的合适的位置插入，直至所有牌插入，则变为有序。
思路：n个数待排，以升序排序为例。待排序区间为[0,n-1]
开始时，有序序列长度为1，第一个数认为是有序的，有序区间为[0,0]，无序区间为[1,n-1]，选择无序区间首个元素，将其插入到有序区间的合适位置，有序序列长度变为2，有序区间为[0,1]，无序区间为[2,n-1]。继续选择无序区间首个元素，将其插入到有序区间的合适位置，保持有序区间升序排序，有序序列长度变为3，有序区间为[0,2]，无序区间为[3,n-1]...继续选择无序区间首个元素，将其插入到有序区间的合适位置，保持有序区间升序排序，直至有序区间变为[0,n-1]，无序区间长度变为0，则排序完成，降序排序同理。
下面用图片向大家展示插入排序（升序排序）的过程：用橙色框表示有序区间，蓝色框表示无序区间。
开始时，有序区间为[0,0]，有序区间长度为1，无序区间为[1,5]。将无序区间首个元素插入有序区间的合适位置，使有序区间仍保持有序。
再取无序区间首个元素，将其插入到有序区间的合适位置，使有序区间仍保持有序，有序区间长度加1，无序区间长度减少1。
14应插入到8后，20前。
插入后，有序区间仍维持有序，有序区间长度加1，无序区间长度减1。再选无序区间首个元素，将其插入到有序区间合适位置，使有序区间仍保持有序。
待插入元素是无序区间首个元素16。
16应插入有序区间的14后，20前。
有序区间插入14后，仍保持升序有序，有序区间长度加1，无序区间长度减1。继续从无序区间取首个元素插入有序区间合适位置，使有序区间仍保持有序。
无序区间首个元素是6。
6应该插入有序区间元素8前来维持有序区间升序排列。
有序区间插入6后，仍保持升序有序，有序区间长度加1，无序区间长度减1。继续从无序区间取首个元素插入有序区间合适位置，使有序区间仍保持有序。
待插入元素是无序区间首个元素24。
24应插入有序区间元素20后，有序区间仍保持升序排列。有序区间长度加1，无序区间长度减1。
无序区间长度变为0，插入排序结束。
代码：
void InsertSort(int* a, int left, int right)//a数组[left,right]闭区间元素升序排序。
{
int end = left;//初始时认为首个元素有序，其余元素无序
while (end < right)
{
int pos = end + 1;//待插入元素是最后一个有序元素的下一个元素
int tmp = a[pos];
int i = 0;
for (i = end; i >= left; i--)//寻找待插入元素的合适插入位置
{
if (a[i] > tmp)
{
a[i + 1] = a[i];
}
else
{
break;
}
}
a[i + 1] = tmp;//插入
end++;//有序区间长度+1
}
}冒泡排序、选择排序、插入排序时间复杂度分析：
这三种排序的时间复杂度和空间复杂度均为：
时间复杂度：O(N^2)
空间复杂度：O(1)
- 冒泡排序时间复杂度 1+2+...+N=(1+N)*N/2----O(N^2)
- 冒泡排序空间复杂度 没有用到额外的空间 O(1)
- 选择排序时间复杂度 1+2+...+N=(1+N)*N/2----O(N^2)
- 选择排序空间复杂度 没有用到额外的空间 O(1)
- 插入排序时间复杂度 1+2+...+N=(1+N)*N/2----O(N^2)
- 插入排序空间复杂度 没有用到额外的空间 O(1)
这几种排序的效率都是比较低的，当比较的数据量很大时，用以上这三个比较方法效率低，下一篇文章我会向大家分享几种更高效的排序方法，以上就是本篇文章的全部内容，希望我的分享对你有帮助，如果文章有错误，欢迎在评论区指正或者与小Q私信，我们下篇文章再见！^-^