目录
冒泡排序
理论
代码实现
时间复杂度
选择排序
理论
代码实现
时间复杂度
插入排序
理论分析
代码实现
时间复杂度
冒泡排序
理论
冒泡，我们很容易联想到水煮沸，或者是鱼儿吐泡的情景，水泡会在水中上升到达水面。冒泡排序正如其名，即大的数一个个往上冒出来。过程是在一个数组中从左至右依次进行两个数的比较，大的就向前进，小的给大的挪出位置。我们用图来加深这个理解。
如图即为一次冒泡的过程,数组nums有7个元素。可以看到第一次冒泡进行了6次比较(7-1),找出了数组中最大的元素。那我们可以由此推出：要确定7个元素的大小关系，我们要进行6次冒泡排序，每次冒泡要两两比较的次数都比上次少1(因为右边的数字位置都固定了)，等最后确定了倒数第二大数字的位置时，全部元素的大小位置就被排好了，冒泡排序结束。所以我们推广一下：n个元素需要n-1次冒泡，第一次冒泡要比较n-1次，后续的冒泡次数为n-1-i(i=0,1,2.....起到累加1的作用)。所以冒泡需要两层循坏：外层控制冒泡次数，内层控制两两元素比较次数。
代码实现
#include<stdio.h>
#include<stdlib.h>
#define L 7
//打印函数
void print(int* nums) {
for (int i = 0; i < L; i++) {
printf("%d ", nums[i]);
}
printf("\n");
}
int main() {
int i, j;
int* nums = (int*)malloc(sizeof(int) * L);//动态分配内存
for (i = 0; i < L; i++) {
scanf("%d", &nums[i]);
}
for (i = 0; i < 6; i++) {//外层循环控制冒泡次数
for (j = 0; j < 6 - i; j++) {内层循环控制比较次数
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
print(nums);
}
return 0;
}执行结果：
时间复杂度
我们看代码可以知道，双层循环，每一层循环都以n为基数进行操作，所以时间复杂度是O(n^2)。
选择排序
理论
和冒泡排序十分相似，从过程上看冒泡是每一次冒泡在最右侧确定出一个较大的数，而选择排序是每一次选择在最左侧确定一个较小的数。换句话说，冒泡是从右到左确定，选择是从左到右确定。
既然要从左到右确定数字位置，那么我们需要以最左侧未固定的数为基准，将数组进行扫描，选出数组中最小的数与基准数位置互换，然后基准数左移一位，以此类推。
如图所示，不难看出，7个元素的数组，经过6次选择(即选择出未固定的最小数)固定出了数组内的所有数位置。推广一下，n个元素的数组，经过了n-1次选择，能得出结果。而我们还不知道的是，每次选择中怎么比较呢？我们从基准数开始向后遍历数组，找出后面的最小数，再进行基准数与最小数的交换，这样来看，双层循环的步骤也就十分明了了。
代码实现
#include<stdio.h>
#include<stdlib.h>
#define L 7
//打印函数
void print(int* nums) {
for (int i = 0; i < L; i++) {
printf("%d ", nums[i]);
}
printf("\n");
}
int main() {
int i, j, min = 0;
int* nums = (int*)malloc(sizeof(int) * L);//动态分配内存
for (i = 0; i < L; i++) {
scanf("%d", &nums[i]);
}
for (i = 0; i < 6; i++) {//设置基准
min = i;//更新min(min代表最小值在数组中的索引)
for (j = i + 1; j < L; j++) {//遍历数组后方
if (nums[j] < nums[min]) {
min = j;
}
}
//交换基准与最小值的位置
int temp = nums[min];
nums[min] = nums[i];
nums[i] = temp;
print(nums);
}
return 0;
}
时间复杂度
从代码看出双层循环每层循环仍然以n为基数，所以时间复杂度也为O(n^2)。
插入排序
理论分析
插入排序就是从前往后遍历，将小的数插在合适的位置(左边的数小于它，右边的数大于等于它)。从过程上分析，我们需要以一个数为基准，遍历它左边的数，来找到基准数合适的插入位置，然后将基准数左边的比它大的数都右移一位，给基准数挪出位置，在将基准书插入到这个位置中。所以我们要用到双指针 i 和 j 。i用来遍历数组中基准数前面的数，j用来指向基准数的位置(默然第一个数已经排好了顺序，从第二数开始)。我们用图来加深理解。
我们看图可以发现，基准值的合适位置其实就是比它大的数中最小数所在的位置。基准数挪出位置供左边比它大的那些数向右移，而反过来这些数右移又能为基准数挪出那个合适的位置。文章来源：https://www.toymoban.com/news/detail-836833.html
代码实现
#include<stdio.h>
#include<stdlib.h>
#define L 7
void print(int nums[], int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", nums[i]);
}
printf("\n");
}
void insertsort(int nums[], int len)
{
for (int i = 1; i < len; i++)//从第二个元素开始定基准
{
for (int j = 0; j < i; j++)//遍历基准的前面的数
{
if (nums[i] < nums[j])//找到基准的合适位置(j的索引)
{
int temp = nums[i];//保存基准值
//整体右移
for (int k = i-1; k>=j; k--)
nums[k + 1] = nums[k];
nums[j] = temp;//将基准值插入合适的位置
}
}
printArray(nums, len);
}
}
int main()
{
int* nums = (int*)malloc(sizeof(int) * L);//动态分配内存
for (int i = 0; i < L; i++) {
scanf("%d", &nums[i]);
}
insertsort(nums, L);
return 0;
}时间复杂度
插入排序若是递增序列，有n-1次插入，每次插入要比较 i 次(i是以n为基数的)，所以时间复杂度为O(n^2),若是递减序列，有n-1次插入，每次插入要比较1次，然后进行i-1-k次右移操作(i和j均以n为基数)，所以也是O(n^2)。文章来源地址https://www.toymoban.com/news/detail-836833.html
到了这里，关于排序算法一：冒泡、选择、插入排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
