数据结构--java语言实现插入排序

目录

1 基本思想

2 实现

2.1 直接插入排序

2.2 希尔排序

---

1 基本思想

把待排序的记录按其关键码值的大小逐个插入到一 个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。当只有一个记录时，该记录就记为有序序列，从第二个数开始进行插入排序。

2 实现

2.1 直接插入排序

当插入元素arr[i](i>=1)时，假设前面的arr[0],arr[1],...arr[i-1]这些元素已排好序，只需将arr[i]与arr[i-1],arr[i-2]...进行数码的比较，找到合适的位置插入即可。如图所示：

解决方法：

将需要插入的元素与前面元素进行比较：将该元素记录下来，与前面所有元素逐一比较，找到合适的位置插入即可。

代码实现：

public static void insertSort1(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int j = 0;
            //将待排序元素记录下来
            int tmp = arr[i];
            for (j = i-1; j > 0; j++) {
                if (arr[j] > tmp){
                    //将元素向后移
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            //将该元素放在arr[j+1]的位置
            arr[j+1] = tmp;
        }
    }

直接插入排序的特性总结：

• 越有序越快
• 时间复杂度：O(N)
• 空间复杂度：O(1)
• 稳定性：稳定 

2.2 希尔排序

又称缩小增量排序。是指将待排序的数据分成若干个组(组数依次递减)，所有距离相同的数据放在一个组中，在组内进行直接插入排序，是直接插入排序的优化。重复分组、排序操作，直到组数达到1的时候排序完成。以下用图来举例：

代码实现：

public static void shell(int[] array,int grp){
        for (int i = grp;i < array.length;i++){
            int j = 0;
            int temp = array[i];
            for (j = i-grp;j >= 0;j -= grp) {
                if (array[j] > temp){
                    array[j+grp] = array[j];
                }else {
                    //array[j+grp] = temp;
                    break;
                }
            }
            array[j+grp] = temp;//
        }
    }
    public static void shellSort(int[] array){
        int[] drr = {5,3,1};
        for (int i = 0; i < drr.length; i++) {
            shell(array,drr[i]);
        }
    }

 

希尔排序的特性总结：

• 时间复杂度：O(N^1.3~N^1.5)
• 空间复杂度：O(1)
• 稳定性：不稳定