三大主要排序方法总结：快速排序，选择排序，冒泡排序
三大主要排序方法总结：快速排序，选择排序，冒泡排序
用户11039529
发布于 2024-03-25 15:13:02
发布于 2024-03-25 15:13:02
本文介绍：三大排序方法（快速排序，选择排序，冒泡排序）（后续期间可能会发布一篇关于qsort函数的文章）
自我介绍：一个脑子不好的大一学生，c语言接触还没到半年，若涉及到效率等问题，各位都可以在评论区提出见解，谢谢啦。
该账号介绍：此帐号会发布游戏（目前还只会简单小游戏），算法，基础知识等内容。
文章特点：会将重要步骤和易错点在代码中用注释标示（方便各位理解和定位）
1.选择排序
（1）初始版本
在整个数组中选择最小的数,放到最前的位置
动图链接：
https://img-blog.csdnimg.cn/20200629172829794.gif
//选择排序
//在整个数组中选择最小的数,放到最前的位置
void xuan_ze_pai_xu(int* arr,int n)
{
for(int j=0;j<n-1/**/; j++)
{
//n-1的原因：当min=n-2时，n-1前面都为小于下标为n-1的元素，无需再进行一次比较，影响效率
int min=j;
/*要更新最开始min的下标*/
for (int i =j+1/**/; i < n; i++)
{
if (arr[i] < arr[min])
min = i;
/*更新最小值的下标，方便后续调换其到 当时比较范围的最前面的位置（j所在位置）*/
}
//调换最小值到对应位置
int t = arr[min];
arr[min] = arr[j];
arr[j] = t;
}
}
int main()
{
int n, arr[1000] = { 0 };//n：数组元素个数
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
xuan_ze_pai_xu(arr, n);
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}（2）优化版本
通过同时找筛查范围的最大值和最小值下标，并将其分别移至该数组的最前方和最后方，以减少其比较次数（以下图片方便理解）
//选择排序优化
void xuan_ze_pai_xu(int *arr, int sz)
{
int l=0, r=sz-1;
//l:左下标，r:右下标
while (l < r)
{
int max=r, min=l;
/*必须得放入循环内，因为进行完一次排序后要更新下一次排序后最大最小值的位置*/
//max:剩下的数中的最大值的下标，min:剩下的数中的最小值的下标
for (int i = l;i <= r; i++)
{/*注意是<=*/
if (arr[i] < arr[min])
min = i;//更新最值下标
if (arr[i] > arr[max])
max = i;//更新最值下标
}
//调换最大值和最小值到相应位置
if (min != l)
{
int t = arr[min];
arr[min] = arr[l];
arr[l] = t;
}
if (max == l)
//如果最大元素的下标在一开始l所在的位置，
//因为在上半部分已经改掉下标为l的元素的值为最小值，
//所以原来l对应的元素值已被调换至min下标的位置
//因此要进行max=min的操作;
//(若先是调换最大值到r所指位置，后调换最小值到l所指位置，则该处写为：min=max)
max = min;
/*!!!!!!!!!超级关键的关键点!!!!!!!!!!*/
if (max != r)
{
int t = arr[max];
arr[max] = arr[r];
arr[r] = t;
}
/*以下为错误写法*/
/*if (min != l)
{
int t = arr[min];
arr[min] = arr[l];
arr[l] = t;
}
if (max != r)
{
int t = arr[max];
arr[max] = arr[r];
arr[r] = t;
}*/
l++;
r--;
/*更新左下标和右下标*/
}
}
//10
//9 8 7 6 5 4 3 2 1 0
//5 32 29 66 91 82
//测试数据
int main()
{
int n,arr[1000] = { 0 };//n：数字个数
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
xuan_ze_pai_xu(arr, n);
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}2.冒泡排序
通过相邻两数的比较，将大的数逐渐移至数组较后的位置，最后将最大的元素冒泡至最后
理解动图：https://img-blog.csdnimg.cn/2020062712431452.gif
//冒泡排序
通过相邻两数的比较，将大的数逐渐移至数组较后的位置，最后将最大的元素冒泡至最后
/*若有n个元素，则一共会进行n-1次排序，每次会把最大的推到最后，在推到最后的过程中
会进行n-1-i次操作*/
/*是j和j+1比较，相邻两数比较*/
void mao_pao_paixu(int* arr, int sz)
{
int i = 0;
for (int i = 0; i < sz-1/**/; i++)
{
//外循环，会进行sz-1次比较（10个数只进行9次比较）
for (int j = 0/*从0开始，而不是i+1*/; j < sz - 1 - i/*!!!!!!!!!*/; j++)
{
/*内循环，会进行sz-1-i次比较（与外循环原理相同）*/
if (arr[j] > arr[j+1/**/])
{
int t = arr[j+1];
arr[j+1] = arr[j];
arr[j] = t;
}
}
}
}
int main()
{
int arr[] = { 10,9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);/**/
mao_pao_paixu(arr, sz);
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}3.快速排序
思路：
先取a[0]为基准值，左指针为0，右指针为n-1，i=左指针，j=右指针，如果a[j]>=基准值，j向左移动，如果不是，则a[i++]=a[j]；如果a[i]<=基准值，i向右移动，如果不是，则a[j--]=a[i]；直到i等于j，本次循环结束（左边已经全为小于基准值的数，右边已经全为大于基准值的数，令a[i]=基准值）,递归进入下一次循环，参数为：pai_xu(a,l,i-1);pai_xu(a,i+1,r);
动图链接：https://img-blog.csdnimg.cn/20210515183213169.gif#pic_center#pic_center
（动图中的key即为我的：ji_zhun）
关键：l,r,ji_zhun，递归
void pai_xu(int* a/*或者int a[]*/, int l, int r)
{
if (l < r)
{
int i = l,j=r,ji_zhun=a[l];
while (i < j)
{
while (i < j && a[j] >= ji_zhun)
{
j--;
}
if (i < j)
a[i++] = a[j];
while (i < j && a[i] <= ji_zhun)
{
i++;
}
if (i < j)
a[j--] = a[i];
}
a[i] = ji_zhun;
pai_xu(a, l, i - 1);
pai_xu(a, i+1, r);
}
}
int main()
{
int a[10000];
int n = 10;
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
int ji_zhun = a[0],l=0,r=n-1;
pai_xu(a,l,r);
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}今天时2024年1月1日，在此对大家说一句：元旦快乐，祝你在新的一年收获满满，健健康康，平平安安
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-01-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录