Java数据结构之常见排序算法（下）

前言

这是 Java 数据结构之常见排序算法的第二篇，本篇文章将继续介绍常见的排序算法。对于尚未了解基本排序算法的读者，可以先阅读 Java 数据结构之常见排序算法（上）。

快速排序

快速排序是一种使用分治思想的排序算法，其思路是将一个数组分为两个子数组，再对子数组进行排序，这个过程不断递归执行。在具体实现时，选择一个元素作为基准值，将所有小于基准值的数放在基准值左侧，将所有大于等于基准值的数放在基准值右侧，然后分别以左右子数组为输入递归执行该过程。

快速排序的时间复杂度为 O(NlogN)（平均情况下），空间复杂度为 O(logN)。需要注意的是，如果选择基准值不合适，快排的时间复杂度可能会退化成 O(N^2)，但这种情况比较少见，且可以通过随机化选择基准值来避免。

以下是使用 Java 实现的快排算法的示例代码：

public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) {
        return;
    }
    // 选择基准值
    int pivot = arr[start];
    // 定义左右指针
    int left = start + 1, right = end;
    // 循环直到左右指针重合
    while (left <= right) {
        // 将左指针指向的数大于基准值的数换到右指针指向的位置
        while (left <= right && arr[left] < pivot) {
            left++;
        }
        // 将右指针指向的数小于等于基准值的数换到左指针指向的位置
        while (left <= right && arr[right] >= pivot) {
            right--;
        }
        if (left < right) {
            swap(arr, left, right);
        }
    }
    // 将基准值换到左指针指向的位置
    swap(arr, start, right);
    // 递归对左右子数组进行排序
    quickSort(arr, start, right - 1);
    quickSort(arr, right + 1, end);
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

归并排序

归并排序是一种使用分治思想的排序算法，其思路是将一个数组分为两个子数组，分别对它们进行排序，然后将排序后的两个子数组合并成一个有序的数组。在具体实现时，可以使用递归算法，对于一个长度为 N 的数组，将其不断二分并递归执行归并排序，直到排序完整个数组。

归并排序的时间复杂度为 O(NlogN)，空间复杂度为 O(N)。与快速排序不同，归并排序是一种稳定的排序算法。

以下是使用 Java 实现的归并排序算法的示例代码：

public static void mergeSort(int[] arr, int start, int end) {
    if (start >= end) {
        return;
    }
    int mid = (start + end) >> 1;
    // 递归对左右子数组进行排序
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    // 合并左右子数组
    int[] tmp = new int[end - start + 1];
    int i = start, j = mid + 1, k = 0;
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= end) {
        tmp[k++] = arr[j++];
    }
    // 将合并后的数组复制回原数组
    for (int l = start, m = 0; l <= end; l++, m++) {
        arr[l] = tmp[m];
    }
}

总结

本篇文章介绍了常见的两种排序算法，快速排序和归并排序，它们分别具有不同的特点和适用场景。同时，本篇文章通过示例代码演示了这两种排序算法的具体实现方法，希望能帮助读者更好地理解和掌握它们。