Java插入排序的研究

傷城~ 2022-05-18 01:58 128阅读 0赞

算法导论原书第三版中这样介绍插入排序：

对于少量的元素的排序，他是一个有效的算法，插入排序的工作方式就像许多人排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中的正确位置。为了找到一张牌的正确位置，我们从右到左将它与已在自己手中的每张牌进行比较。

下面给出他们给出的伪代码

![70][]

根据伪代码再结合咱们强大的Java编程语言，可以这样实现它。

public class Sort {
    
        public static void main(String[] args) {
            int[] arr = {55, 98, 67,23, 54, 66};
            System.out.println("初始化关键字");
            printArray(arr);
            System.out.println();
            insertSort(arr);
            System.out.println("排序后的结果");
            printArray(arr);
    
        }
        /**
         * 插入排序方法
         * @param arr
         */
        public static  void insertSort(int[] arr){
            int i,j,key;
            for ( i =1; i < arr.length; i++){
                //假设第一个数据是排好序的，从数组中的第二个数据开始
                    key = arr[i];
                    j = i-1;
                    //如果要插入的数据小于第j个数据，则将key往前移动插入
                while ( j >= 0 && key < arr[j]){
                    arr[j+1] = arr[j];
                    j--;
                }
                arr[j + 1] = key;
                //打印每次排序后的结果
                System.out.println("第" + i + " 次排序的结果");
                printArray(arr);
            }
    
        }
        /**
         * 打印数组方法
         * @param arr
         */
        private static void printArray(int[] arr){
            for (int i : arr){
                System.out.print("\t" + i);
            }
            System.out.println();
        }
    }

打印的结果如下：

![70 1][]

算法分析：

看上边的肯定能分析出来，咱就不分析了。

效率分析：

插入排序存在最好和最坏的情况，如果你想使用插入排序降序，而刚好需要要排序的序列是降序的，那只需要比较n-1次

如果想使用插入序列升序，而需要排序的序列为降序，那就需要比较n(n-1)/2次。

插入排序不适合数据量比较大的排序应用。

[70]: /images/20220518/e86562d64d35447eacf5d3f57a7b368d.png
[70 1]: /images/20220518/a3cd36bb8a134f89ae8f43a31a7b6321.png