常见排序算法及其java实现

以下是常见的排序算法及其 ​​Java 实现​​，包括 ​​时间复杂度、空间复杂度、稳定性​​ 分析，并附上代码示例。

一、冒泡排序（Bubble Sort）​

原理​​：重复比较相邻元素，较大的元素逐步“冒泡”到数组末尾。
时间复杂度​​：

• 最好情况（已有序）：​​O(n)​​
• 平均和最坏情况：​​O(n²)​​

​​空间复杂度​​：​​O(1)​​（原地排序）
​​稳定性​​：​​稳定​​（相同元素相对位置不变）

public void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {boolean swapped = false; // 优化：如果某次没有交换，说明已有序for (int j = 0; j < n - 1 - i; 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; // 提前终止}
}

---

二、选择排序（Selection Sort）​​ ​​

原理​​：每次选择未排序部分的最小元素，放到已排序部分的末尾。
​​时间复杂度​​：​​O(n²)​​（无论数据是否有序）
​​空间复杂度​​：​​O(1)​​
​​稳定性​​：​​不稳定​​（可能破坏相同元素的顺序） ​​

public void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; 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;}
}   

---

三、插入排序（Insertion Sort）​​

​​原理​​：将未排序元素逐个插入到已排序部分的正确位置。
​​时间复杂度​​：

• 最好情况（已有序）：​​O(n)​​
• 平均和最坏情况：​​O(n²)​​

​​空间复杂度​​：​​O(1)​​
​​稳定性​​：​​稳定​​ ​​

public void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; 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; // 插入}
}          ​​

---

四、快速排序（Quick Sort）​​ ​​

原理​​：分治思想，选择一个基准（pivot），将数组分为小于基准和大于基准的两部分，递归排序。
​​时间复杂度​​：

• 平均情况：​​O(n log n)​​
• 最坏情况（如数组已有序）：​​O(n²)​​（可通过随机化基准避免）

​​空间复杂度​​：​​O(log n)​​（递归栈开销）
​​稳定性​​：​​不稳定​​ ​​

public void quickSort(int[] arr, int low, int high) {if (low < high) {int pivotIndex = partition(arr, low, high);quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}
}private int partition(int[] arr, int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;// 交换int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 把基准放到正确位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;return i + 1;
}  

---

五、归并排序（Merge Sort）​​ ​​

原理​​：分治思想，将数组分为两半，分别排序后合并。
​​时间复杂度​​：​​O(n log n)​​（所有情况）
​​空间复杂度​​：​​O(n)​​（需要额外数组）
​​稳定性​​：​​稳定​​

public void mergeSort(int[] arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}private void merge(int[] arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int[] L = new int[n1];int[] R = new int[n2];// 拷贝数据到临时数组for (int i = 0; i < n1; i++) L[i] = arr[left + i];for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];// 合并int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 处理剩余元素while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}  

---

六、堆排序（Heap Sort）​

​​原理​​：利用堆数据结构（大顶堆/小顶堆）进行排序。
​​时间复杂度​​：​​O(n log n)​​（所有情况）
​​空间复杂度​​：​​O(1)​​（原地排序）
​​稳定性​​：​​不稳定

public void heapSort(int[] arr) {int n = arr.length;// 构建大顶堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐个提取堆顶元素for (int i = n - 1; i > 0; i--) {// 交换堆顶和最后一个元素int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 调整堆heapify(arr, i, 0);}
}private 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 temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;heapify(arr, n, largest);}
}

---

总结​​

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n²)	O(n²)	O(1)	稳定	小规模数据
选择排序	O(n²)	O(n²)	O(1)	不稳定	小规模数据
插入排序	O(n²)	O(n²)	O(1)	稳定	小规模或接近有序数据
快速排序	O(n log n)	O(n²)	O(log n)	不稳定	大规模数据（最快）
归并排序	O(n log n)	O(n log n)	O(n)	稳定	大规模数据（稳定）
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	大规模数据（原地排序）

推荐选择​​：

• ​​小规模数据​​：插入排序（稳定）或冒泡排序（简单）。
• ​大规模数据​​：快速排序（最快）、归并排序（稳定）、堆排序（原地排序）。