欢迎大家来到IT世界,在知识的湖畔探索吧!

Java排序算法主要分为两类：比较排序和非比较排序。

比较排序

比较排序是指通过比较元素之间的大小关系来进行排序的算法。

以下是常见的比较排序算法：

• 冒泡排序（Bubble Sort）
• 选择排序（Selection Sort）
• 插入排序（Insertion Sort）
• 希尔排序（Shell Sort）
• 快速排序（Quick Sort）
• 归并排序（Merge Sort）
• 堆排序（Heap Sort）

非比较排序

非比较排序是指不通过比较元素之间大小关系来进行排序的算法。

以下是常见的非比较排序算法：

• 计数排序（Counting Sort）
• 桶排序（Bucket Sort）
• 基数排序（Radix Sort）

在实际应用中，常用的排序算法有冒泡排序、选择排序、插入排序、快速排序和归并排序。其中，快速排序和归并排序是比较常用的高效排序算法。

下面的代码将会向大家演示相关概念和实现

冒泡排序

冒泡排序是一种基本的排序算法，它通过不断交换相邻的元素将较大的元素“浮”到数组的顶部，而较小的元素则“沉”到数组的底部。

以下是 Java 实现冒泡排序的代码：

  /**
     * 冒泡排序
     @param arr 传递的数组
     */
public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换相邻的元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

欢迎大家来到IT世界,在知识的湖畔探索吧!/** 主方法测试  */
public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}

在这个代码中，外层循环控制排序的轮数，内层循环控制每一轮的比较和交换。如果相邻的元素顺序不正确，就交换它们。由于每一轮都会将未排序部分的最大元素移动到已排序部分的末尾，所以内层循环每次都要减少一次比较的次数。最终，经过 n-1 轮排序后，数组就按照从小到大的顺序排好了。

选择排序

选择排序是一种简单的排序算法，它的思想是每一次从待排序的元素中选择最小（或最大）的一个元素，放到已排序部分的末尾。

以下是 Java 实现选择排序的代码：

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        // 从未排序的部分中找到最小元素的下标
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 将最小元素与未排序部分的第一个元素交换
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

在这个代码中，外层循环控制排序的轮数，内层循环在未排序的部分中查找最小元素的下标，然后将最小元素与未排序部分的第一个元素交换。由于每一轮都会将未排序部分的最小元素移动到已排序部分的末尾，所以内层循环的起始位置每次都要加一。最终，经过 n-1 轮排序后，数组就按照从小到大的顺序排好了

可以使用以下代码测试上述算法

欢迎大家来到IT世界,在知识的湖畔探索吧!public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    selectionSort(arr);
    System.out.println(Arrays.toString(arr));
}

快速排序

快速排序是一种基于分治思想的高效排序算法，它通过不断划分数组为两个子数组，然后分别对子数组进行排序，最终将子数组合并起来得到有序的数组。

以下是 Java 实现快速排序的代码：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left + 1, j = right;
    while (i <= j) {
        if (arr[i] < pivot && arr[j] > pivot) {
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
        if (arr[i] >= pivot) {
            i++;
        }
        if (arr[j] <= pivot) {
            j--;
        }
    }
    // 将枢轴元素和 arr[j] 交换
    arr[left] = arr[j];
    arr[j] = pivot;
    return j;
}

在这个代码中，快速排序算法采用了递归实现。

首先，将数组划分为两个子数组，然后递归地对每个子数组进行排序，最后将排序好的子数组合并起来。其中，划分子数组的过程称为分区（partition），它的目的是将数组分成比枢轴元素小和大的两个部分。

具体实现中，我们选取数组的第一个元素作为枢轴元素，然后使用两个指针 i 和 j 分别从左到右和从右到左遍历数组，交换 i 和 j 指向的元素，直到 i 和 j 相遇为止。最后将枢轴元素和 arr[j] 交换，返回 j 作为下一次递归的分割点。

归并排序

归并排序是一种基于分治思想的高效排序算法，它通过将待排序数组分为两个子数组，对每个子数组进行递归排序，然后将两个有序子数组合并成一个有序数组。

以下是 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++];
    }
    // 将临时数组中的元素拷贝回原数组
    for (i = left, k = 0; i <= right; i++, k++) {
        arr[i] = temp[k];
    }
}

在这个代码中，归并排序算法采用了递归实现。

首先，将待排序数组分为两个子数组，然后递归地对每个子数组进行排序，最后将排序好的子数组合并起来。

其中，合并子数组的过程称为归并（merge），它的目的是将两个有序的子数组合并成一个有序数组。

具体实现中，我们使用一个临时数组 temp 存储归并结果，同时使用三个指针 i、j 和 k 分别指向左子数组、右子数组和临时数组，比较左右子数组的元素大小，并将较小的元素拷贝到临时数组中。最后，将临时数组中的元素拷贝回原数组中相应位置。

插入排序

插入排序是一种简单直观的排序算法，它的基本思想是将待排序的元素插入到已经排序好的序列中的合适位置。

以下是 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;
    }
}

在这个代码中，插入排序算法采用了迭代实现。首先，从待排序数组的第二个元素开始遍历，将其插入到已经排序好的子数组中的合适位置。

具体实现中，我们将第 i 个元素存储在变量 key 中，然后将指针 j 指向 i 的前一个位置。接着，我们将 key 与已排序的子数组中的每一个元素逐个比较，如果该元素大于 key，则将该元素后移一位，直到找到一个合适的位置将 key 插入。最后，将 key 插入到正确的位置。

可以使用以下代码测试上述算法：

public static void main(String[] args) {
    int[] arr = {64, 34, 25, 12, 22, 11, 90};
    insertionSort(arr);
    System.out.println(Arrays.toString(arr));
}