插入排序
1.直接插入排序
基本思想：每趟将一条待排序的记录，按其关键字值(这里为了简单，我使用的就是int型值)的大小插入到前面已经排好序的记录序列中适当的位置，直到全部记录插入完成为止。
基本要求：开始时，将第0个记录组成一个有序的子表，然后依次将后面的记录插入到这个字表中，并且一直保持子表的有序性。
2.希尔排序：
基本思路：先选取一个小于n的整数d（增量，我这里为了方便就是每次减半，时间复杂度与d的选取有关，可以选取好各个d存入一个数组中），把n个记录分为d个字表，从下标为0的记录开始，间隔为d的记录组成一个子表，在各子表内进行直接插入排序。
3.二分插入排序
基本思路:将待排序的记录插入到前面已经排好序的记录的适当位置，要找到这个适当位置，最快的方法就是二分法。
交换排序
1.冒泡排序
基本思路：冒泡，顾名思义，就是小的数向上冒，大的数向下沉。依次比较相邻的两个数，将小数放在前面，大数放在后面。
主要步骤：
1.比较第一个数与第二个数，若a[0]>a[1]，则交换；然后比较第二个数与第三个数；依次类推，直至第n-1个数和第n个数比较为止——第一趟起泡排序，结果最大的数被安置在最后一个元素位置上。2.对前n-1个数进行第二趟冒泡排序，结果使次大的数被安置在第n-1个元素位置。
3.重复上述过程，共经过n-1趟冒泡排序后，排序结束
2.快速排序
基本思想：通过一趟排序将要排序的记录分割成独立的两个部分，其中一部分的所有记录的值都比另外一部分的所有记录的值小，然后再按此方法分别对这两个部分进行快速排序。
主要步骤：
1.数组头尾分别设置一个哨兵，分别为i和j，并设置数组头值为基准值
2.j从右开始扫描，扫描到小于基准值时，停下来。i从左开始扫描，扫描到大于基准值时，停下来。交换i和j所在位置的值。i和j继续扫描，直到相遇。若相遇，则交换基准值和相遇值。相遇的位置即分割的边界。
3.对分割的左右部分进行上诉过程
选择排序
1.直接选择排序
基本思路：走n趟，每趟把最小值放到前面。第一趟，第一个与后面的记录中寻找最小值的下标，然后将最小值和第一个交换。第二趟，第二个和后面的记录中寻找最小值下标，然后交换。重复步骤，直到n趟走完，排序完成。
2.树形选择排序（这里不谈）
3.堆排序（这里不谈）
归并排序
基本思路：采用经典的分治策略，分而治之。分：把一个数组分成2个，这2个又可以接着分，直到不能分为止。治：将分出来的小数组合并成一个有序的数组，比如 6 5合并成{5,6}，9 7合并成{7,9}
，然后{5,6}和{7,9}又可以合并成{5,6,7,9}，直到合并完成。
基数排序（这里不谈）基数排序是一种借助多关键字进行排序，也就是一种将单关键字按基数分成 多关键字 进行排序的方法。
老九学堂会员社群出品
原文：https://www.cnblogs.com/ljxt/p/11609040.html