在将n个元素的序列进行升序或者降序排列，采用插入排序最好情况就是序列已经是有序的了，在这种情况下，需要进行的比较操作需n-1次即可。最坏情况就是序列是反序的，那么此时需要进行的比较共有n(n-1)/2次。平均来说插入排序算法复杂度为 O(n^2)。所以插入排序不适合对于数据量比较大的排序应用。但是在需要排序的数据量很小或者若已知输入元素大致上按照顺序排列，插入排序的效率还是不错。
带哨兵的插入排序
在插入排序的时候，我们看到每一次进行比较都有两次比较操作j>=0&&temp<nums[j]，即既要保证不越界又要判断数据是否符合条件，假设在反序的情况下就几乎多出一倍的比较次数。这里我们使用一个哨兵来消除掉多的比较操作。
代码
public static void insertWithSentinelSort(int[] nums){
int i,j;
for(i=1;i<nums.length;i++){
//将第一个元素指定为哨兵
//要求传入的数组比原数组长度大1
nums[0] = nums[i];
//将元素后移
//这里只需比较数据是否符合条件
for(j=i-1;nums[j]>nums[0];j--){
nums[j+1] = nums[j];
}
nums[j+1] = nums[0];
}
}
添加哨兵的好处就是将原本的比较次数减少，提高了算法效率。
希尔排序
希尔排序是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定的步长进行分组，对每组数据使用直接插入排序算法排序；随着步长逐渐减少，每组包含的关键词越来越多，当步长为1时，刚好就是一个插入排序。而在此时整个数据序列已经基本有序，插入排序在对几乎已经排好序的数据操作时，效率高，可以达到线性排序的效率。所以希尔排序的整体效率较高。
希尔排序的步骤：
1.选择步长大小，根据步长将数据分组
2.循环对每一组进行排序
3.修改步长的大小(一般为一半，也可以通过步长数组指定)，重复1-2操作
4.直到步长为1进行排序后停止
代码
public static void shellSort(int[] nums){
int size = nums.length/2;
int i,j;
while(size>=1){
for(i=0;i<nums.length;i++){
for(j=i;j+size<nums.length;j+=size){
if(nums[j]>nums[j+size]){
swap(nums, j, j+size);
}
}
}
size/=2;
}
}
复杂度
希尔排序的时间复杂度分析比较复杂，因为它和所选取的步长有着直接的关系。步长的选取没有一个统一的定论，只需要使得步长最后为1即可。希尔排序的时间复杂度根据所选取的步长不同时间复杂度范围在o(n^1.3)~o(n^2)。
快速排序
快速排序是对冒泡排序的改进。
快排的基本步骤：
1.从待排序列中选取一个数(一般为第一个)，进行一次排序，将大于该数的放在该数前面，小于该数的放在其后面。
2.上述操作将待排序列分为两个独立的部分，递归的进行上面的操作，直到序列无法再被分割。
3.最后一次排序后序列中是有序的。
代码
public static void quickSort(int[] nums, int low, int high){
if(low<high){
int partation = partition(nums, low, high);
//这里返回的low值的位置已经确定了 所以不用参与排序
quickSort(nums, 0, low-1);
quickSort(nums, low+1, high);
}
}
//进行一次排序 将待排序列分为两个部分
public static int partition(int[] nums, int low, int high){
//选取第一个值为枢纽值
int pivo = nums[low];
while(low<high){
while(low<high&&nums[high]>=pivo){
high--;
}
nums[low] = nums[high];
while(low<high&&nums[low]<=pivo){
low++;
}
nums[high]=nums[low];
}
nums[low] = pivo;
return low;
}
复杂度
时间复杂度
在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归的深度就为log2n+1，即仅需递归log2n 次。时间复杂度为O(nlogn)。