目录
1.直接插入排序
代码实现
时间复杂度
2. 冒泡排序
代码实现
时间复杂度
3. 对比直接插入排序和冒泡排序
4. 希尔排序
代码实现 （2种版本）
特性总结
5. 选择排序
代码实现（2种版本）
时间复杂度
1.直接插入排序
基本思想：
把第一个元素当作有序，把第二个元素插入进去，前两个元素有序，把第三个元素插入进去，前三个元素已经有序，把第四个元素插入进去，以此类推，这样从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想。
它的工作原理为将待排列元素划分为【已排序】和【未排序】两部分，每次从【未排序】元素中选择一个插入到【已排序】元素中的正确位置。
动图：
代码实现
//插入排序
void InsertSort(int* a, int n) //n个数据
{for (int i = 0; i < n - 1; i++) //最后end=n-2，注意i的取值范围{int end = i; int tmp = a[end + 1];//[0,end]有序，把end+1位置的值插入到这个区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end]; //数据往后挪--end;}else{break;}}a[end + 1] = tmp; //这条语句没有放到上面的else语句里是为了兼容end=-1的情况，所有值都比tmp值大，把它放在a[0]处}
}时间复杂度
最好情况：要排序的数据本身就有序，没有移动，总共比较了n-1次，时间复杂度为O(n)
最坏情况：即待排数据是逆序的，需要比较1+2+3+……+n-1=(n-1)(1+n-1)/2次，时间复杂度O(n²)
总的时间复杂度为O(n²)。
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
2. 冒泡排序
代码实现
void BubbleSort(int* a, int n)
{for (int j = 0; j < n-1; j++){int flag = 0;//若flag为1，则有数据交换，否则退出循环//单趟for (int i = 0; i < n-j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);flag = 1;} }if (flag == 0){break;}}
}时间复杂度
最好情况，待排序的数据有序，总共进行n-1次比较，没有数据交换，时间复杂度为O(n)。
最坏情况：待排序数据是逆序的，需要进行n-1+n-2+……+3+2+1=(n-1)(n-1+1)/2次比较。
总的时间复杂度为O(n²)。
3. 对比直接插入排序和冒泡排序
虽然它们的时间复杂度都为O(n²)，但是插入排序在多数情况下会优于冒泡排序。如果数据存在大量重复元素或已经部分有序，插入排序通常会比冒泡排序更快，因为插入排序可以利用这些特点来减少比较和移动的次数，对于完全随机分布的数据集合，两者的性能相差不大。
4. 希尔排序
希尔排序是一种排序算法，由美国计算机科学家Donald Shell于1959年提出。希尔排序法又称缩小增量法。
基本思想：将待排序的元素分为多个子序列，子序列之间相距某个“增量”，然后对每个子序列进行插入排序。然后逐渐减小增量排序，最终将增量减小到1，此时序列已经基本有序，只需完成最后一轮的插入排序，只进行了少量的比较和交换操作，大大提高了排序效率。
基本有序：小的数据基本在前面，大的数据基本在后面，不大不小的基本在中间。
将数据分成几组，增量gap是几就是几组，每个组分别进行插入排序，缩小间隔gap的值，重复上述过程，最后gap=1，进行最后一次插入排序就完成排序了。
图解：
代码实现 （2种版本）
//方便理解版本
void ShellSort(int* a, int n)
{int gap = n;//将数组的长度赋值给gap，再设置循环使gap除以3得到 分成4组 分成2组 分成1组(依据上图分析)while (gap > 1){gap = gap / 3 + 1; //+1为了保证gap最后是1，gap>1是预排序，gap=1是插入排序for (int j = 0; j < gap; j++) //j变量指向初始位置，gap组依次排序，一组一组来！{ for (int i = j; i < n - gap; i += gap) //注意控制好i的取值范围，防止越界{int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}
}//优化版本，相对于上面减少一层循环，效率无区别
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) //多组并着走！{int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;} }
}特性总结
１．希尔排序是对直接插入排序的优化。
２．当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经基本接近有序，只需最后插入排序进行少量的比较和交换操作，这样就会很快。这样整体而言，可以达到优化的效果。
３．希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，有学者经过大量计算，得出结果大约在Ｏ（n＾1.25） 到 Ｏ（1.6*n²) 范围内，我们暂且按照这个来算。
４．稳定性：不稳定。
5. 选择排序
基本思想： 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。
动图：
流程：
- 在元素集合 [0,n-1] 中选择最小的数据,将其和第1个位置的数据交换。
- 接着从剩下的n-1个数据中选择最小的数，将其和第2个位置的数据交换。
- 不断重复上面步骤，直到最后两个元素发生交换，完成排序。
代码实现（2种版本）
void SelectSort(int* a, int n) // [0,n-1]
{for (int i = 0; i < n - 1; i++){int mini = i;for (int j = i + 1; j < n; j++){if (a[j] < a[mini]){mini = j;} }if (mini != i){Swap(&a[i], &a[mini]);} }
}//优化版本（一次性找出最大的数和最小的数的下标）
void SelectSort(int* a, int n) // [0,n-1]
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++)//遍历一遍，同时选出最小的数和最大的数的下标{if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[begin], &a[mini]);if (begin == maxi) //如果某次循环时初始元素下标begin处的值就是最大的数，当把mini处的值赋给begin，begin下标处的值发生改变，变成最小的数，就不能赋值给end了，需要更新一下maxi的值再发生交换{maxi = mini;}Swap(&a[end], &a[maxi]);begin++;end--;}
}时间复杂度
无论最好还是最坏情况，其比较次数都是一样多的，需要进行n-1+n-2+n-3+……+2+1=(n-1)(n-1+1)/2次比较，对于交换次数而言，最好的时候交换0次，最坏的时候交换n-1次，基于最终的排序时间是比较与交换次数的总和，因此，总的时间复杂度为O(n²)。
与冒泡排序的时间复杂度相同，但是在性能上要略优于冒泡排序。选择排序是不稳定的排序算法