java排序算法插入排序

Java中的插入排序（Insertion Sort）是一种简单的排序算法，其基本思想是将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置，以此方式将整个数组排序。

以下是一个使用Java实现插入排序算法的示例代码：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

在上面的代码中，insertionSort方法接受一个整数数组作为参数，使用嵌套的for循环来实现插入排序。外部循环迭代数组的第二个元素到最后一个元素，内部循环将当前元素与已排序部分中的元素进行比较，并在适当位置插入当前元素。最终，整个数组将被排序并输出。

插入排序的时间复杂度为O(n^2)，其中n是数组的大小。在最坏的情况下，即数组已经按相反的顺序排列，插入排序需要进行n(n-1)/2次比较和n(n-1)/2次移动。尽管插入排序的时间复杂度较高，但它可以在某些情况下比其他排序算法表现更好，例如在数组已经基本有序的情况下。此外，它的实现简单，容易理解，因此可以作为其他排序算法的基础。

插入排序还有一些优点和缺点：

优点：

简单：插入排序算法的实现非常简单，易于理解和实现。
稳定：插入排序是一种稳定的排序算法，即相等的元素之间的相对顺序不会发生改变。
适用于小型数组：插入排序对于小型数据集的排序表现很好，它的性能甚至可能比某些高级算法更优。

缺点：

时间复杂度高：插入排序的时间复杂度为O(n^2)，因此对于大型数据集的排序表现较差。
不适合链表：插入排序需要对数组进行随机访问，因此不适用于链表等不支持随机访问的数据结构。
不适合逆序的数组：插入排序对于已经排序的数据集表现良好，但对于逆序的数据集表现不佳。

总的来说，插入排序是一种简单、稳定、适用于小型数据集的排序算法。它可能不是最快的排序算法，但是它容易实现，并且在某些情况下可能比其他算法表现更好。

原文链接：codingdict.net

java排序算法 插入排序

热门标签

java排序算法插入排序