内部排序
-插入排序
-直接插入排序
-折半插入排序
-希尔排序
-交换排序
-冒泡排序
-快速排序
-选择排序
-简单选择排序
-堆排序
-归并排序
-基数排序
外部排序
-多路归并排序
1.直接插入排序
算法思路：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，指导全部记录插入完成。
性能分析：
空间复杂度O(1)
时间复杂度O(n^2)
算法稳定
适用于顺序表和链表，使用链表的时候可以重前向后查找插入位置
void InsertSort(int arr[],int n){ int i,j; for(int i=2;i<=n;i++){ // arr[0]不存内容，从1开始存起，arr[0]后面会作为哨兵使用 if(arr[i]<arr[i-1]){ arr[0]=arr[i]; for(int j=i-1;arr[0]<arr[j],j--){ arr[j+1]=arr[j]; } arr[j+1]=arr[0]; } } }
2.折半插入排序
算法思路：和插入排序一样，只是在查找插入位置的时候采用折半查找找到插入位置，找到以后一次性移动元素。注意这里采用的是折半查找，因此这种排序算法只适用于顺序表。
算法时间复杂度：O(n^2)
void InsertSort_Binary_Search(int arr[],int n){ int i,j,low,heigh; for(i=2;i<=n;i++){ arr[0]=arr[i]; low=1; heigh=i-1; while(low<=heigh){ int mid=(low+heigh)/2; if(arr[mid]>arr[0]) heigh=mid-1; else //mid<=arr[0]的时候low=mid+1保证算法的稳定性 low=mid+1; } for(j=i;j>low;j--){ arr[j]=arr[j-1]; } arr[low]=arr[0]; } }
3.希尔排序
分析：插入排序在序列初始基本有序的时候，算法时间复杂度接近O(N)，希尔排序正式基于这一点改进而来的
思路：把待排序序列中的元素按照[i,i+d,i+2d...]分为若干个子表对每个子表进行直接插入排序，不断降低d的大小，使表基本有序，然后采用一次插入排序，即d取1.希尔提出的d取d1=n/2,di=d(i-1)/2(向下取整)。
性能分析：
空间复杂度O(1)
当n在某个范围时，时间复杂度O(n^1.3)，最坏情况下O(n^2)
由于相同关键字会划分到不同子表，因此不稳定。
仅适用于顺序存储。
void ShellSort(int arr[],int n){ for(int d=n/2;d>=1;d=d/2){ for(int i=d+1;i<=n;i++){ if(arr[i]<arr[i-d]){ arr[0]=arr[i]; //arr[0]不是哨兵，只是用来暂存数据元素 int j; for(j=i-d;arr[j]>arr[0]&&j>0;j-=d){ arr[j+d]=arr[j]; } arr[j+d]=arr[0]; } } } }
原文：https://www.cnblogs.com/foodie-nils/p/13181543.html