一、排序算法总结
1. 插入排序
- 原理：顺序表插入，将一个数据插入到已经排好序的数组中的适当位置。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定排序
2. 希尔排序
- 原理：分组，分别进行插入排序。引入 gap 表示分组方式， gap 值大时每组长度小， gap 值变小过程中数组逐渐有序，最后 gap 为1时保证最终有序。
- 时间复杂度：最坏O(N^2)，平均取决于 gap 序列取值
- 空间复杂度：O(1)
- 稳定性：不稳定
3. 直接选择排序
- 原理：每次从待排序区间中找到最小的元素，放到待排序区间的开头，再合并入已排序区间 。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
4. 堆排序
- 原理：通过建堆的方式，找到“最小/最大”元素 。升序建大堆，降序建小堆，把堆顶元素和最后一个元素交换。
- 时间复杂度：O(NlogN)
- 空间复杂度：O(1)
- 稳定性：不稳定
5. 冒泡排序
- 原理：比较交换相邻元素。
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
6. 快速排序
- 原理：采用分治思想，选定基准值，将数组整理成比基准值小、基准值、比基准值大三个部分，再对左右区间递归该过程。
- 时间复杂度：最坏O(N^2) ，平均O(NlogN)
- 空间复杂度：递归深度相关，平均O(logN)
- 稳定性：不稳定
- 优化策略
- 三数取中：取数组最左、最右、中间位置元素，用中间值作为基准值，可避免基准值为区间最大/最小值的极端情况。
- 小数组插入排序：当递归到子问题较小时，使用插入排序替代递归。
- 堆排序替代：针对大数组排序，递归深度较高时，对分出来的子区间用堆排序。
- 代码示例（Java）
public class QuickSort {
private static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int index = partition(arr, left, right);
quickSort(arr, left, index - 1);
quickSort(arr, index + 1, right);
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
7. 归并排序
- 原理：分治思想，把数组不断拆分成子数组，直到子数组长度为1（有序），再两两合并成有序数组。
- 时间复杂度：O(NlogN)
- 空间复杂度：O(N) ，递归空间损耗O(logN)，合并需临时数组
- 稳定性：稳定，合并时相邻数组操作，可保证相同值元素相对顺序。
- 优势：可对链表排序；能处理海量数据，可进行外部排序 。
- 代码示例（Java）
public class MergeSort {
private 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;
int j = mid + 1;
int 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 (k = 0; k < temp.length; k++) {
arr[left + k] = temp[k];
}
}
public static void main(String[] args) {
int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
mergeSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
