Java超详细整理讲解各种排序

本文详细讲解了Java中各种排序算法的实现方式及其时间复杂度。本文内容包括以下几个部分：

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

排序算法分类

Java中的排序算法可以按照时间复杂度从小到大分为以下三类：

1. 时间复杂度为O(n^2)的算法：冒泡排序、插入排序、选择排序
2. 时间复杂度为O(nlogn)的算法：归并排序、快速排序、堆排序
3. 时间复杂度为O(n)的算法：桶排序、计数排序、基数排序

本文将主要讲解前两类排序算法。

冒泡排序

冒泡排序的实现方式很简单，每次比较相邻两个元素，如果左边的元素大于右边的元素则交换位置。需要进行多次遍历，每次遍历找到一个未排序元素中最大的元素并放到末尾。

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

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

下面我们用一个示例说明冒泡排序的过程。假设原数组为{5,3,8,6,4}，则冒泡排序的过程如下：

1. 5和3比较，交换位置，得到{3,5,8,6,4}
2. 5和8比较，不交换位置，得到{3,5,8,6,4}
3. 8和6比较，交换位置，得到{3,5,6,8,4}
4. 8和4比较，交换位置，得到{3,5,6,4,8}
5. 3和5比较，不交换位置，得到{3,5,6,4,8}
6. 5和6比较，不交换位置，得到{3,5,6,4,8}
7. 6和4比较，交换位置，得到{3,5,4,6,8}
8. 6和8比较，不交换位置，得到{3,5,4,6,8}
9. 3和5比较，不交换位置，得到{3,5,4,6,8}
10. 5和4比较，交换位置，得到{3,4,5,6,8}
11. 5和6比较，不交换位置，得到{3,4,5,6,8}
12. 6和8比较，不交换位置，得到{3,4,5,6,8}

最终得到了有序数组{3,4,5,6,8}。

插入排序

插入排序的实现方式也很简单，将未排序元素逐个插入到已排序数组的正确位置。需要进行多次遍历，每次遍历找到一个未排序元素并插入到有序数组的正确位置。

插入排序的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;
    }
}

下面我们用一个示例说明插入排序的过程。假设原数组为{5,3,8,6,4}，则插入排序的过程如下：

1. 5不用处理，得到{5,3,8,6,4}
2. 3插入到5的前面，得到{3,5,8,6,4}
3. 8不用处理，得到{3,5,8,6,4}
4. 6插入到8的前面，得到{3,5,6,8,4}
5. 4插入到6的前面，得到{3,4,5,6,8}

最终得到了有序数组{3,4,5,6,8}。

总结

本文详细讲解了Java中三种时间复杂度的排序算法，分别是冒泡排序、插入排序和归并排序、快速排序、堆排序，其中包括排序算法的分类、Java实现代码和示例说明。在实际应用中，我们可以根据数据规模和性能要求的不同选择不同的排序算法。