当前位置：首页 > news >正文

C语言--排序算法

news 2026/7/24 23:31:52

排序算法有三类：

1.选择排序

2.冒泡排序

3.插入排序

选择排序：

选择排序核心思想：每一轮从待排序的元素中选出最小的一个，放到已排序序列的末尾。

#include<stdio.h> 2 3 int main(int argc, const char *argv[]) 4 { 5 int i,j; 6 int a[]={8,6,2,9,3,5,1,7,4,10}; 7 int len = sizeof(a)/sizeof(a[0]); //获取数组长度 8 for(i=0;i<len-1;i++) //控制要对比的开始位置 开始位置前数组是已排序的 9 { 10 for(j=i+1;j<len;j++) //控制要与开始位置对比的数 11 { 12 if(a[i]>a[j]) //如果开始位置的数更大，则交换位置，使得开始位置的数趋于最小 13 { 14 int t=a[i]; //开始交换 15 a[i]=a[j]; 16 a[j]=t; //结束交换 17 } 18 } 19 } 20 for(i=0;i<len;i++) 21 { 22 printf("a[%d]=%d\n",i,a[i]); //输出数组的所有值 23 } 24 printf("len=%d\n",len); 25 return 0; 26 }

易错点：内层循环需要从i+1开始，若从i开始则a[i]会与a[i]自己比较一次

外循环i需要从0开始，因为数组从a[0]开始

特点：

时间复杂度：O(n²)（无论好坏）
空间复杂度：O(1)
交换次数最少
这里我写的选择排序遇到更小的立刻交换，也可以记录最小的数据下标，遍历之后再交换以减少交换次数

冒泡排序：

1 #include<stdio.h> 2 3 int main(int argc, const char *argv[]) 4 { 5 int a[9]={5,2,6,8,3,9,1,4,7}; 6 int i; 7 int len =sizeof(a)/sizeof(a[0]); //获取数组长度 8 int j; 9 for(j=len;j>1;j--) //控制未排序数组的位置，使得程序不在有序位置进行对比 10 { 11 for(i=0;i<j-1;i++) //在未排序数组中逐个对比 12 { 13 if (a[i]>a[i+1]) 14 { 15 int t = a[i]; 16 a[i]=a[i+1]; 17 a[i+1]=t; 18 //交换 19 } 20 } 21 } 22 for(i=0;i<len;i++) //打印数组 23 { 24 printf("a[%d] = %d\n",i,a[i]); 25 } 26 return 0; 27 } 28 //冒泡排序，核心思想在于让较大的数交换到右边，然后最右侧就有部分是有序的，下一次不需要再检查有序部分，循环进行此步骤让整个数组有序

冒泡排序基本流程：两数对比，排序（顺序不符的情况下交换），i++对比下一对数，一遍走完之后可以确定最大（小）数在最左（右）边，则可以确定那部分数是有序的，下一次不必再对比。

特点：

时间复杂度：O(n²)（最坏），O(n)（最好，已有序时）
空间复杂度：O(1)
稳定排序

插入排序：

1 #include<stdio.h> 2 3 int main(int argc, const char *argv[]) 4 { 5 int a[10]={8,6,0,3,5,2,1,9,7,4}; 6 int b[10]; 7 int i; 8 int j=0; 9 for(i=0;i<10;i++) //a[i]是要插入的数 10 { 11 int t = a[i]; 12 j=i; 13 while(j>0 && t<b[j-1]) //j>0条件是为了防止数组越界，当要插入的数更小时，说明要插入的数应该在对比数的前面，对比数后移让出位置，j--继续对比 14 { 15 b[j]=b[j-1]; 16 j--; 17 } 18 b[j]=t; 19 } 20 for(i=0;i<10;i++) //打印数组b 21 printf(" %d\n",b[i]); 22 return 0; 23 } 24 //插入排序核心思想在于寻找我新拿来要插入的数需要放在已有数组的什么位置，找到位置并空出位置后插入就好了

注意，插入排序初始插入第一个数时，只有一个数所以认为其已排序，然后依次取出元素插入合适位置，保持已排序部分始终有序。

特点：