Java实现几种常见排序算法代码

Java实现几种常见排序算法代码

在本文中，我们将介绍 6 种常见的排序算法的 Java 代码实现，这些排序算法分别是：

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 快速排序
5. 归并排序
6. 堆排序

为了方便说明，我们将在每个排序算法的代码实现中使用一个简单的示例数组 arr，用于展示排序前与排序后的结果。示例代码如下：

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

冒泡排序

冒泡排序的原理是比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置，直到没有任何一对数字需要比较。

以下是 Java 代码实现：

for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

经过冒泡排序后，arr 数组的结果如下：

{1, 2, 3, 5, 8, 9}

选择排序

选择排序的原理是每次从未排序的元素中选择最小的元素，将其放到已排序数列的末尾。

以下是 Java 代码实现：

for (int i = 0; i < arr.length - 1; i++){
    int minIndex = i;
    for (int j = i + 1; j < arr.length; j++){
        if (arr[j] < arr[minIndex]){
            minIndex = j;
        }
    }
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

经过选择排序后，arr 数组的结果如下：

{1, 2, 3, 5, 8, 9}

插入排序

插入排序的原理是将未排序的元素插入到已排序部分的正确位置中。

以下是 Java 代码实现：

for (int i = 1; i < arr.length; i++) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
    }
    arr[j + 1] = key;
}

经过插入排序后，arr 数组的结果如下：

{1, 2, 3, 5, 8, 9}

快速排序

快速排序的原理是选择一个基准数，将小于基准数的元素放在它前面，大于基准数的元素放在它后面，不断重复这个过程直到整个数组排序完成。

以下是 Java 代码实现：

public static void quickSort(int[] arr, int start, int end) {
    if (start < end) {
        int partitionIndex = partition(arr, start, end);
        quickSort(arr, start, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, end);
    }
}

public static int partition(int[] arr, int start, int end) {
    int pivot = arr[end];
    int i = start - 1;
    for (int j = start; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[end];
    arr[end] = temp;
    return i + 1;
}

经过快速排序后，arr 数组的结果如下：

{1, 2, 3, 5, 8, 9}

归并排序

归并排序的原理是将数组一分为二，然后对两部分分别排序，最后将两个已排序的部分合并为一个已排序的部分。

以下是 Java 代码实现：

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

public static void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= high) {
        temp[k++] = arr[j++];
    }
    for (int x = 0; x < temp.length; x++) {
        arr[low + x] = temp[x];
    }
}

经过归并排序后，arr 数组的结果如下：

{1, 2, 3, 5, 8, 9}

堆排序

堆排序的原理是将数组构建为一个堆，然后取出堆顶元素（即最大元素），将剩余元素再构建为一个堆，再取出堆顶元素，重复这个过程直到整个数组排序完成。

以下是 Java 代码实现：

public static void heapSort(int[] arr) {
    int len = arr.length;
    for (int i = len / 2 - 1; i >= 0; i--) {
        heapify(arr, len, i);
    }
    for (int i = len - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

public static void heapify(int[] arr, int len, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < len && arr[l] > arr[largest]) {
        largest = l;
    }
    if (r < len && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, len, largest);
    }
}

经过堆排序后，arr 数组的结果如下：

{1, 2, 3, 5, 8, 9}