八大排序算法排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
我们这里说说八大排序就是内部排序。
基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。
即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。
直接插入排序示例：如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
算法的实现：1.void print(int a[], int n ,int i){2. cout<<i <<":";3.for(int j= 0; j<8; j++){4. cout<<a[j] <<" ";5. }6. cout<<endl;7.}8.9.10.void InsertSort(int a[], int n)11.{12.for(int i= 1; i<n; i++){13.if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。
小于的话，移动有序表后插入14.int j= i-1;15.int x = a[i]; //复制为哨兵，即存储待排序元素16. a[i] = a[i-1]; //先后移一个元素17.while(x < a[j]){ //查找在有序表的插入位置18. a[j+1] = a[j];19. j--; //元素后移20. }21. a[j+1] = x; //插入到正确位置22. }23. print(a,n,i); //打印每趟排序的结果24. }25.26.}27.28.int main(){29.int a[8] = {3,1,5,7,2,4,9,6};30. InsertSort(a,8);31. print(a,8,8);32.}效率：时间复杂度：O（n^2）.其他的插入排序有二分插入排序，2-路插入排序。
c#实现的⼏种排序⽅法1.经典排序算法 – 插⼊排序Insertion sort插⼊排序就是每⼀步都将⼀个待排数据按其⼤⼩插⼊到已经排序的数据中的适当位置，直到全部插⼊完毕。
插⼊排序⽅法分直接插⼊排序和折半插⼊排序两种，这⾥只介绍直接插⼊排序，折半插⼊排序留到“查找”内容中进⾏。
图1演⽰了对4个元素进⾏直接插⼊排序的过程，共需要(a),(b),(c)三次插⼊。
public void Sort(int[] arr){for (int i = 1; i < arr.Length; i++){int t = arr[i];int j = i;while ((j > 0) && (arr[j - 1] > t)){arr[j] = arr[j - 1];//交换顺序--j;}arr[j] = t;}}折半排序算法是对直接插⼊算法的⼀种优化，优化的核⼼是：通过折半查看有序数组中间位置的数值（a）与待插⼊的数值（temp）的⼤⼩，如果a>=temp，则转向折半的左区间继续折半查找；如果a<temp，则转向折半后的右区间继续折半查找。
直到左右下标相同时，此时折半的下标也指向相同的位置，再做最后⼀次循环，最终的结果是：左右下标相差1，并且原来左侧的下标指向⼤于temp的位置，原来右侧的下标指向了⼩于temp的位置，即：array[biggerIndex] < temp < array[smallerIndex]。
//折半排序算法（传递待排数组名，即：数组的地址。
故形参数组的各种操作反应到实参数组上）private static void BinaryInsertionSortFunction(int[] array){try{int smallerIndex = 0; //记录有序数组的起始位置int biggerIndex = 0; //记录有序数组的终⽌位置int midIndex = 0; //记录获取有序数组的中间位置（折半法的关键：折半的位置）int temp; //记录带排的数值for (int i = 1; i < array.Length; i++) //循环向有序数组中插⼊数值（i从1开始，因为操作的是同⼀个数组）{temp = array[i]; //记录待插⼊有序数组的数值biggerIndex = i - 1;//当smallerIndex==biggerIndex时，进⼊最后⼀次循环：smallerIndex指向⼤于temp的数组位置，biggerIndex指向⼩于temp的数组位置while (smallerIndex <= biggerIndex){midIndex = (smallerIndex + biggerIndex) / 2; //确定折半的位置if(array[midIndex] >= temp) //折半位置的数值 >= temp{biggerIndex = midIndex - 1; //biggerIndex以midIndex为基础向前移动⼀位}else{smallerIndex = midIndex + 1; //smallerIndex以midIndex为基础向后移动⼀位}}for (int j = i - 1; j >biggerIndex; j--) //将有序数组中⼤于temp的数值分别向后移动⼀位{array[j + 1] = array[j]; //}array[biggerIndex + 1] = temp; //将temp插⼊biggerIndex + 1，因为此时array[biggerIndex]<temp<array[smallerIndex]}}catch (Exception ex){ }}2. //选择排序public static void SelectionSort(int[] num){int min, temp;for (int i = 0; i < num.Length-1; i++){min = i;for (int j =i+1; j < num.Length; j++){if (num[j] < num[min]){min = j;}}temp = num[i];num[i] = num[min];num[min] = temp;}}3. //冒泡排序(Bubble Sort)的基本思想是：将相邻的记录的关键码进⾏⽐较，若前⾯记录的关键码⼤于后⾯记录的关键码，则将它们交换，否则不交换。
插入排序的基本概念插入排序是一种简单直观的排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序的时间复杂度为O(n^2)，但在小规模数据时表现优异，且稳定性较好。
一、基本思想插入排序将待排序数组分为已排好序和未排好序两部分。
每次将未排好序的第一个元素插入到已排好序部分的相应位置，直至全部元素有序。
二、具体实现1. 直接插入排序直接插入排序是最基本的插入排序算法。
它从第二个元素开始遍历待排数组，将当前元素与前面已经排好序的元素依次比较，找到合适位置并插入。
2. 希尔排序希尔排序是直接插入排序的改进版。
它通过设置增量gap来分组进行直接插入排序，每轮对每个组进行一次直接插入排序。
随着增量gap逐渐减小，组数也逐渐减少，当gap=1时即为最后一轮直接插入排序。
三、优化方案1. 二分查找优化在寻找待插入位置时使用二分查找可以提高效率。
二分查找的时间复杂度为O(logn)，相比于直接比较可以减少一部分比较次数。
2. 跳跃式插入跳跃式插入是对直接插入排序的优化，它将待插入元素与一定间隔的元素进行比较，从而减少了比较次数。
四、应用场景由于插入排序在小规模数据时表现优异，因此常被用于对小规模数据进行排序。
同时，由于其稳定性较好，也常被用于稳定性要求较高的场景。
五、总结插入排序是一种简单直观的排序算法，通过构建有序序列实现对待排数组的排序。
虽然时间复杂度为O(n^2)，但在小规模数据时表现优异，并且稳定性良好。
同时，通过二分查找和跳跃式插入等优化方案可以进一步提高效率。
