java实现排序算法(java排序方法)

插入排序的过程就像整理桥牌的过程；每次将待排元素中的第一个元素插入到有序区间的合适位置，为了给当前待排元素腾出位置，需要将有序区间内所有大于待排元素的元素都向右移动一位；
与选择排序一样，当前待排元素左边区间的元素是有序的，但是它们的位置并不确定，因为可能会被移动，当索引到达数组右端时，整个数组就有序了。

与选择排序不同，插入排序所需要的时间取决于输入时元素的顺序；若初始数据越接近有序，则排序时间效率就越高，所以插入排序经常用于高阶排序算法的优化手段之一。

    public static void insertionShort(int[] arr) {
        //[0,i]为有序区间
        //[j,arr.length)为无序区间
        //j指向当前待排的那个元素
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                //在区间[0,i]内搬移元素至合适位置
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }else {
                    //说明此时包含新插入的元素的左区间已经有序，直接排下一个元素
                    break;
                }
            }
        }
    }

在有序区间选择数据应该插入的位置时，因为区间的有序性，可以利用二分查找的思想定位元素位置。在数据量大且不重复的情况下，折半插入排序速度远快于直接插入排序

    public static void insertionShortHalf(int[] arr) {
        int len = arr.length;
        //[0,i]为有序区间
        //[i+1,len)为无序区间
        for (int i = 0; i < len - 1; i++) {
            //left指向有序区间第一个元素
            int left = 0;
            //right指向无序区间第一个元素，即待插元素
            int right = i + 1;
            //待插元素值
            int value = arr[right];
            //出了循环，left所指就是待插位置
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (arr[mid] > value) {
                    right = mid;
                }else{
                    left = mid + 1;
                }
            }
            //[left,i]区间所有元素向右搬移一位
            for (int j = i + 1; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            //待排元素归位
            arr[left] = value;
        }
    }