常见的排序算法详解
以下是常见的排序算法：
- 冒泡排序（Bubble Sort）
- 选择排序（Selection Sort）
- 插入排序（Insertion Sort）
- 快速排序（Quick Sort）
- 归并排序（Merge Sort）
- 堆排序（Heap Sort）
- 希尔排序（Shell Sort）
- 计数排序（Counting Sort）
- 桶排序（Bucket Sort）
- 基数排序（Radix Sort）
每个排序算法都有其独特的应用场景和优缺点，选择最适合问题的算法可以提高程序的效率。
排序算法详解
下面给出前五种排序算法的Java版本代码实现和详细介绍，代码中会有详细的注释。
1. 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法，它的基本思想是重复地交换相邻两个元素，将较大的元素逐渐“浮”到数列的顶端，而较小的元素则沉到底部。
时间复杂度：O(n^2)
稳定性：稳定
代码实现：
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
boolean swapped = false;
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;
swapped = true;
}
}
if (!swapped) {
// 如果没有进行交换操作，说明已经有序，可以提前结束循环
break;
}
}
}2. 选择排序（Selection Sort）
选择排序的基本思想是：首先，在未排序的数列中找到最小（大）的元素，然后将其放到数列的起始位置；接着，从剩余未排序的元素中继续寻找最小（大）的元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
时间复杂度：O(n^2)
稳定性：不稳定
代码实现：
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; 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;
}
}3. 插入排序（Insertion Sort）
插入排序的基本思想是：将未排序的元素逐个插入到已排序的序列中，形成一个有序序列。
时间复杂度：O(n^2)
稳定性：稳定
代码实现：
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
// 从未排序部分的第一个元素开始逐个向前插入
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
// 如果前一个元素比后一个元素大，交换它们的位置
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
} else {
// 如果前一个元素比后一个元素小，说明已经有序，可以提前结束循环
break;
}
}
}
}4. 快速排序（Quick Sort）
快速排序是一种分治的排序算法，它的基本思想是：选择一个基准数，将序列中小于基准数的元素放在基准数的左边，大于基准数的元素放在基准数的右边，然后对左右两个子序列分别递归地进行快速排序。
时间复杂度：O(nlogn)
稳定性：不稳定
代码实现：
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
// 从右往左找到第一个小于基准数的元素
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
// 从左往右找到第一个大于基准数的元素
while (i < j && arr[i] < pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot;
// 递归对左右两个子序列进行快速排序
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}5. 归并排序（Merge Sort）
归并排序是一种分治的排序算法，它的基本思想是：将序列分成两个子序列，对每个子序列递归地进行归并排序，然后将两个已排序的子序列合并成一个有序序列。
时间复杂度：O(nlogn)
稳定性：稳定
代码实现：
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
// 递归对左右两个子序列进行归并排序
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, 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++];
}
System.arraycopy(temp, 0, arr, left, temp.length);
}6. 希尔排序（Shell Sort）
希尔排序是一种基于插入排序的排序算法，它通过将原序列分成若干个子序列来加快插入排序的速度，每次对子序列进行插入排序，缩小子序列的长度，直到子序列长度为1，即完成了对整个序列的排序。
时间复杂度：O(nlogn)
稳定性：不稳定
代码实现：
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 temp = arr[i];
int j;
// 将元素插入到已排序的子序列中
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}7. 计数排序（Counting Sort）
计数排序是一种非比较排序算法，它的基本思想是：统计序列中每个元素出现的次数，然后根据元素出现的次数，将元素放回原序列中。
时间复杂度：O(n+k)，其中k是元素的范围
稳定性：稳定
代码实现：
public static void countingSort(int[] arr) {
int n = arr.length;
int max = Arrays.stream(arr).max().getAsInt();
int[] count = new int[max + 1];
// 统计每个元素出现的次数
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 根据元素出现的次数，将元素放回原序列中
int index = 0;
for (int i = 0; i <= max; i++) {
for (int j = 0; j < count[i]; j++) {
arr[index++] = i;
}
}
}8. 桶排序（Bucket Sort）
桶排序是一种非比较排序算法，它的基本思想是：将元素分到不同的桶中，并对每个桶中的元素进行排序，最后将桶中的元素按顺序合并到原序列中。
时间复杂度：O(n+k)，其中k是桶的个数
稳定性：稳定
代码实现：
public static void bucketSort(int[] arr, int bucketSize) {
int n = arr.length;
int min = Arrays.stream(arr).min().getAsInt();
int max = Arrays.stream(arr).max().getAsInt();
int bucketCount = (max - min) / bucketSize + 1;
List<List<Integer>> buckets = new ArrayList<>(bucketCount);
// 初始化桶
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
// 将元素分到不同的桶中
for (int i = 0; i < n; i++) {
int bucketIndex = (arr[i] - min) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
// 对每个桶中的元素进行排序
for (List<Integer> bucket : buckets) {
Collections.sort(bucket);
}
// 将桶中的元素按顺序合并到原序列中
int index = 0;
for (List<Integer> bucket : buckets) {
for (int num : bucket) {
arr[index++] = num;
}
}
}9. 基数排序（Radix Sort）
基数排序是一种非比较排序算法，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较，最终得到有序序列。
时间复杂度：O(d(n+k))，其中d是最大数字的位数，k是基数大小
稳定性：稳定
代码实现：
public static void radixSort(int[] arr) {
int n = arr.length;
int max = Arrays.stream(arr).max().getAsInt();
for (int exp = 1; max / exp > 0; exp *= 10) {
int[] count = new int[10];
// 统计每个桶中的元素个数
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
// 计算每个桶中元素的结束位置
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// 将元素移动到对应的桶中
int[] temp = new int[n];
for (int i = n - 1; i >= 0; i--) {
temp[--count[(arr[i] / exp) % 10]] = arr[i];
}
System.arraycopy(temp, 0, arr, 0, n);
}
}10. 堆排序（Heap Sort）
堆排序是一种选择排序，它的基本思想是：将待排序序列建成一个大根堆（或小根堆），然后将堆顶元素与堆底元素交换位置，并重新调整堆，直到整个序列有序。
时间复杂度：O(nlogn)
稳定性：不稳定
代码实现：
public static void heapSort(int[] arr) {
int n = arr.length;
// 建立大根堆
for (int i = n / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, n);
}
// 依次输出堆顶元素，并重新调整堆
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
adjustHeap(arr, 0, i);
}
}
private static void adjustHeap(int[] arr, int i, int n) {
int temp = arr[i];
for (int k = i * 2 + 1; k < n; k = k * 2 + 1) {
if (k + 1 < n && 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;
}以上就是针对常见的十种排序算法的总结和例子演示，希望你们可以从中学到自己想要的知识。
Java api当中使用算法的例子
在JDK中，对于排序算法的实现，主要是在java.util包下的Arrays类和Collections类中。
1. 冒泡排序（Bubble Sort）
Arrays类中的sort方法默认使用的是快速排序算法，如果需要使用冒泡排序算法，可以通过传递自定义比较器实现。
int[] arr = {5, 2, 8, 4, 7};
Arrays.sort(arr, (a, b) -> b - a);
System.out.println(Arrays.toString(arr)); // [8, 7, 5, 4, 2]2. 选择排序（Selection Sort）
Collections类中的sort方法可以对List进行排序，默认使用的是归并排序算法。如果需要使用选择排序算法，可以通过传递自定义比较器实现。
List<Integer> list = Arrays.asList(5, 2, 8, 4, 7);
list.sort((a, b) -> a - b);
System.out.println(list); // [2, 4, 5, 7, 8]3. 插入排序（Insertion Sort）
Collections类中的sort方法可以对List进行排序，默认使用的是归并排序算法。如果需要使用插入排序算法，可以通过传递自定义比较器实现。
List<Integer> list = Arrays.asList(5, 2, 8, 4, 7);
list.sort((a, b) -> b - a);
System.out.println(list); // [8, 7, 5, 4, 2]4. 归并排序（Merge Sort）
Arrays类中的parallelSort方法可以对数组进行并行排序，默认使用的是归并排序算法。如果需要使用顺序排序算法，可以使用Arrays类的sort方法。
int[] arr = {5, 2, 8, 4, 7};
Arrays.parallelSort(arr);
System.out.println(Arrays.toString(arr)); // [2, 4, 5, 7, 8]5. 快速排序（Quick Sort）
Arrays类中的sort方法可以对数组进行排序，默认使用的是快速排序算法。如果需要使用自定义的快速排序算法，可以通过实现Comparator接口和Arrays类的sort方法传递自定义比较器实现。
int[] arr = {5, 2, 8, 4, 7};
Arrays.sort(arr, (a, b) -> b - a);
System.out.println(Arrays.toString(arr)); // [8, 7, 5, 4, 2]6. 希尔排序（Shell Sort）
JDK中没有提供希尔排序算法的实现，需要自己实现。
7. 计数排序（Counting Sort）
JDK中没有提供计数排序算法的实现，需要自己实现。
8. 桶排序（Bucket Sort）
JDK中没有提供桶排序算法的实现，需要自己实现。
9. 基数排序（Radix Sort）
JDK中没有提供基数排序算法的实现，需要自己实现。
10. 堆排序（Heap Sort）
JDK中提供了PriorityQueue类，该类实现了小根堆的数据结构，并提供了相应的操作方法，可以方便地实现堆排序算法。
int[] arr = {5, 2, 8, 4, 7};
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : arr) {
pq.offer(num);
}
for (int i = 0; i < arr.length; i++) {
arr[i] = pq.poll();
}
System.out.println(Arrays.toString(arr)); // [2, 4, 5, 7, 8]以上就是JDK中使用以上十种排序算法的示例代码和说明，希望对你有所帮助。
文章评论