📚 选择排序和插入排序区别-DS笔记

选择排序法

A[i...n)未排序，A[0...i)已排序
A[i...n]中最小值要放到A[i]的位置

复杂度 \(O(n^2)\)

第一层循环n次

第二层循环：i=0，n次；i=1，n-1次......i=n-1，1次。即1+2+3+...+n

public static void sort(int[] arr) {

    for (int i = 0; i < arr.length; i++) {

        int minIdx = i;

        // 选择A[i...n]中的最小值的索引

        for (int j = i; j < arr.length; j++) {

            if (arr[j] < arr[minIdx])

                minIdx = j;

        }

        swap(arr, i, minIdx);

    }

}

/* 使用带约束的泛型 */

public static <E extends Comparable<E>> void sort(E[] arr) {

        for (int i = 0; i < arr.length; i++) {

            int minIdx = i;

            for (int j = i; j < arr.length; j++) {

                if (arr[j].compareTo(arr[minIdx]) < 0)

                    minIdx = j;

            }

            swap(arr, i, minIdx);

        }

}

比较引用类型必须要实现Comparable 接口！

插入排序

A[i...n)未排序，A[0...i)已排序

将arr[i]插入适当的位置
整体复杂度 \(O(n^2)\)

对于有序数组，插入排序的复杂度是\(O(n)\)

public <E extends Comparable<E>> void insertSort(E[] arr) {

    for (int i = 0; i < arr.length; i++) {

        // 将arr[i]插入适当的位置

        for (int j = i; j-1 >= 0; j--)

            if (arr[j].compareTo(arr[j-1]) < 0)

                swap(arr, j, j-1);

        	else break;

    }

}

/* 小优化 */

public <E extends Comparable<E>> void insertSort2(E[] arr) {

    for (int i = 0; i < arr.length; i++) {

        int t = arr[i];  // 暂存arr[i]

        int j;

        for (j = i; j-1>=0 && t.comparaTo(arr[j-1]) < 0) {

            arr[j] = arr[j-1];  // 向后移动元素

        }

        arr[j] = t;

    }

}

区别：

选择排序：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

插入排序：将元素逐个插入到有序排列之中，其特点是要不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去

巴特西

📚 选择排序和插入排序区别-DS笔记

选择排序法

插入排序

最新文章

热门文章