Java实现插入排序,希尔排序和归并排序

Java实现插入排序、希尔排序和归并排序

插入排序

插入排序算法的思路是：将一个待排序的数组（序列）分为两部分，前面的有序序列和后面的无序序列，将无序序列中的每一个元素插到有序序列中的适当位置，直到无序序列为空。

Java代码实现：

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

示例：

int[] arr = {5, 3, 8, 6, 4};
insertionSort(arr);
System.out.println(Arrays.toString(arr)); // 打印结果：[3, 4, 5, 6, 8]

希尔排序

希尔排序（Shell Sort）是插入排序的一种改进版本，它的基本思路是将待排序的数组元素按下标序号一定增量分组，对每个分组应用插入排序算法排序，然后逐步缩小增量，再次对分组进行排序，直到增量为1时完成最后一次排序。

Java代码实现：

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

示例：

int[] arr = {5, 3, 8, 6, 4};
shellSort(arr);
System.out.println(Arrays.toString(arr)); // 打印结果：[3, 4, 5, 6, 8]

归并排序

归并排序（Merge Sort）也是一种分治算法，它的基本思路是：将一个待排序的数组不断递归分解为两个子序列，每个子序列都是有序的，然后将两个子序列合并成一个有序的序列。

Java代码实现：

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    System.arraycopy(temp, 0, arr, left, temp.length);
}

示例：

int[] arr = {5, 3, 8, 6, 4};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // 打印结果：[3, 4, 5, 6, 8]

以上就是Java实现插入排序、希尔排序和归并排序的详细攻略，希望对你有所帮助。