Java排序算法完整代码实例详解

Java Sort排序算法是Java编程语言中一个非常重要的知识点，它允许开发者对数组或集合中的元素进行排序。排序是数据处理和分析中的常见操作，它能帮助我们整理数据，以便更容易地进行查找、搜索和合并等操作。 在Java中，排序通常由`java.util.Arrays`类和`java.util.Collections`类中的静态方法来实现。对于基本类型的数组，Java提供了`Arrays.sort()`方法进行快速排序。对于对象数组或者集合，排序稍微复杂一些，因为涉及到元素的比较，通常需要实现`java.lang.Comparable`接口或者提供`java.util.Comparator`接口的实现。 以下将详细介绍Java中几种常见的Sort排序算法实例代码，以及它们在不同场景下的应用。 1. 冒泡排序 冒泡排序是一种简单的排序算法，它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 ```java public static void bubbleSort(int[] array) { if (array == null || array.length < 2) { return; } for (int i = 0; i < array.length - 1; i++) { for (int j = 0; j < array.length - 1 - i; j++) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } ``` 2. 选择排序 选择排序算法是一种原址比较排序算法。工作原理是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 ```java public static void selectionSort(int[] array) { if (array == null || array.length < 2) { return; } for (int i = 0; i < array.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[minIndex]) { minIndex = j; } } if (minIndex != i) { int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } } } ``` 3. 插入排序 插入排序的工作方式像许多人排序一副扑克牌。开始时，我们的左手为空；然后从右手取出一张牌，并将它插入到左手中的正确位置。为了找到这张牌的正确位置，我们可能需要从左手中的最后一张牌开始比较，依次向前比较，直到找到一个小于或等于它的牌，或者找不到这样的牌为止。 ```java public static void insertionSort(int[] array) { if (array == null || array.length < 2) { return; } for (int i = 1; i < array.length; i++) { int temp = array[i]; int j = i; while (j > 0 && temp < array[j - 1]) { array[j] = array[j - 1]; j--; } array[j] = temp; } } ``` 4. 快速排序 快速排序使用分治法策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。快速排序的平均时间复杂度为O(n log n)，但在最坏的情况下它的时间复杂度会退化为O(n^2)。 ```java public static void quickSort(int[] array, int low, int high) { if (low >= high) { return; } int pivot = partition(array, low, high); quickSort(array, low, pivot - 1); quickSort(array, pivot + 1, high); } private static int partition(int[] array, int low, int high) { int pivot = array[low]; while (low < high) { while (low < high && array[high] >= pivot) { high--; } array[low] = array[high]; while (low < high && array[low] <= pivot) { low++; } array[high] = array[low]; } array[low] = pivot; return low; } ``` 5. 归并排序 归并排序是创建在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。 ```java public static void mergeSort(int[] array) { if (array == null || array.length < 2) { return; } int[] temp = new int[array.length]; mergeSort(array, temp, 0, array.length - 1); } private static void mergeSort(int[] array, int[] temp, int leftStart, int rightEnd) { if (leftStart >= rightEnd) { return; } int middle = (leftStart + rightEnd) / 2; mergeSort(array, temp, leftStart, middle); mergeSort(array, temp, middle + 1, rightEnd); mergeHalves(array, temp, leftStart, rightEnd); } private static void mergeHalves(int[] array, int[] temp, int leftStart, int rightEnd) { int leftEnd = (rightEnd + leftStart) / 2; int rightStart = leftEnd + 1; int size = rightEnd - leftStart + 1; int left = leftStart; int right = rightStart; int index = leftStart; while (left <= leftEnd && right <= rightEnd) { if (array[left] <= array[right]) { temp[index] = array[left]; left++; } else { temp[index] = array[right]; right++; } index++; } System.arraycopy(array, left, temp, index, leftEnd - left + 1); System.arraycopy(array, right, temp, index, rightEnd - right + 1); System.arraycopy(temp, leftStart, array, leftStart, size); } ``` 6. 堆排序 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的方法。 ```java public static void heapSort(int[] array) { if (array == null || array.length < 2) { return; } int heapSize = array.length; buildMaxHeap(array); while (heapSize > 1) { swap(array, 0, --heapSize); adjustDown(array, 0, heapSize); } } private static void buildMaxHeap(int[] array) { int heapSize = array.length; for (int i = (heapSize / 2) - 1; i >= 0; i--) { adjustDown(array, i, heapSize); } } private static void adjustDown(int[] array, int parent, int heapSize) { int child = 2 * parent + 1; while (child < heapSize) { if (child + 1 < heapSize && array[child] < array[child + 1]) { child++; } if (array[parent] < array[child]) { swap(array, parent, child); parent = child; child = 2 * parent + 1; } else { break; } } } private static void swap(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } ``` 以上便是Java Sort排序算法的几个常见实例代码，以及对应的实现原理和方法。了解这些排序算法对编程能力的提高有着重要的意义，因为它们是很多复杂算法和数据结构的基础。在实际开发中，Java开发者可以利用Java内置的排序方法，但在特定场景下，理解并实现特定的排序算法将有助于优化程序性能。