java插入排序 Insert sort实例

下面我将详细讲解如何实现Java的插入排序算法。

插入排序 Insert Sort

插入排序是一种简单直观的排序算法，它的基本思想是将未排序的数据依次插入到已排序数据中的合适位置，使得插入后序列仍然有序。

插入排序的算法步骤如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

插入排序有两种实现方式，分别为直接插入排序和二分插入排序。下面我们来详细介绍这两种实现方式。

直接插入排序

直接插入排序是一种最简单的实现方式。它的核心思想是将未排序的元素依次插入到已排序的序列中的合适位置。

代码示例：

/**
 * 直接插入排序实现
 * @param array 待排序数组
 */
public static void insertSort(int[] array) {
    int i, j, temp;
    for (i = 1; i < array.length; i++) {
        temp = array[i];
        for (j = i - 1; j >= 0; j--) {
            if (array[j] > temp) {
                array[j + 1] = array[j];
            } else {
                break;
            }
        }
        array[j + 1] = temp;
    }
}

直接插入排序的时间复杂度为 $O(n^{2})$，空间复杂度为 $O(1)$。在实际应用中，直接插入排序在小规模数据的排序中性能表现较好，在数据量比较大的情况下表现较差。

二分插入排序

二分插入排序是直接插入排序的一种改进方式。它的核心思想是使用二分查找的策略来寻找待排序元素在已排序数组中的合适位置。

代码示例：

/**
 * 二分插入排序实现
 * @param array 待排序数组
 */
public static void binaryInsertSort(int[] array) {
    int i, j, left, right, mid, temp;
    for (i = 1; i < array.length; i++) {
        temp = array[i];
        left = 0;
        right = i - 1;
        while (left <= right) {
            mid = (left + right) / 2;
            if (temp < array[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        for (j = i - 1; j >= left; j--) {
            array[j + 1] = array[j];
        }
        array[left] = temp;
    }
}

二分插入排序的时间复杂度同样为 $O(n^{2})$，但是它的时间常数比直接插入排序略小。在实际应用中，二分插入排序在大规模数据的排序中性能表现较好。

示例说明

假设我们有一个整数数组，数组元素为 [3, 5, 1, 4, 2] ，如果我们使用直接插入排序算法进行排序，那么排序后的数组应该为 [1, 2, 3, 4, 5] 。下面是一个Java实现的示例：

public class InsertSortExample {
    public static void main(String[] args) {
        int[] array = {3, 5, 1, 4, 2};
        System.out.println("排序前：" + Arrays.toString(array));
        insertSort(array);
        System.out.println("排序后：" + Arrays.toString(array));
    }
}

如果我们使用二分插入排序算法进行排序，那么排序后的数组依然为 [1, 2, 3, 4, 5] 。下面是一个Java实现的示例：

public class BinaryInsertSortExample {
    public static void main(String[] args) {
        int[] array = {3, 5, 1, 4, 2};
        System.out.println("排序前：" + Arrays.toString(array));
        binaryInsertSort(array);
        System.out.println("排序后：" + Arrays.toString(array));
    }
}

以上就是关于Java插入排序的完整攻略及示例说明。