冒泡排序(bubble sort)基本原理很简单,如图所示:
这边方便大家快速观察顺序:
这边我们可以观察出冒泡排序是两两相比,每一趟都能确定最后一位成为本趟的最大值。 10个数字9趟就完成了。
那我们试着写写代码吧
void bubble_sort(int arr[], int sz)
{
int i = 0;//趟数
for (i = 0; i < sz-1; i++)//十个数字只用9趟
{
//每一趟里面的交换操作
int j = 0;
for (j = 0; j < sz-i-1; j++)//每趟都会固定一个数,所以不能写出j<sz-1
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
int main()
{
int arr[] = { 6,4,1,2,9,3,7,8,10,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr,sz);
//打印出来看看结果
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
代码到这已经能非常完美的实现冒泡排序了,但有没有想过我们只需要排序这样一个数组:
{10,1,2,3,4,5,6,7,8,9}
我们知道只需要将10放到最后一位,一趟就搞定了,但我们现在的代码还会将它循环9趟,那么如何提高我们的代码质量呢?
试想如果我们进入一趟内部,代码运行,但比较完一对都没有交换,是不是证明现在已经有序了。所以我们假设这个数组已经有序,但如果进入到交换数字的表达段落中,我们就把数组假设有序的开关关闭。
优化后代码:
void bubble_sort(int arr[], int sz)
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
int flag = 1;//假设数组有序
for (j = 0; j < sz - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = 0;//进行过交换数字,关闭开关
}
}
if (flag == 1)//如果经历过判断,没进入交换,那么数组已经有序
{
break;
}
}
}
int main()
{
int arr[] = { 6,4,1,2,9,3,7,8,10,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz);
//打印出来看看结果
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
这样一个简单的优化,我们的冒泡排序就很有含金量啦
将优化版本写成指针形式:
void bubble_sort(int* p, int sz)
{
int i = 0;
for (i = 0; i < sz - 1; i++)
{
int j = 0;
int flag = 1;
for (j = 0; j < sz - i - 1; j++)
{
if (*(p+j) > *(p+j+1))
{
int tmp = *(p+j);
*(p + j) = *(p + j + 1);
*(p + j + 1) = tmp;
flag = 0;
}
}
if (flag == 1)
{
break;
}
}
}
int main()
{
int arr[] = { 6,4,1,2,9,3,7,8,10,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, sz);
//打印出来看看结果
for (int i = 0; i < sz; i++)
{
printf("%d ", *(arr+i));
}
return 0;
}
有帮助点个三连,还有优化方案评论区求分享
标签:sort,sz,arr,int,冒泡排序,C语言,++,Mr,bubble From: https://blog.csdn.net/CPP_ZhouXuyang/article/details/141819472