一、排序的基本概念与分类排序是计算机程序设计中的一个重要操作它的功能是将一个数据元素或记录的任意序列重新排列成一个按关键字有序的序列。一排序的稳定性假设且在排序前的序列中领先于即 i j。如果排序后仍领先于则称所用的排序方法是稳定的反之若可能使得排序后的序列中领先于则称所用的排序方法是不稳定的。二内部排序与外部排序内部排序是在排序整个过程中待排序的所有记录全部被放置在内存中。外部排序是由于排序的记录个数太多不能同时放置在内存整个排序过程需要在内外存之间多次交换数据才能进行。三排序核心评价指标1.时间复杂度2.空间复杂度3.稳定性4.算法复杂性二、八大排序一直接插入排序1.概述直接插入排序是一种最简单的排序方法它的基本操作是将一个记录插入到已经排好序有序表中从而得到一个新的、记录数增1的有序表。2.核心原理把待排序序列分为有序区和无序区默认第一个元素为有序区。依次取出无序区的第一个元素向前插入到有序区的合适位置直到所有元素有序。3.代码实现C语言void Insert_Sort(int arr[], int len) { //控制排序总趟数从第二个元素开始默认第一个元素有序 for (int i 1; i len - 1; i) { int tmp arr[i]; //取出无序区的第一个数 int j i - 1; //从有序区末尾开始向前遍历 //从右至左遍历有序区寻找tmp的插入位置 for (; j 0; j--) { //有序区当前元素大于待插入元素tmp元素后移腾出位置 if (arr[j] tmp) { arr[j 1] arr[j]; } else { //找到小于等于tmp的元素确定插入位置跳出遍历 break; } } //两种情况统一赋值 //情况1:循环中途breakj为合法下标j1为插入位置 //情况2:循环遍历完毕j-1仍未找到小于等于tmp的元素说明tmp是最小值插入数组首位 arr[j 1] tmp; } }4.特点1数据越有序整体排序效率越高2适用场景小规模数据、基本有序的数据优化方法在有序区查找待插值的插入位置时可以采用二分法。二希尔排序1.概述希尔排序又称“缩小增量排序”它也是一种属插入排序类的方法。它的基本思想是先将整个待排序记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行一个直接插入排序。注意1子序列的构成不是简单地“逐段分割”而是将相隔某个“增量”的记录组成一个子序列。2增量序列取法好坏与希尔排序的时间复杂度直接相关可是又没有一个最优解。3增量序列需要遵从一些规则取值从大到小取值尽量互素最后一个增量值必须是12.核心原理希尔排序是直接插入排序的优化版核心是分组插入1定义一个增量gap将数组按gap分组2对每组分别进行直接插入排序3不断缩小gap直到gap1此时就是普通插入排序数组完全有序。总的来说先让数组大体有序最后微调大幅提升插入排序效率。3.代码实现C语言//单趟分组插入处理函数 gap_val:当前分组增量 void Shell(int arr[], int len, int gap_val) { //i遍历所有需要往前插入的待排序元素 for (int i gap_val; i len - 1; i) //此时i控制的是需要往前插入的待排序值 { int tmp arr[i]; //取出当前分组中待插入的元素 int j i - gap_val; //定位当前元素所在分组的前一个位置 //从右至左遍历同组的已排序序列 for (; j 0; j - gap_val) { //已排序元素大于待插入值元素后移腾出插入位置 if (arr[j] tmp) { arr[j gap_val] arr[j]; } //找到小于等于tmp的元素确定插入位置终止遍历 else { break; } } //两种情况统一赋值 //情况1:遍历中途breakj为合法下标jgap_val为正确插入位置 //情况2:遍历越界j0说明tmp为当前组最小值插入组内首位 arr[j gap_val] tmp; } } //希尔排序函数 void Shell_Sort(int arr[], int len) { //自定义增量序列 int Gap[] { 5,3,1 }; int len_Gap sizeof(Gap) / sizeof(Gap[0]); //增量数组长度 // 遍历每一个增量完成多趟分组排序 for (int i 0; i len_Gap; i) { Shell(arr, len, Gap[i]); } }4.特点1时间复杂度取决于增量序列的赋值或2适用场景中等规模数据作为插入排序的优化方案三简单选择排序1.概述简单选择排序的操作为通过 n - i 次关键字间的比较从 n - i 1 个记录中选出关键字最小的记录并和第 i1 i n个记录交换之。简单来说就是每一趟将待排序序列中最小值找到再将其和待排序序列的第一个值进行交换相当于每一趟都把当前的最小值挪动到最前面和冒泡区别冒泡是相邻交换选择排序是每轮只交换一次交换次数更少。2.核心原理分有序区和无序区每一轮遍历找出无序区的最小值下标和无序区第一个元素交换逐步构建有序区。当无序区仅剩一个元素时无序区最小值和第一个元素都是它自身无需再交换3.代码实现C语言void Select_Sort(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[j] arr[min]) { min j; } } //最小值下标不等于起始下标说明找到更小值执行交换 if (min ! i) { int tmp arr[min]; arr[min] arr[i]; arr[i] tmp; } } }4.特点1交换次数少2无论数据是否有序都需要完整遍历3适用场景对交换次数有要求、小规模数据四冒泡排序1.概述冒泡排序是一种交换排序它的基本思想是两两比较相邻记录的关键字如果反序则交换直到没有反序的记录为止。每一轮遍历结束后当前最大值都会“冒泡”到数组末尾像水泡上浮一样因此得名冒泡排序。2.核心原理重复遍历数组相邻两个元素两两比较如果前一个比后一个大就交换位置。3.代码实现C语言void Bubble_Sort(int arr[], int len) { //外层循环:控制排序总趟数 for (int i 0; i len - 1; i) { //内层循环:每一趟从左向右遍历待排序区间两两比较 //每完成一趟末尾i个元素已经有序无需再次比较 for (int j 0; j len - i - 1; j) { //相邻元素两两对比左侧元素大于右侧则交换 if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; } } } }4.特点1时间复杂度高数据量大时效率极低2适用场景小规模数据、几乎有序的数据5.冒泡排序的优化引入有序标记变量每一趟排序开始时默认数组已有序发生元素交换说明数组无序修改标记继续下一趟排序全程无交换说明数组已经完全有序直接终止排序不再执行剩余趟数。最优时间复杂度从 O(n²) 优化为 O(n)void Bubble_Sort_Plus(int arr[], int len) { //外层循环控制排序趟数 for (int i 0; i len - 1; i) { bool tag true; //每趟初始默认数组已有序 //遍历待排序区间两两比较交换 for (int j 0; j len - i - 1; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; tag false; //发生交换说明数组无序 } } //本趟无任何交换数组已经完全有序直接结束排序 if (tag) return; } }五归并排序1.概述“归并”的含义是将两个或两个以上的有序表合成一个新的有序表。归并排序就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录则可以看成是n个有序的子序列每个子序列的长度为1然后两两归并得到[n/2][x]表示不小于x的最小整数个长度为2或1的有序子序列再两两归并......如此重复直到得到一个长度为n的有序序列为止这种排序方法称为2路归并排序。2.核心原理纯分治思想先分后合1分将数组不断对半拆分拆到单个元素天然有序2合将两个有序子数组按大小规则合并为一个有序数组3逐层向上合并最终得到完整有序数组。3.代码实现C语言//归并排序:将两个有序子区间合并为一个有序区间 void Merge(int arr[], int left, int mid, int right) { //动态开辟临时数组存储合并后的有序序列 int* brr (int*)malloc((right - left 1) * sizeof(int)); if (NULL brr) exit(EXIT_FAILURE); //内存开辟失败容错 int i left; //左有序区间起始下标 int j mid 1; //右有序区间起始下标 int k 0;//临时数组存储下标 //同时遍历左右两个有序区间取较小值放入临时数组 while (i mid j right) { if (arr[i] arr[j]) { brr[k] arr[i]; } else { brr[k] arr[j]; } } //处理左区间剩余元素 while (i mid) { brr[k] arr[i]; } //处理右区间剩余元素 while (j right) { brr[k] arr[j]; } //将临时有序数组数据拷贝回原数组对应区间 for (int w left; w right; w) { arr[w] brr[w - left]; } //释放动态内存避免内存泄漏 free(brr); brr NULL; } //归并排序:递归拆分区间分治核心 void Divide(int arr[], int left, int right) { //递归终止条件:区间只有一个元素或无元素天然有序 if (left right) { return; } int mid (left right) / 2; //中间分界点拆分左右区间 //分好的左区间的范围 [left, mid] //分好的右区间的范围 [mid 1, right] //递归拆分左区间 [left, mid] Divide(arr, left, mid); //递归拆分右区间 [mid 1, right] Divide(arr, mid 1, right); //拆分完成合并两个有序区间 Merge(arr, left, mid, right); } //归并排序入口函数 void Merge_Sort(int arr[], int len) { //对整个数组区间执行分治归并 Divide(arr, 0, len - 1); }4.特点1八大排序中唯一时间复杂度完全稳定O(nlogn)且稳定的排序2适用场景对排序稳定性要求高、大数据外排序、链表排序六堆排序1.概述堆排序就是利用堆假设利用大顶堆进行排序的方法。它的基本思想是将待排序的序列造成一个大顶堆。此时整个序列的最大值就是堆顶的根节点。将它移走其实就是将其与堆数组的末尾元素交换此时末尾元素就是最大值然后将剩余的n-1个序列重新造成一个堆这样就会得到n个元素中的次小值。如此反复执行便能得到一个有序序列了。2.核心原理1将数组构建成大顶堆父节点大于左右子节点2堆顶就是最大值将堆顶和数组末尾元素交换末尾变为有序3剩余无序数组重新调整为大顶堆重复交换直到全部有序。3.代码实现C语言//堆排序:单次堆调整函数将指定子树调整为大顶堆 //start:当前需要调整的根节点下标 //end:堆的有效最后节点下标 void Heap_Adjust(int arr[], int start, int end) { //取出根节点值产生空白根节点位置 int tmp arr[start]; //maxchild默认指向根节点左孩子 int maxchild start * 2 1; //循环向下调整堆结构空白节点存在孩子则继续遍历 while (maxchild end) { //判断右孩子是否存在且更大更新最大孩子下标 if (maxchild 1 end arr[maxchild 1] arr[maxchild]) { maxchild; } //若最大孩子值小于等于根节点值满足大顶堆性质直接回填结束 if (arr[maxchild] tmp) { arr[start] tmp; return; } else { //最大孩子值更大孩子值上移填充空白位 arr[start] arr[maxchild]; //空白位下移继续向下调整 start maxchild; maxchild start * 2 1; } } //空白节点无孩子触底回填根节点原值完成调整 arr[start] tmp; return; } //堆排序入口函数 void Heap_Sort(int arr[], int len) { //初始建堆:从最后一个非叶子节点向前遍历由下至上构建大顶堆 for (int i (len - 1 - 1) / 2; i 0; i--) { Heap_Adjust(arr, i, len - 1); } //逐步交换堆顶与末尾元素缩减堆范围反复调整堆 for (int i len - 1; i 1; i--) //i代表的是要头尾交换的尾结点下标 { //交换堆顶最大值与当前末尾元素末尾区间转为有序 int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; //堆结构破坏重新调整根节点有效堆范围缩减为[0, i-1] Heap_Adjust(arr, 0, i - 1); } }4.特点1堆排序是选择排序的最优优化时间复杂度稳定O(nlogn)2适用场景要求排序时间稳定、大数据量七基数排序1.概述基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法2.核心原理基于桶排序思想按位排序、从低位到高位1找出数组最大值确定最大位数2从个位开始依次按照当前位数字放入对应桶中3按桶顺序回收数组逐位排序直到最高位排序完成数组整体有序。3.代码实现C语言//获取数组最大值的总位数 int Get_MaxNum_Figure(int arr[], int len) { //找出数组最大值 int max arr[0]; for (int i 0; i len; i) { if (arr[i] max) max arr[i]; } //统计最大值的位数 int count 1; while (max / 10) { count; } return count; } //获取数字num第digit位上的数值 //digit0:个位排序digit1:十位排序以此类推 int Get_Num_Digit(int num, int digit) { assert(digit 0); //右移digit位取出当前位 for (int i 0; i digit; i) { num / 10; } return num % 10; } //单趟基数排序:对数组按照第digit位进行桶排序 //digit0:个位排序digit1:十位排序以此类推 void Radix(int arr[], int len, int digit) { //1.申请0~9十个队列桶 std::queueint Buckets[10]; //2.遍历所有元素按当前位数值入桶 for (int i 0; i len; i) { //获取当前元素对应位数的数字确定桶下标 int index Get_Num_Digit(arr[i], digit); //元素进入对应桶 Buckets[index].push(arr[i]); } //3.按桶顺序依次出队覆盖原数组完成当前位有序 int k 0; for (int i 0; i 9; i) { //当前桶不为空全部取出放回原数组 while (!Buckets[i].empty()) { arr[k] Buckets[i].front(); Buckets[i].pop(); } } } //基数排序总入口函数 void Radix_Sort(int arr[], int len) { //获取数组最大值位数确定排序总趟数 int fig Get_MaxNum_Figure(arr, len); //从低位到高位逐位进行桶排序 for (int i 0; i fig; i) //i0代表按个数处理 i1代表按十位处理 以此类推 { Radix(arr, len, i); } }4.特点1非比较型排序速度远超比较排序2只能处理整数数据、需要额外空间3适用场景固定位数的整数排序数据之间位数差距不大的排序八快速排序1.概述快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序的目的。2.核心原理分治思想挖坑填数1从数组中选一个基准数2将数组分区小于基准数的放左边大于基准数的放右边3对基准数左右两个子数组重复分区操作直到全部有序。3.代码实现C语言1方法一递归实现//快速排序:单趟挖空法分区函数 //将数组以基准值为中心分为左右两部分返回基准值最终下标 int Partition(int arr[], int left, int right) { //取出最左端元素作为基准值用tmp临时保存防止被覆盖 int tmp arr[left]; //左右指针未相遇时持续分区 while (left right) { //从右向左遍历寻找小于等于基准值的元素 while (leftright arr[right] tmp) { right--; } //这个内部while循环结束会有两种情况 //情况1:指针相遇直接退出分区 if (left right) break; //情况2:指针未相遇但是找到了小于等于基准值的元素直接将其填入左侧空位 arr[left] arr[right]; //从左向右遍历寻找大于基准值的元素 while (leftright arr[left] tmp) { left; } //情况1:指针相遇直接退出分区 if (left right) break; //情况2:指针未相遇但是找到了大于基准值的元素直接将其填入右侧空位 arr[right] arr[left]; } //指针相遇位置即为基准值的正确位置将基准值填入 arr[left] tmp; //或 arr[right] tmp; //返回基准值下标 return left; //或 return right; } //快速排序递归分治函数 void Quick(int arr[], int left, int right) { //递归终止条件:区间无元素或只有单个元素天然有序 if (left right) return; //完成单趟分区获取基准下标 int par Partition(arr, left, right); //递归排序左区间小于基准值 Quick(arr, left, par - 1); //递归排序右区间大于基准值 Quick(arr, par 1, right); } //快速排序入口函数 void Quick_Sort(int arr[], int len) { //对整个数组执行快速排序 Quick(arr, 0, len - 1); }2方法二非递归实现//快速排序:非递归版 void Quick_Sort_No_Recursion(int arr[], int len)//非递归的方法 { //栈存储区间左右边界每一组区间存储两个值:左边界、右边界 std::stackint st; //初始整体区间入栈 st.push(0); st.push(len - 1); //栈不为空持续迭代处理所有分区 while (!st.empty()) { //取出当前待处理区间的左右边界 int right st.top(); st.pop(); int left st.top(); st.pop(); //执行单趟挖空法分区获取基准值下标 int par Partition(arr, left, right); //左区间若存在有效元素元素个数 2区间入栈等待后续处理 if (left par - 1) { st.push(left); st.push(par - 1); } //右区间存在有效元素元素个数 2区间入栈等待后续处理 if (par 1 right) { st.push(par 1); st.push(right); } } }4.特点1平均效率极高O(nlogn)、速度快2数据越乱效率越高数据越有序反而效率越低最坏退化成O(n²)3适用场景大规模无序数据、数据量极大的场景5.快速排序的优化核心思想打乱数据1快速排序启动时如果待排序序列数据量较小直接放弃快速排序调用直接插入排序或冒泡排序完成排序。针对原始整体数组2在快速排序持续分区过程中如果发现划分出的子区间长度小于设定阈值则直接对当前小区间使用直接插入排序或冒泡排序完成排序。针对拆分后的子区间3三数取中法从当前待排序区间中取出最左端、最右端、中间位置三个数值对比大小选取三者中“大小居中的值”交换到区间最左端作为本轮分区的基准值。4随机基准数法随机打乱数据在当前待排序区间内随机选取一个数值将其与区间最左端数值交换以随机值作为本轮分区的基准值。可多次随机交换进一步打乱有序性。三、总结排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度稳定性直接插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序或O(1)不稳定简单选择排序O(n²)O(n²)O(n²)O(1)不稳定冒泡排序O(n²)O(n)O(n²)O(1)稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定基数排序O(d(nr))O(d(nr))O(d(nr))O(nr)稳定快速排序O(nlogn)O(nlogn)O(n²)O(logn)不稳定
数据结构——八大排序算法精解：从原理到代码实现
一、排序的基本概念与分类排序是计算机程序设计中的一个重要操作它的功能是将一个数据元素或记录的任意序列重新排列成一个按关键字有序的序列。一排序的稳定性假设且在排序前的序列中领先于即 i j。如果排序后仍领先于则称所用的排序方法是稳定的反之若可能使得排序后的序列中领先于则称所用的排序方法是不稳定的。二内部排序与外部排序内部排序是在排序整个过程中待排序的所有记录全部被放置在内存中。外部排序是由于排序的记录个数太多不能同时放置在内存整个排序过程需要在内外存之间多次交换数据才能进行。三排序核心评价指标1.时间复杂度2.空间复杂度3.稳定性4.算法复杂性二、八大排序一直接插入排序1.概述直接插入排序是一种最简单的排序方法它的基本操作是将一个记录插入到已经排好序有序表中从而得到一个新的、记录数增1的有序表。2.核心原理把待排序序列分为有序区和无序区默认第一个元素为有序区。依次取出无序区的第一个元素向前插入到有序区的合适位置直到所有元素有序。3.代码实现C语言void Insert_Sort(int arr[], int len) { //控制排序总趟数从第二个元素开始默认第一个元素有序 for (int i 1; i len - 1; i) { int tmp arr[i]; //取出无序区的第一个数 int j i - 1; //从有序区末尾开始向前遍历 //从右至左遍历有序区寻找tmp的插入位置 for (; j 0; j--) { //有序区当前元素大于待插入元素tmp元素后移腾出位置 if (arr[j] tmp) { arr[j 1] arr[j]; } else { //找到小于等于tmp的元素确定插入位置跳出遍历 break; } } //两种情况统一赋值 //情况1:循环中途breakj为合法下标j1为插入位置 //情况2:循环遍历完毕j-1仍未找到小于等于tmp的元素说明tmp是最小值插入数组首位 arr[j 1] tmp; } }4.特点1数据越有序整体排序效率越高2适用场景小规模数据、基本有序的数据优化方法在有序区查找待插值的插入位置时可以采用二分法。二希尔排序1.概述希尔排序又称“缩小增量排序”它也是一种属插入排序类的方法。它的基本思想是先将整个待排序记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行一个直接插入排序。注意1子序列的构成不是简单地“逐段分割”而是将相隔某个“增量”的记录组成一个子序列。2增量序列取法好坏与希尔排序的时间复杂度直接相关可是又没有一个最优解。3增量序列需要遵从一些规则取值从大到小取值尽量互素最后一个增量值必须是12.核心原理希尔排序是直接插入排序的优化版核心是分组插入1定义一个增量gap将数组按gap分组2对每组分别进行直接插入排序3不断缩小gap直到gap1此时就是普通插入排序数组完全有序。总的来说先让数组大体有序最后微调大幅提升插入排序效率。3.代码实现C语言//单趟分组插入处理函数 gap_val:当前分组增量 void Shell(int arr[], int len, int gap_val) { //i遍历所有需要往前插入的待排序元素 for (int i gap_val; i len - 1; i) //此时i控制的是需要往前插入的待排序值 { int tmp arr[i]; //取出当前分组中待插入的元素 int j i - gap_val; //定位当前元素所在分组的前一个位置 //从右至左遍历同组的已排序序列 for (; j 0; j - gap_val) { //已排序元素大于待插入值元素后移腾出插入位置 if (arr[j] tmp) { arr[j gap_val] arr[j]; } //找到小于等于tmp的元素确定插入位置终止遍历 else { break; } } //两种情况统一赋值 //情况1:遍历中途breakj为合法下标jgap_val为正确插入位置 //情况2:遍历越界j0说明tmp为当前组最小值插入组内首位 arr[j gap_val] tmp; } } //希尔排序函数 void Shell_Sort(int arr[], int len) { //自定义增量序列 int Gap[] { 5,3,1 }; int len_Gap sizeof(Gap) / sizeof(Gap[0]); //增量数组长度 // 遍历每一个增量完成多趟分组排序 for (int i 0; i len_Gap; i) { Shell(arr, len, Gap[i]); } }4.特点1时间复杂度取决于增量序列的赋值或2适用场景中等规模数据作为插入排序的优化方案三简单选择排序1.概述简单选择排序的操作为通过 n - i 次关键字间的比较从 n - i 1 个记录中选出关键字最小的记录并和第 i1 i n个记录交换之。简单来说就是每一趟将待排序序列中最小值找到再将其和待排序序列的第一个值进行交换相当于每一趟都把当前的最小值挪动到最前面和冒泡区别冒泡是相邻交换选择排序是每轮只交换一次交换次数更少。2.核心原理分有序区和无序区每一轮遍历找出无序区的最小值下标和无序区第一个元素交换逐步构建有序区。当无序区仅剩一个元素时无序区最小值和第一个元素都是它自身无需再交换3.代码实现C语言void Select_Sort(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[j] arr[min]) { min j; } } //最小值下标不等于起始下标说明找到更小值执行交换 if (min ! i) { int tmp arr[min]; arr[min] arr[i]; arr[i] tmp; } } }4.特点1交换次数少2无论数据是否有序都需要完整遍历3适用场景对交换次数有要求、小规模数据四冒泡排序1.概述冒泡排序是一种交换排序它的基本思想是两两比较相邻记录的关键字如果反序则交换直到没有反序的记录为止。每一轮遍历结束后当前最大值都会“冒泡”到数组末尾像水泡上浮一样因此得名冒泡排序。2.核心原理重复遍历数组相邻两个元素两两比较如果前一个比后一个大就交换位置。3.代码实现C语言void Bubble_Sort(int arr[], int len) { //外层循环:控制排序总趟数 for (int i 0; i len - 1; i) { //内层循环:每一趟从左向右遍历待排序区间两两比较 //每完成一趟末尾i个元素已经有序无需再次比较 for (int j 0; j len - i - 1; j) { //相邻元素两两对比左侧元素大于右侧则交换 if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; } } } }4.特点1时间复杂度高数据量大时效率极低2适用场景小规模数据、几乎有序的数据5.冒泡排序的优化引入有序标记变量每一趟排序开始时默认数组已有序发生元素交换说明数组无序修改标记继续下一趟排序全程无交换说明数组已经完全有序直接终止排序不再执行剩余趟数。最优时间复杂度从 O(n²) 优化为 O(n)void Bubble_Sort_Plus(int arr[], int len) { //外层循环控制排序趟数 for (int i 0; i len - 1; i) { bool tag true; //每趟初始默认数组已有序 //遍历待排序区间两两比较交换 for (int j 0; j len - i - 1; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; tag false; //发生交换说明数组无序 } } //本趟无任何交换数组已经完全有序直接结束排序 if (tag) return; } }五归并排序1.概述“归并”的含义是将两个或两个以上的有序表合成一个新的有序表。归并排序就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录则可以看成是n个有序的子序列每个子序列的长度为1然后两两归并得到[n/2][x]表示不小于x的最小整数个长度为2或1的有序子序列再两两归并......如此重复直到得到一个长度为n的有序序列为止这种排序方法称为2路归并排序。2.核心原理纯分治思想先分后合1分将数组不断对半拆分拆到单个元素天然有序2合将两个有序子数组按大小规则合并为一个有序数组3逐层向上合并最终得到完整有序数组。3.代码实现C语言//归并排序:将两个有序子区间合并为一个有序区间 void Merge(int arr[], int left, int mid, int right) { //动态开辟临时数组存储合并后的有序序列 int* brr (int*)malloc((right - left 1) * sizeof(int)); if (NULL brr) exit(EXIT_FAILURE); //内存开辟失败容错 int i left; //左有序区间起始下标 int j mid 1; //右有序区间起始下标 int k 0;//临时数组存储下标 //同时遍历左右两个有序区间取较小值放入临时数组 while (i mid j right) { if (arr[i] arr[j]) { brr[k] arr[i]; } else { brr[k] arr[j]; } } //处理左区间剩余元素 while (i mid) { brr[k] arr[i]; } //处理右区间剩余元素 while (j right) { brr[k] arr[j]; } //将临时有序数组数据拷贝回原数组对应区间 for (int w left; w right; w) { arr[w] brr[w - left]; } //释放动态内存避免内存泄漏 free(brr); brr NULL; } //归并排序:递归拆分区间分治核心 void Divide(int arr[], int left, int right) { //递归终止条件:区间只有一个元素或无元素天然有序 if (left right) { return; } int mid (left right) / 2; //中间分界点拆分左右区间 //分好的左区间的范围 [left, mid] //分好的右区间的范围 [mid 1, right] //递归拆分左区间 [left, mid] Divide(arr, left, mid); //递归拆分右区间 [mid 1, right] Divide(arr, mid 1, right); //拆分完成合并两个有序区间 Merge(arr, left, mid, right); } //归并排序入口函数 void Merge_Sort(int arr[], int len) { //对整个数组区间执行分治归并 Divide(arr, 0, len - 1); }4.特点1八大排序中唯一时间复杂度完全稳定O(nlogn)且稳定的排序2适用场景对排序稳定性要求高、大数据外排序、链表排序六堆排序1.概述堆排序就是利用堆假设利用大顶堆进行排序的方法。它的基本思想是将待排序的序列造成一个大顶堆。此时整个序列的最大值就是堆顶的根节点。将它移走其实就是将其与堆数组的末尾元素交换此时末尾元素就是最大值然后将剩余的n-1个序列重新造成一个堆这样就会得到n个元素中的次小值。如此反复执行便能得到一个有序序列了。2.核心原理1将数组构建成大顶堆父节点大于左右子节点2堆顶就是最大值将堆顶和数组末尾元素交换末尾变为有序3剩余无序数组重新调整为大顶堆重复交换直到全部有序。3.代码实现C语言//堆排序:单次堆调整函数将指定子树调整为大顶堆 //start:当前需要调整的根节点下标 //end:堆的有效最后节点下标 void Heap_Adjust(int arr[], int start, int end) { //取出根节点值产生空白根节点位置 int tmp arr[start]; //maxchild默认指向根节点左孩子 int maxchild start * 2 1; //循环向下调整堆结构空白节点存在孩子则继续遍历 while (maxchild end) { //判断右孩子是否存在且更大更新最大孩子下标 if (maxchild 1 end arr[maxchild 1] arr[maxchild]) { maxchild; } //若最大孩子值小于等于根节点值满足大顶堆性质直接回填结束 if (arr[maxchild] tmp) { arr[start] tmp; return; } else { //最大孩子值更大孩子值上移填充空白位 arr[start] arr[maxchild]; //空白位下移继续向下调整 start maxchild; maxchild start * 2 1; } } //空白节点无孩子触底回填根节点原值完成调整 arr[start] tmp; return; } //堆排序入口函数 void Heap_Sort(int arr[], int len) { //初始建堆:从最后一个非叶子节点向前遍历由下至上构建大顶堆 for (int i (len - 1 - 1) / 2; i 0; i--) { Heap_Adjust(arr, i, len - 1); } //逐步交换堆顶与末尾元素缩减堆范围反复调整堆 for (int i len - 1; i 1; i--) //i代表的是要头尾交换的尾结点下标 { //交换堆顶最大值与当前末尾元素末尾区间转为有序 int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; //堆结构破坏重新调整根节点有效堆范围缩减为[0, i-1] Heap_Adjust(arr, 0, i - 1); } }4.特点1堆排序是选择排序的最优优化时间复杂度稳定O(nlogn)2适用场景要求排序时间稳定、大数据量七基数排序1.概述基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法2.核心原理基于桶排序思想按位排序、从低位到高位1找出数组最大值确定最大位数2从个位开始依次按照当前位数字放入对应桶中3按桶顺序回收数组逐位排序直到最高位排序完成数组整体有序。3.代码实现C语言//获取数组最大值的总位数 int Get_MaxNum_Figure(int arr[], int len) { //找出数组最大值 int max arr[0]; for (int i 0; i len; i) { if (arr[i] max) max arr[i]; } //统计最大值的位数 int count 1; while (max / 10) { count; } return count; } //获取数字num第digit位上的数值 //digit0:个位排序digit1:十位排序以此类推 int Get_Num_Digit(int num, int digit) { assert(digit 0); //右移digit位取出当前位 for (int i 0; i digit; i) { num / 10; } return num % 10; } //单趟基数排序:对数组按照第digit位进行桶排序 //digit0:个位排序digit1:十位排序以此类推 void Radix(int arr[], int len, int digit) { //1.申请0~9十个队列桶 std::queueint Buckets[10]; //2.遍历所有元素按当前位数值入桶 for (int i 0; i len; i) { //获取当前元素对应位数的数字确定桶下标 int index Get_Num_Digit(arr[i], digit); //元素进入对应桶 Buckets[index].push(arr[i]); } //3.按桶顺序依次出队覆盖原数组完成当前位有序 int k 0; for (int i 0; i 9; i) { //当前桶不为空全部取出放回原数组 while (!Buckets[i].empty()) { arr[k] Buckets[i].front(); Buckets[i].pop(); } } } //基数排序总入口函数 void Radix_Sort(int arr[], int len) { //获取数组最大值位数确定排序总趟数 int fig Get_MaxNum_Figure(arr, len); //从低位到高位逐位进行桶排序 for (int i 0; i fig; i) //i0代表按个数处理 i1代表按十位处理 以此类推 { Radix(arr, len, i); } }4.特点1非比较型排序速度远超比较排序2只能处理整数数据、需要额外空间3适用场景固定位数的整数排序数据之间位数差距不大的排序八快速排序1.概述快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小则可分别对这两部分记录继续进行排序以达到整个序列有序的目的。2.核心原理分治思想挖坑填数1从数组中选一个基准数2将数组分区小于基准数的放左边大于基准数的放右边3对基准数左右两个子数组重复分区操作直到全部有序。3.代码实现C语言1方法一递归实现//快速排序:单趟挖空法分区函数 //将数组以基准值为中心分为左右两部分返回基准值最终下标 int Partition(int arr[], int left, int right) { //取出最左端元素作为基准值用tmp临时保存防止被覆盖 int tmp arr[left]; //左右指针未相遇时持续分区 while (left right) { //从右向左遍历寻找小于等于基准值的元素 while (leftright arr[right] tmp) { right--; } //这个内部while循环结束会有两种情况 //情况1:指针相遇直接退出分区 if (left right) break; //情况2:指针未相遇但是找到了小于等于基准值的元素直接将其填入左侧空位 arr[left] arr[right]; //从左向右遍历寻找大于基准值的元素 while (leftright arr[left] tmp) { left; } //情况1:指针相遇直接退出分区 if (left right) break; //情况2:指针未相遇但是找到了大于基准值的元素直接将其填入右侧空位 arr[right] arr[left]; } //指针相遇位置即为基准值的正确位置将基准值填入 arr[left] tmp; //或 arr[right] tmp; //返回基准值下标 return left; //或 return right; } //快速排序递归分治函数 void Quick(int arr[], int left, int right) { //递归终止条件:区间无元素或只有单个元素天然有序 if (left right) return; //完成单趟分区获取基准下标 int par Partition(arr, left, right); //递归排序左区间小于基准值 Quick(arr, left, par - 1); //递归排序右区间大于基准值 Quick(arr, par 1, right); } //快速排序入口函数 void Quick_Sort(int arr[], int len) { //对整个数组执行快速排序 Quick(arr, 0, len - 1); }2方法二非递归实现//快速排序:非递归版 void Quick_Sort_No_Recursion(int arr[], int len)//非递归的方法 { //栈存储区间左右边界每一组区间存储两个值:左边界、右边界 std::stackint st; //初始整体区间入栈 st.push(0); st.push(len - 1); //栈不为空持续迭代处理所有分区 while (!st.empty()) { //取出当前待处理区间的左右边界 int right st.top(); st.pop(); int left st.top(); st.pop(); //执行单趟挖空法分区获取基准值下标 int par Partition(arr, left, right); //左区间若存在有效元素元素个数 2区间入栈等待后续处理 if (left par - 1) { st.push(left); st.push(par - 1); } //右区间存在有效元素元素个数 2区间入栈等待后续处理 if (par 1 right) { st.push(par 1); st.push(right); } } }4.特点1平均效率极高O(nlogn)、速度快2数据越乱效率越高数据越有序反而效率越低最坏退化成O(n²)3适用场景大规模无序数据、数据量极大的场景5.快速排序的优化核心思想打乱数据1快速排序启动时如果待排序序列数据量较小直接放弃快速排序调用直接插入排序或冒泡排序完成排序。针对原始整体数组2在快速排序持续分区过程中如果发现划分出的子区间长度小于设定阈值则直接对当前小区间使用直接插入排序或冒泡排序完成排序。针对拆分后的子区间3三数取中法从当前待排序区间中取出最左端、最右端、中间位置三个数值对比大小选取三者中“大小居中的值”交换到区间最左端作为本轮分区的基准值。4随机基准数法随机打乱数据在当前待排序区间内随机选取一个数值将其与区间最左端数值交换以随机值作为本轮分区的基准值。可多次随机交换进一步打乱有序性。三、总结排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度稳定性直接插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序或O(1)不稳定简单选择排序O(n²)O(n²)O(n²)O(1)不稳定冒泡排序O(n²)O(n)O(n²)O(1)稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定基数排序O(d(nr))O(d(nr))O(d(nr))O(nr)稳定快速排序O(nlogn)O(nlogn)O(n²)O(logn)不稳定
