Java 排序算法

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历要排序的数列，比较相邻元素的大小并交换位置，使得较大的元素逐渐向数列的末尾移动。

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

该算法的时间复杂度为O(n^2)，其中n是待排序数列的长度。

选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，它通过每次从未排序的元素中选出最小（或最大）的元素，将其放到已排序序列的末尾。

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

该算法的时间复杂度为O(n^2)，其中n是待排序数列的长度。

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

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

该算法的时间复杂度为O(n^2)，其中n是待排序数列的长度。

快速排序

快速排序（Quick Sort）是一种高效的排序算法，它通过分治的思想将待排序的数列分为两个部分，一部分比另一部分的所有元素都小，然后再对这两部分分别进行排序。

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

该算法的平均时间复杂度为O(nlogn)，其中n是待排序数列的长度。

 归并排序

归并排序（Merge Sort）是一种高效的排序算法，它通过分治的思想将待排序的数列分为两个部分，分别对这两部分进行排序，然后将它们合并成一个有序序列。

以下是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);}
}private 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 p = 0; p < temp.length; p++) {arr[low + p] = temp[p];}
}

该算法的平均时间复杂度为O(nlogn)，其中n是待排序数列的长度。

 堆排序

堆排序（Heap Sort）是一种高效的排序算法，它通过构建大顶堆或小顶堆来实现。

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

public static void heapSort(int[] arr) {// 构建大顶堆for (int i = arr.length / 2 - 1; i >= 0; i--) {adjustHeap(arr, i, arr.length);}// 交换堆顶元素和末尾元素并重新调整堆for (int j = arr.length - 1; j > 0; j--) {swap(arr, 0, j);adjustHeap(arr, 0, j);}
}private static void adjustHeap(int[] arr, int i, int length) {int temp = arr[i];for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {if (k + 1 < length && arr[k] < arr[k + 1]) {k++;}if (arr[k] > temp) {arr[i] = arr[k];i = k;} else {break;}}arr[i] = temp;
}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

该算法的平均时间复杂度为O(nlogn)，其中n是待排序数列的长度。

 希尔排序

希尔排序（Shell Sort）是一种改进的插入排序算法，它通过将待排序数列按照一定的间隔分组，对每组进行插入排序，然后逐渐缩小间隔，直到间隔为1时，整个数列已经基本有序，此时再进行一次普通的插入排序即可。

以下是Java实现的希尔排序代码：

public static void shellSort(int[] arr) {int gap = arr.length / 2;while (gap > 0) {for (int i = gap; i < arr.length; i++) {int j = i;int temp = arr[j];while (j - gap >= 0 && temp < arr[j - gap]) {arr[j] = arr[j - gap];j -= gap;}arr[j] = temp;}gap /= 2;}
}

该算法的平均时间复杂度为O(n^1.3)，其中n是待排序数列的长度。

计数排序

计数排序（Counting Sort）是一种非比较的排序算法，它通过统计每个元素出现的次数，然后根据元素出现的次数来对元素进行排序。

以下是Java实现的计数排序代码：

public static void countingSort(int[] arr) {int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}int[] count = new int[max + 1];for (int i = 0; i < arr.length; i++) {count[arr[i]]++;}int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] > 0) {arr[index++] = i;count[i]--;}}
}

该算法的时间复杂度为O(n+k)，其中n是待排序数列的长度，k是待排序数列中的最大值。

 桶排序

桶排序（Bucket Sort）是一种非比较的排序算法，它通过将待排序数列分到有限数量的有序桶中，然后对每个桶再进行排序，最后将各个桶中的数据依次取出即可得到有序序列。

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

public static void bucketSort(int[] arr) {int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;for (int i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}if (arr[i] < min) {min = arr[i];}}int bucketNum = (max - min) / arr.length + 1;ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);for (int i = 0; i < bucketNum; i++) {bucketArr.add(new ArrayList<>());}for (int i = 0; i < arr.length; i++) {int num = (arr[i] - min) / arr.length;bucketArr.get(num).add(arr[i]);}int index = 0;for (int i = 0; i < bucketArr.size(); i++) {Collections.sort(bucketArr.get(i));for (int j = 0; j < bucketArr.get(i).size(); j++) {arr[index++] = bucketArr.get(i).get(j);}}
}

该算法的时间复杂度为O(n+k)，其中n是待排序数列的长度，k是待排序数列中的最大值。

基数排序

基数排序（Radix Sort）是一种非比较的排序算法，它通过将待排序数列按照位数进行分组，然后对每个位数进行计数排序，最后将各个位数的数据依次取出即可得到有序序列。

以下是Java实现的基数排序代码：

public static void radixSort(int[] arr) {int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}int maxDigit = 0;while (max != 0) {max /= 10;maxDigit++;}int mod = 10, div = 1;ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();for (int i = 0; i < 10; i++) {bucketList.add(new ArrayList<>());}for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {for (int j = 0; j < arr.length; j++) {int num = (arr[j] % mod) / div;bucketList.get(num).add(arr[j]);}int index = 0;for (int j = 0; j < bucketList.size(); j++) {for (int k = 0; k < bucketList.get(j).size(); k++) {arr[index++] = bucketList.get(j).get(k);}bucketList.get(j).clear();}}
}

该算法的时间复杂度为O(n*k)，其中n是待排序数列的长度，k是待排序数列中的最大值的位数。