Java数据结构之插入排序与希尔排序

插入排序

插入排序是一种简单而有效的排序算法。它的基本思想是将一个元素插入已经排好序的部分中。插入排序的过程可以用以下伪代码表示：

for i=1 to length-1
   j = i
   while j > 0 and array[j-1] > array[j]
       swap array[j] and array[j-1]
       j = j - 1

插入排序的实现比较简单，可以用两个for循环来实现。以下是Java实现代码：

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;
    }
}

希尔排序

希尔排序是一种改进的插入排序算法，也称为“缩小增量排序”。它通过将原始序列分成若干个子序列来加快插入排序的速度。与插入排序不同的是，希尔排序首先对相距一定间隔的元素进行排序，然后逐步减小间隔，继续进行排序，直到间隔为1为止。

希尔排序的实现比较复杂，需要用到递归和循环。以下是Java实现代码：

public static void shellSort(int[] arr) {
    int n = arr.length;
    int gap = n / 2;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
        gap /= 2;
    }
}

实例说明

以下是两个实例说明，分别是对一个整型数组和一个字符串数组进行插入排序。

整型数组插入排序

假设有一个整型数组arr，其内容如下：

int[] arr = {3, 7, 4, 9, 5, 2, 6, 1, 8};

使用插入排序对其进行排序，可以得到以下结果：

int[] sorted = {1, 2, 3, 4, 5, 6, 7, 8, 9};

字符串数组插入排序

假设有一个字符串数组strArr，其内容如下：

String[] strArr = {"orange", "banana", "apple", "mango", "pear"};

使用插入排序对其进行排序，可以得到以下结果：

String[] sorted = {"apple", "banana", "mango", "orange", "pear"};

以上是使用插入排序对整型数组和字符串数组进行排序的实例说明，同样的操作也可以应用于希尔排序。