直接插入排序
1.从第一个元素开始，该元素可以认为已经被排序
2.取下一个元素tem，从已排序的元素序列从后往前扫描
3.如果该元素大于tem，则将该元素移到下一位
4.重复步骤3，直到找到已排序元素中小于等于tem的元素
5.tem插入到该元素的后面，如果已排序所有元素都大于tem，则将tem插入到下标为0的位置
例如：从数字5开始排序
时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)
代码：
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 1, 6};
System.out.println("Before sorting: " + Arrays.toString(arr));
insertionSort(arr);
System.out.println("After sorting: " + Arrays.toString(arr));
}
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i =0;j--){
//如果当前元素小于他前边的那个元素，当前这个元素目前所在位置放置他前一个元素
if(key希尔排序
1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
时间复杂度平均：O(N^1.3)
空间复杂度：O(1)
代码：
public static void main(String[] args) {
int[] a = {1,2,5,4,3,9};
ShellSort(a);
}
public static void ShellSort(int[] array)
{
int n = array.length;
int inc;//希尔增量
//这里采用朴素希尔增量，就是每次增量都是原来的一半，直到增量为1为止
for (inc = n / 2; inc >= 1; inc = inc / 2)
{//每一次循环都通过不断缩短增量达到排序的效果
//在一次循环内，inc的值是固定的
//下面的内容和插入排序的原理是一样的,只不过每个待排序元素的间隔是inc
for (int i = inc; i = 0 && array[j] > temp; j = j - inc)
{//j从i-inc开始往前遍历，每一步的距离是inc
array[j+inc] = array[j];//如果当前遍历到的元素(这里说的遍历到的元素是(array[j])比待插入元素temp小，
//这个元素往后移动一位，后边的元素被元素覆盖
//一旦不满足条件，1.说明要么遍历到元素比temp小，这个时候所有比temp大的元素都后移完了
//2.遍历到头了，此时第一个元素就是要插入的地方
}
array[j+inc] = temp;
//那么此时array[j+inc]也就是要插入的地方，把temp插入进去
System.out.println(Arrays.toString(array));
}
}
// System.out.println(Arrays.toString(array));
}直接选择排序
每次从待排序列中选出一个最小值，然后放在序列的起始位置，直到全部待排数据排完即可。
实际上，我们可以一趟选出两个值，一个最大值一个最小值，然后将其放在序列开头和末尾，这样可以使选择排序的效率快一倍。
public static void main(String[] args) {
int arrLength = 8; //测试数组的长度
/*
* 获得随机arrLength个数的数组
*/
int[] arr = new int[arrLength];
for(int i = 0;i arr[j]){
min=j; //记住最小元素下标
}
}
//一轮后，当最小元素的下标不为i时交换位置
if(min != i){
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
System.out.println(Arrays.toString(arr));
}
}服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
