排序算法----插入和希尔排序
1、插入排序
插入排序的基本思想：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有 序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排 序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
1.1、插入排序代码实现
public static int[] insertSort(int[] initial) {
/**
* 冒泡排序核心代码
*/
//temp临时变量
int temp;
//要插入的位置的下标
int index = 0;
/**
* 代表遍历N-1遍,因为i从1开始，所以长度不需要-1
*/
for (int i = 1; i < initial.length; i++) {
//每次都将要插入的元素，存到临时变量中
temp = initial[i];
//将要插入的元素，和要插入的元素的前一个数开始比较，直到要插入的元素，大于当前比较的元素
for (index = i - 1; index >= 0 && initial[index] > temp; index--) {
//从有序的数组最后一位开始，一个一个往后移动
initial[index + 1] = initial[index];
}
/**
* 当前元素比要插入的元素小时，代表已经找到了要插入的位置
* 因为找到的index所对应的值，是比要插入的元素还要小，所以要插入的元素，要插到当前index的后面，所以要index+1
*/
initial[index + 1] = temp;
}
return initial;
}1.2 插入排序存在的问题
*当排在最后的数是较小的数时，后移的次数明显增多，对效率存在很大的影响.，因此，通常把希尔排序称为插入排序的优化版本
2、希尔排序
希尔排序的基本思想：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含 的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止
2.1、希尔排序代码实现
/**
* 希尔排序：通常认为是插入排序的优化版
* 第一次：将元素个数/2，得到分组的个数，将每个分组里面的元素进行比较，如果下标小的元素，值比下标大的元素要大，则两个数进行交换
* 第二次：将上一次的 组数/2，得到新的分组数量，将每组中小的元素放到前面，大的放到后面
* 依次重复上面的操作，直到 上一组/2 = 1，则得到排序后的结果
* 简单来说：就是把数组里面的元素分成个数/2份，然后每一组里面的元素做插入排序，以此类推
* @param initial 要排序的数组
* @return 已排序好的数组
*/
public static int[] shellSort(int[] initial){
//temp临时变量
int temp;
//定义每一次的步长，也是分组的个数
int gap;
//插入排序中的位置的下标
int index;
for (gap = initial.length / 2; gap > 0; gap /= 2) {
//中间使用插入排序
for (int i = gap; i < initial.length; i += gap) {
temp = initial[i];
for (index = i - gap; index >= 0 && initial[index] > temp; index -= gap) {
initial[index + gap] = initial[index];
}
initial[index + gap] = temp;
}
}
return initial;
}