思路：在找到第i个记录的插入位置时，前i-1个记录已排序，将第i个记录的排序码key[i]和已排序的前i-1个的中间位置记录的排序码进行比较，如果key[i]小于中间位置记录排序码，则可以在前半部分继续使用二分法查找，否则在后半部分继续使用二分法查找。直到查找范围为空，即可确定key[i]的插入位置。

?表插入排序

思路：表插入排序将在不进行记录移动的情况下，利用存储结构有关信息的改变来达到排序的目的。为此，可以给每个记录附设一个指针域 link,它的类型为整型，表插人排序的思路是，在插人第i个记录R，时，R, R2, ...... Ri-1已经通过各自的指针域link按排序码不减的次序连接成一个 (静态链)表，将记录R;的排序码key;与表中已经排好序的排序码从表头向右、或称向后依次比较，找到R,应插人的位置，将其插人在表中，使表中各记录的排序码仍然有序。

下标0处的link域指向排好序的第一个元素，其他下标的link域指向该元素的下一个元素，最后一个元素的link域指向0

Shell插入排序（希尔排序）

选择排序

思想：每次从待排序的文件中选择出排序码最小的记录，将该记录放于已排序文件的最后一个位置，直到已排序文件记录个数等于初始待排序文件的记录个数为止。

直接选择排序

首先从所有n个待排序记录中选择排序码最小的记录，将该记录与第一个记录交换，再从剩下的n-1个记录中选出排序码最小的记录和第2个记录交换。重复这样的操作直到剩下两个记录，再从中选出排序码最小的记录和第n-1个记录交换。

树型选择排序

参考：树型选择排序https://blog.csdn.net/qq_16234613/article/details/52675953?ops_request_misc=&request_id=&biz_id=102&utm_term=%E6%A0%91%E5%9E%8B%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-1-52675953.142%5Ev21%5Econtrol,157%5Ev15%5Enew_3&spm=1018.2226.3001.4187

堆排序?

参考：堆排序https://blog.csdn.net/m0_62434776/article/details/122930566

交换排序

思路：对待排序记录两两进行排序码比较，若不满足排序顺序，则交换这对记录，直到任何两个记录的排序码都满足排序要求为止。

冒泡排序

具体的做法是:第1趟，对所有记录从左到右每相邻两个记录的排序码进行比较，如果这两个记录的排序码不符合排序要求，则进行交换，这样一趟做完，将排序码最大者放在最后一个位置(即该排序码对应的记录最终应该放的位置).第2趟对前下的n-1个待排序记录重复上述过程，又将个排序码放于最终位置，反复进行n-1次，可n-1个排序码对应的记录放至最终位置，剩下的即为排序码最小的记录，它在第1的位置处。如果在某一趟中，没有发生交换，则说明此时所有记录已经按排序要求排列完毕，排序结束。