排序算法是计算机科学中最基础且核心的组成部分无论是数据处理、数据库查询还是算法竞赛高效的排序都是提升程序性能的关键。对于 C 语言初学者和开发者而言深入理解经典排序算法的原理与实现是夯实编程基础、培养算法思维的重要一步。本文将以 C 语言为载体详细剖析三种最经典、最常用的排序算法快速排序、冒泡排序和选择排序。我们将从算法思想、时间复杂度、稳定性等理论层面入手并结合清晰易懂的 C 语言代码实现逐步拆解每个算法的执行流程与关键细节。通过对比这三种算法的优缺点与适用场景希望能帮助读者建立起对排序算法的系统认知并能在实际编程中灵活运用。一、快速排序优点快排是不稳定排序但效率最高时间复杂度最好 / 平均O(n log n)最坏O(n²)思路选一个基准数把数组分成「比它小的」和「比它大的」两部分把基准数放到它最终的正确位置上对这两部分分别重复上面的操作直到所有数都排好序代码#includestdio.hintpartition(inta[],ints,intt){intis;intjt;inttmpa[i];while(i!j){// 只要左右指针没相遇就继续执行while(ijtmpa[j]){j--;// 从右往左找只要右边元素比基准大就将指针向左移动一个}a[i]a[j];// 如果右边元素比基准小将这个元素往前挪 i 的位置此时相当于这个元素位置是一个洞while(ijtmpa[i]){i;// 从左往右找如果左边元素比基准小左指针向后移动一个}a[j]a[i];// 将此时这个元素放到有洞的位置现在这个位置有洞}a[i]tmp;// 直到左右指针相遇此时有洞的位置就是基准应该在的正确位置returni;}voidquicksort(inta[],ints,intt){if(st){intipartition(a,s,t);quicksort(a,s,i-1);quicksort(a,i1,t);}}voidprintArray(inta[],intn){inti;for(i0;in;i){printf(%d ,a[i]);}}intmain(){inta[5]{5,3,8,4,2};intnsizeof(a)/sizeof(a[0]);printf(排序前:\n);printArray(a,n);printf(\n);printf(排序后:\n);quicksort(a,0,n-1);printArray(a,n);}注意点外层循环 while (i ! j)作用直到指针相遇才停止内层必须加 i j作用防止越界崩溃先从右往左扫 j再从左往右扫 i顺序不能反所有比较都用 tmp不要用 a[s]递归公式固定模板quicksort(a,s,i-1);quicksort(a,i1,t);递归出口 if (s t)不写会无限递归崩溃二、冒泡排序优点稳定复杂度最优O(n)平均、最坏O(n²)核心思路相邻两个元素两两比较逆序就交换每一轮遍历最大元素会逐步“冒泡”到末尾总共遍历数组长度 - 1 轮后续轮次只需比较未排序部分可优化某轮无交换说明已有序直接结束代码如下示例#includestdio.hvoidbubbleSort(inta[],intn){inti,j;intflag;for(i0;in-1;i){// 管跑了几轮每次循环过后最大的都已经在后面flag0;// 标记是否发生交换for(j0;jn-i-1;j){// 管每一轮都交换几次后面 n-i-1 个都已经排好了if(a[j]a[j1]){inttempa[j];a[j]a[j1];a[j1]temp;flag1;}}if(flag0){// 说明已经交换好了break;}}}voidprintArray(inta[],intn){inti;for(i0;in;i){printf(%d ,a[i]);}}intmain(){inta[5]{5,3,8,4,2};intnsizeof(a)/sizeof(a[0]);printf(排序前:\n);printArray(a,n);printf(\n);printf(排序后:\n);bubbleSort(a,n);printArray(a,n);}三、选择排序优点时间最优 / 平均 / 最坏 O(n²)空间O(1)稳定性不稳定思路每一轮在未排序区间找出最小值和区间首位元素交换逐步敲定有序部分。划分已排序、未排序两段遍历未排序区记录最小元素下标最小数换到未排序区开头重复操作全部元素归位代码#includestdio.hvoidselectSort(inta[],intn){inti,j,minindex;for(i0;in-1;i){// 有 n 个元素外面进行 n-1 次循环确定每次循环的起点minindexi;for(ji1;jn;j){// 内层循环找出最小数if(a[j]a[minindex]){minindexj;// 将最小下标找出来}}inttempa[i];a[i]a[minindex];a[minindex]temp;}}voidprintArray(inta[],intn){inti;for(i0;in;i){printf(%d ,a[i]);}}intmain(){inta[5]{5,3,8,4,2};intnsizeof(a)/sizeof(a[0]);printf(排序前:\n);printArray(a,n);printf(\n);printf(排序后:\n);selectSort(a,n);printArray(a,n);}总结本文详细介绍了 C 语言中三种经典的排序算法快速排序、冒泡排序和选择排序。快速排序以其分治思想著称平均时间复杂度为 O(n log n)是三者中效率最高的适用于大规模数据排序但需要注意其不稳定性和最坏情况下的性能退化。冒泡排序实现简单直观具有稳定性通过相邻元素比较和交换完成排序。虽然其平均和最坏时间复杂度为 O(n²)但在数据基本有序时通过优化可达到 O(n) 的最佳复杂度。选择排序同样简单通过不断选择未排序部分的最小元素进行交换。它不稳定且时间复杂度恒为 O(n²)但其空间复杂度低交换次数少在数据量小或对交换成本敏感的场景下有一定价值。掌握这三种基础排序算法不仅有助于理解更复杂的算法思想也是面试和笔试中的常见考点。建议读者在理解原理的基础上亲手实现代码并通过调试观察排序过程从而加深对算法本质的理解。
C语言三大经典排序算法详解：快速排序、冒泡排序与选择排序
排序算法是计算机科学中最基础且核心的组成部分无论是数据处理、数据库查询还是算法竞赛高效的排序都是提升程序性能的关键。对于 C 语言初学者和开发者而言深入理解经典排序算法的原理与实现是夯实编程基础、培养算法思维的重要一步。本文将以 C 语言为载体详细剖析三种最经典、最常用的排序算法快速排序、冒泡排序和选择排序。我们将从算法思想、时间复杂度、稳定性等理论层面入手并结合清晰易懂的 C 语言代码实现逐步拆解每个算法的执行流程与关键细节。通过对比这三种算法的优缺点与适用场景希望能帮助读者建立起对排序算法的系统认知并能在实际编程中灵活运用。一、快速排序优点快排是不稳定排序但效率最高时间复杂度最好 / 平均O(n log n)最坏O(n²)思路选一个基准数把数组分成「比它小的」和「比它大的」两部分把基准数放到它最终的正确位置上对这两部分分别重复上面的操作直到所有数都排好序代码#includestdio.hintpartition(inta[],ints,intt){intis;intjt;inttmpa[i];while(i!j){// 只要左右指针没相遇就继续执行while(ijtmpa[j]){j--;// 从右往左找只要右边元素比基准大就将指针向左移动一个}a[i]a[j];// 如果右边元素比基准小将这个元素往前挪 i 的位置此时相当于这个元素位置是一个洞while(ijtmpa[i]){i;// 从左往右找如果左边元素比基准小左指针向后移动一个}a[j]a[i];// 将此时这个元素放到有洞的位置现在这个位置有洞}a[i]tmp;// 直到左右指针相遇此时有洞的位置就是基准应该在的正确位置returni;}voidquicksort(inta[],ints,intt){if(st){intipartition(a,s,t);quicksort(a,s,i-1);quicksort(a,i1,t);}}voidprintArray(inta[],intn){inti;for(i0;in;i){printf(%d ,a[i]);}}intmain(){inta[5]{5,3,8,4,2};intnsizeof(a)/sizeof(a[0]);printf(排序前:\n);printArray(a,n);printf(\n);printf(排序后:\n);quicksort(a,0,n-1);printArray(a,n);}注意点外层循环 while (i ! j)作用直到指针相遇才停止内层必须加 i j作用防止越界崩溃先从右往左扫 j再从左往右扫 i顺序不能反所有比较都用 tmp不要用 a[s]递归公式固定模板quicksort(a,s,i-1);quicksort(a,i1,t);递归出口 if (s t)不写会无限递归崩溃二、冒泡排序优点稳定复杂度最优O(n)平均、最坏O(n²)核心思路相邻两个元素两两比较逆序就交换每一轮遍历最大元素会逐步“冒泡”到末尾总共遍历数组长度 - 1 轮后续轮次只需比较未排序部分可优化某轮无交换说明已有序直接结束代码如下示例#includestdio.hvoidbubbleSort(inta[],intn){inti,j;intflag;for(i0;in-1;i){// 管跑了几轮每次循环过后最大的都已经在后面flag0;// 标记是否发生交换for(j0;jn-i-1;j){// 管每一轮都交换几次后面 n-i-1 个都已经排好了if(a[j]a[j1]){inttempa[j];a[j]a[j1];a[j1]temp;flag1;}}if(flag0){// 说明已经交换好了break;}}}voidprintArray(inta[],intn){inti;for(i0;in;i){printf(%d ,a[i]);}}intmain(){inta[5]{5,3,8,4,2};intnsizeof(a)/sizeof(a[0]);printf(排序前:\n);printArray(a,n);printf(\n);printf(排序后:\n);bubbleSort(a,n);printArray(a,n);}三、选择排序优点时间最优 / 平均 / 最坏 O(n²)空间O(1)稳定性不稳定思路每一轮在未排序区间找出最小值和区间首位元素交换逐步敲定有序部分。划分已排序、未排序两段遍历未排序区记录最小元素下标最小数换到未排序区开头重复操作全部元素归位代码#includestdio.hvoidselectSort(inta[],intn){inti,j,minindex;for(i0;in-1;i){// 有 n 个元素外面进行 n-1 次循环确定每次循环的起点minindexi;for(ji1;jn;j){// 内层循环找出最小数if(a[j]a[minindex]){minindexj;// 将最小下标找出来}}inttempa[i];a[i]a[minindex];a[minindex]temp;}}voidprintArray(inta[],intn){inti;for(i0;in;i){printf(%d ,a[i]);}}intmain(){inta[5]{5,3,8,4,2};intnsizeof(a)/sizeof(a[0]);printf(排序前:\n);printArray(a,n);printf(\n);printf(排序后:\n);selectSort(a,n);printArray(a,n);}总结本文详细介绍了 C 语言中三种经典的排序算法快速排序、冒泡排序和选择排序。快速排序以其分治思想著称平均时间复杂度为 O(n log n)是三者中效率最高的适用于大规模数据排序但需要注意其不稳定性和最坏情况下的性能退化。冒泡排序实现简单直观具有稳定性通过相邻元素比较和交换完成排序。虽然其平均和最坏时间复杂度为 O(n²)但在数据基本有序时通过优化可达到 O(n) 的最佳复杂度。选择排序同样简单通过不断选择未排序部分的最小元素进行交换。它不稳定且时间复杂度恒为 O(n²)但其空间复杂度低交换次数少在数据量小或对交换成本敏感的场景下有一定价值。掌握这三种基础排序算法不仅有助于理解更复杂的算法思想也是面试和笔试中的常见考点。建议读者在理解原理的基础上亲手实现代码并通过调试观察排序过程从而加深对算法本质的理解。
