八大排序算法

一、排序算法总览表排序算法平均时间最好最坏空间稳定性直接插入O(n²)O(n)O(n²)O(1)稳定希尔排序O(nlogn)O(n)O(n²)O(1)不稳定直接选择O(n²)O(n²)O(n²)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定冒泡排序O(n²)O(n)O(n²)O(1)稳定快速排序O(nlogn)O(nlogn)O(n²)O(logn)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定基数排序O(d*n)O(d*n)O(d*n)O(n)稳定二、插入排序系列1. 直接插入排序InsertSort思想把数组分为有序区 无序区每次从无序区取一个数插入到有序区的正确位置。特点越接近有序速度越快小规模数据效率极高稳定代码void InsertSort(int arr[], int n) { for (int i 1; i n; i) { int val arr[i]; int j i - 1; while (j 0 arr[j] val) { arr[j 1] arr[j]; j--; } arr[j 1] val; } }2. 希尔排序ShellSort思想分组插入排序 → 逐步缩小增量 → 最后整体直接插入。突破 O (n²) 的第一种高效排序。特点效率比直接插入高很多不稳定代码void ShellSort(int arr[], int n) { int gap n / 2; while (gap 0) { for (int i gap; i n; i) { int val arr[i]; int j i - gap; while (j 0 arr[j] val) { arr[j gap] arr[j]; j - gap; } arr[j gap] val; } gap / 2; } }三、选择排序系列3. 直接选择排序SelectSort思想每次在无序区选最小的放到有序区末尾。特点数据移动次数少无论什么数据都是O(n²)不稳定代码void SelectSort(int arr[], int len) { for (int i 0; i len - 1; i) { int min i; for (int j i 1; j len; j) { if (arr[min] arr[j]) { min j; } } if (min ! i) { int tmp arr[min]; arr[min] arr[i]; arr[i] tmp; } } }4. 堆排序HeapSort思想利用大顶堆 / 小顶堆每次取堆顶最大值然后调整堆。特点最好最坏都是O(nlogn)空间O(1)不稳定大数据量效率极高代码// 核心函数1堆调整大顶堆 // 参数arr-待调整数组n-堆的大小i-当前需要调整的节点下标 void heapify(int arr[], int n, int i) { int largest i; // 初始化最大值为当前节点父节点 int left 2 * i 1; // 左子节点下标 int right 2 * i 2; // 右子节点下标 // 1. 找出父节点、左子节点、右子节点中的最大值 if (left n arr[left] arr[largest]) { largest left; // 左子节点更大更新最大值下标 } if (right n arr[right] arr[largest]) { largest right; // 右子节点更大更新最大值下标 } // 2. 如果最大值不是当前父节点交换并递归调整子堆 if (largest ! i) { swap(arr[i], arr[largest]); // 交换父节点和最大值节点 // 递归调整被交换的子节点确保子堆也是大顶堆 heapify(arr, n, largest); } } // 核心函数2堆排序主函数 void heapSort(int arr[], int n) { // 步骤1构建大顶堆从最后一个非叶子节点开始向前调整 for (int i (n - 2) / 2; i 0; i--) { heapify(arr, n, i); } // 步骤2交换堆顶与末尾元素 调整堆重复n-1次 for (int i n - 1; i 0; i--) { swap(arr[0], arr[i]); // 交换堆顶最大值和当前末尾元素 heapify(arr, i, 0); // 调整剩余i个元素为大顶堆i是当前堆的大小 } }四、交换排序系列5. 冒泡排序BubbleSort思想两两比较大的往后冒每轮确定一个最大值。特点最简单稳定效率低代码void BubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { bool flag false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { //swap(arr[j], arr[j 1]); tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; flag true; } } if (!flag) break; } }6. 快速排序QuickSort思想选基准 → 比基准小的放左边大的放右边 → 递归左右。目前综合性能最好的内部排序。特点平均最快不稳定数据量大优势明显代码// 左右指针划分标准划分 int Partion(int* ar, int left, int right) { assert(ar ! nullptr); int i left; int j right; // 基准选左边第一个 int tmp ar[i]; while (i j) { // 从右往左找小于基准的数 while (i j tmp ar[j]) --j; ar[i] ar[j]; // 填坑 // 从左往右找大于等于基准的数 while (i j tmp ar[i]) i; ar[j] ar[i]; // 填坑 } ar[i] tmp; // 基准归位 return i; // 返回基准下标 } void QuickSort(int arr[], int left, int right) { if (left right) return; int pivot Partion(arr, left, right); QuickSort(arr, left, pivot - 1); QuickSort(arr, pivot 1, right); }五、归并与基数排序7. 归并排序MergeSort思想分治法 → 拆分到单个元素 → 两两合并成有序序列。特点稳定非递归也能实现外部排序常用代码void Merge(int arr[], int tmp[], int left, int mid, int right) { int i left; int j mid 1; int k left; while (i mid j right) { if (arr[i] arr[j]) tmp[k] arr[i]; else tmp[k] arr[j]; } while (i mid) tmp[k] arr[i]; while (j right) tmp[k] arr[j]; for (i left; i right; i) arr[i] tmp[i]; } void MergeSort(int arr[], int tmp[], int left, int right) { if (left right) return; int mid (left right) / 2; MergeSort(arr, tmp, left, mid); MergeSort(arr, tmp, mid 1, right); Merge(arr, tmp, left, mid, right); }8. 基数排序RadixSort思想按个位、十位、百位依次分配、收集。不比较大小只按位分配。特点稳定适合整数、字符串空间消耗大六、高频试题1. 最快的通用排序快速排序2. 最好最坏都是 O (nlogn)堆排序、归并排序3. 哪种排序不需要比较基数排序4. 稳定的排序有哪些插入、冒泡、归并、基数。5. 快速排序最差情况是什么原本有序或逆序 → O (n²)6. 归并排序缺点是什么空间复杂度 O (n)7. 哪种排序越有序越快直接插入、冒泡8. 哪种排序和数据初始状态无关直接选择、堆排序、归并、基数