当前位置：首页 > news >正文

Java 八大排序算法详解（从入门到面试）

news 2026/7/1 22:10:39

一、八大排序算法总览

排序算法	类型	稳定性	平均时间复杂度	空间复杂度
冒泡排序	交换	稳定	O(n²)	O(1)
选择排序	选择	不稳定	O(n²)	O(1)
插入排序	插入	稳定	O(n²)	O(1)
希尔排序	插入	不稳定	O(n^1.3)	O(1)
归并排序	归并	稳定	O(n log n)	O(n)
快速排序	交换	不稳定	O(n log n)	O(log n)
堆排序	选择	不稳定	O(n log n)	O(1)
基数排序	分配	稳定	O(n·k)	O(n+k)

二、冒泡排序（Bubble Sort）

1. 思想

像水中的气泡一样，大的数不断“浮”到后面。

每一趟比较相邻元素
大的往后放
一趟结束，最大值到末尾

2. Java 实现

public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { boolean flag = false; 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; flag = true; } } if (!flag) break; // 优化：已排好序 } }

3. 特点

✅ 稳定
❌ 慢，只适合理解思想

三、选择排序（Selection Sort）

1. 思想

每一轮选择一个最小值，放到前面。

2. 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; } } int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } }

3. 特点

❌ 不稳定
❌ 比较次数固定

四、插入排序（Insertion Sort）

1. 思想

像打牌一样，把当前数插入到已排好序的部分。

2. Java 实现

public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int current = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > current) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = current; } }

3. 特点

✅ 稳定
✅ 小规模 / 基本有序非常快

五、希尔排序（Shell Sort）

1. 思想

插入排序的升级版，先分组，再插入。

2. Java 实现

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

六、归并排序（Merge Sort）

1. 思想

分而治之：

拆分数组
排序子数组
合并有序数组

2. 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); } }

七、快速排序（Quick Sort）⭐

1. 思想

选一个基准值，比它小的放左边，大的放右边。

2. Java 实现

public static void quickSort(int[] arr, int left, int right) { if (left >= right) return; int pivot = arr[left]; int l = left, r = right; while (l < r) { while (l < r && arr[r] >= pivot) r--; arr[l] = arr[r]; while (l < r && arr[l] <= pivot) l++; arr[r] = arr[l]; } arr[l] = pivot; quickSort(arr, left, l - 1); quickSort(arr, l + 1, right); }

3. 特点

🚀 实际中最快
❗ 最坏 O(n²)

八、堆排序（Heap Sort）

1. 思想

利用大顶堆/小顶堆的结构。

2.代码实现

package com.qcby; import java.lang.reflect.Array; import java.util.Arrays; public class duiSort { public static void main(String[] args) { int arr[] = {5,7,4,2,0,3,1,6}; for(int p = arr.length-1;p>=0;p--){ sort(arr,p,arr.length); } for(int i = arr.length-1;i>=0;i--){ int temp = arr[i]; arr[i] = arr[0]; arr[0] = temp; sort(arr,0,i); } System.out.println(Arrays.toString(arr)); } public static void sort(int arr[], int parent, int length){ int child = parent*2+1; while (child<length){ int rchild = child + 1; if(rchild<length && arr[rchild]>arr[child] ){ child++; } if(arr[parent]<arr[child] ){ int temp = arr[parent]; arr[parent] = arr[child]; arr[child] = temp; parent = child; child = parent*2+1; }else { break; } } } }