Java排序算法详解及代码实现

Java作为一门广泛使用的编程语言，其内置的排序功能虽然已经足够高效，但在某些特殊场景下，开发者可能需要实现特定的排序算法以满足特定的性能要求或理解排序过程的原理。在本篇文档中，我们将详细介绍Java中常见的几种排序算法，并提供相应的代码实现。这些排序算法包括插入排序、交换排序、选择排序、归并排序以及分配排序，这些内容对于理解算法原理和提高编程能力都非常重要。 ### 插入排序 插入排序的核心思想是将数组分为已排序和未排序两部分，逐步将未排序部分的元素插入到已排序序列中。 #### 直接插入排序 直接插入排序是最简单直观的排序算法，它的工作方式是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。以下是直接插入排序的Java实现代码： ```java public static void insertionSort(int[] arr) { 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--; } arr[j + 1] = key; } } ``` #### 希尔排序 希尔排序是直接插入排序的一种更高效的改进版本，它先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。希尔排序的代码实现相对复杂，涉及到步长的选择。 ```java public static void shellSort(int[] arr) { int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int j = i; int current = arr[i]; while (j - gap >= 0 && current < arr[j - gap]) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = current; } } } ``` ### 交换排序 交换排序包括冒泡排序和快速排序，它们都是通过元素间比较和交换来完成排序。 #### 冒泡排序 冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。 ```java public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 交换两个元素的位置 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } ``` #### 快速排序 快速排序又称为分治排序，它采用的是分治法策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。快速排序的效率通常比冒泡排序要高得多。 ```java public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } private static int partition(int[] arr, int low, int high) { int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { low++; } arr[high] = arr[low]; } arr[low] = pivot; return low; } ``` ### 选择排序 选择排序算法是一种原址比较排序算法，它的工作原理是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 #### 直接选择排序 直接选择排序是通过把排序序列分割成未排序区间和已排序区间来完成排序，每次从未排序区间选出最小（或最大）元素放到已排序区间。 ```java public static void selectionSort(int[] arr) { 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; } } if (minIndex != i) { int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } } ``` #### 堆排序 堆排序是一种树形选择排序，在未排序序列中找到最大（或最小）元素，存放到堆的根节点；然后，再对堆的根节点进行一次调整，使之成为新的最大（或最小）堆。然后继续重复这个过程，直到所有元素均排序完毕。 ```java public static void heapSort(int[] arr) { // 构建最大堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { heapify(arr, arr.length, i); } // 一个个从堆顶取出元素 for (int i = arr.length - 1; i > 0; i--) { // 把最大堆的根节点放到数组末尾 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; heapify(arr, i, 0); } } private static void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } ``` ### 归并排序 归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 ```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]; } } ``` ### 分配排序 分配排序是通过把输入的元素分配到两个有序的输出序列中，然后将两个有序序列合并为一个有序序列的方法。 #### 箱排序（桶排序） 箱排序是将数组分到有限数量的桶里，每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用箱排序进行排序）。桶排序最好情况下可达到线性时间复杂度，但是实际情况下，它需要依赖于输入数据的分布特性。 ```java public static void bucketSort(int[] arr) { int max = arr[0]; int min = arr[0]; for (int value : arr) { if (value > max) { max = value; } if (value < min) { min = value; } } int bucketNum = (max - min) / arr.length + 1; int[][] buckets = new int[bucketNum][arr.length]; int[] buckectSize = new int[bucketNum]; for (int i = 0; i < arr.length; i++) { int index = (arr[i] - min) / arr.length; buckets[index][buckectSize[index]++] = arr[i]; } int index = 0; for (int i = 0; i < buckets.length; i++) { if (buckectSize[i] > 0) { insertionSort(buckets[i], 0, buckectSize[i] - 1); for (int j = 0; j < buckectSize[i]; j++) { arr[index++] = buckets[i][j]; } } } } ``` #### 基数排序 基数排序也是分配排序的一种，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表示字符串（如名字或日期）和特定格式的浮点数，所以基数排序也不是只能用于整数。 ```java public static void radixSort(int[] arr) { int max = arr[0]; for (int value : arr) { if (value > max) { max = value; } } for (int exp = 1; max / exp > 0; exp *= 10) { countSort(arr, exp); } } private static void countSort(int[] arr, int exp) { int[] output = new int[arr.length]; int[] count = new int[10]; for (int i = 0; i < arr.length; i++) { count[(arr[i] / exp) % 10]++; } for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } for (int i = arr.length - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } for (int i = 0; i < arr.length; i++) { arr[i] = output[i]; } } ``` 总结以上内容，Java提供了丰富多样的排序算法供开发者选择使用。理解这些排序算法的工作原理对于提高编程水平、优化程序性能都有着极为重要的意义。对于开发中遇到的不同需求，可以灵活选择不同的排序算法进行应对。同时，这些排序算法的设计思想在其他数据结构和算法的学习中也有着重要的启发作用。