排序算法有三类1.选择排序2.冒泡排序3.插入排序选择排序选择排序核心思想每一轮从待排序的元素中选出最小的一个放到已排序序列的末尾。#includestdio.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(i0;ilen-1;i) //控制要对比的开始位置 开始位置前数组是已排序的 9 { 10 for(ji1;jlen;j) //控制要与开始位置对比的数 11 { 12 if(a[i]a[j]) //如果开始位置的数更大则交换位置使得开始位置的数趋于最小 13 { 14 int ta[i]; //开始交换 15 a[i]a[j]; 16 a[j]t; //结束交换 17 } 18 } 19 } 20 for(i0;ilen;i) 21 { 22 printf(a[%d]%d\n,i,a[i]); //输出数组的所有值 23 } 24 printf(len%d\n,len); 25 return 0; 26 }易错点内层循环需要从i1开始若从i开始则a[i]会与a[i]自己比较一次外循环i需要从0开始因为数组从a[0]开始特点时间复杂度O(n²)无论好坏空间复杂度O(1)交换次数最少这里我写的选择排序遇到更小的立刻交换也可以记录最小的数据下标遍历之后再交换以减少交换次数冒泡排序1 #includestdio.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(jlen;j1;j--) //控制未排序数组的位置使得程序不在有序位置进行对比 10 { 11 for(i0;ij-1;i) //在未排序数组中逐个对比 12 { 13 if (a[i]a[i1]) 14 { 15 int t a[i]; 16 a[i]a[i1]; 17 a[i1]t; 18 //交换 19 } 20 } 21 } 22 for(i0;ilen;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 #includestdio.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 j0; 9 for(i0;i10;i) //a[i]是要插入的数 10 { 11 int t a[i]; 12 ji; 13 while(j0 tb[j-1]) //j0条件是为了防止数组越界当要插入的数更小时说明要插入的数应该在对比数的前面对比数后移让出位置j--继续对比 14 { 15 b[j]b[j-1]; 16 j--; 17 } 18 b[j]t; 19 } 20 for(i0;i10;i) //打印数组b 21 printf( %d\n,b[i]); 22 return 0; 23 } 24 //插入排序核心思想在于寻找我新拿来要插入的数需要放在已有数组的什么位置找到位置并空出位置后插入就好了注意插入排序初始插入第一个数时只有一个数所以认为其已排序然后依次取出元素插入合适位置保持已排序部分始终有序。特点时间复杂度O(n²)最坏O(n)最好已有序时空间复杂度O(1)稳定排序数据量小或基本有序时效率高
