C排序算法(一):冒泡排序
冒泡排序
冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们的位置交换过来。走访数列重复地进行直到排序完成。因为越大（小）的元素经过交换会慢慢”浮”到数列的顶端（尾端），就如同碳酸饮料中的气泡一样，故名“冒泡排序”。
算法原理
以从大到小降序排列为例。
- 第一走轮访开始 —-> 比较相邻的元素- —> 如果第一个元素比第二个元素小，就交换他们的位置，把小的放到后面 —-> 如果第二个比第三个小，同样交换他们的位置，以此类推 —-> 第一轮走访结束
这个时候最小的数就“浮”到最右端了
- 第二轮走访开始 —-> 比较相邻的元素- —> 如果第一个元素比第二个元素小，就交换他们的位置，把小的放到后面 —-> 如果第二个比第三个小，同样交换他们的位置，以此类推 —-> 第二轮走访结束
这时候倒数第二小的数就“浮”到倒数第二列了
- 第三轮走访开始 —-> 比较相邻的元素- —> 如果第一个元素比第二个元素小，就交换他们的位置，把小的放到后面 —-> 如果第二个比第三个小，同样交换他们的位置，以此类推 —-> 第三轮走访结束
这时候倒数第三小的数就“浮”到倒数第三列了
- 以此类推，最多经过n-1轮循环 …… …… ……
所有元素从大到小排序完成
实例演示
对2 3 1 5 4进行从大到小的降序排列。
第一轮走访开始
2 3 1 5 4 （比较2和3，交换位置） 3 2 1 5 4（比较2和1，不交换位置） 3 2 1 5 4 （比较1和5，交换位置） 3 2 5 1 4（比较1和4，交换位置） 3 2 5 4 1（第一轮走访结束）
最小的数1已经在最后面了，因此第二轮排序只需要对前面四个数进行再比较。
第二轮走访开始
3 2 5 4 1（比较3和2，不交换位置） 3 2 5 4 1（比较2和5，交换位置） 3 5 2 4 1（比较2和4，交换位置） 3 5 4 2 1（第二轮走访结束）
第二小的数已经排在倒数第二个位置了，所以第三轮只需要比较前两个元素。
第三轮走访开始
3 5 4 2 1（比较3和5，交换位置） 5 3 4 2 1（比较3和4，交换位置） 5 4 3 2 1（第三轮走访结束）
至此，排序结束。
C语言实现代码
#include<stdio.h>
#define N 10
int main(void)
{
int arr[N] = { 0,3,2,5,8,4,7,6,9,1 };//创建一个大小为N的数组，方便理解算法
int i = 0;//控制走访轮数
int j = 0;//控制数组元素下标
int temp = 0;//申请一个临时的空间（数组元素交换时需要一个临时空间）
for (i = 0; i < N; i++)
{
for (j = 0; j < N - i; j++)//内层循环j<n-i即可，得到n-i的最小值，最大值自然而然就冒出来了
{
if (arr[j] < arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
//for循环执行完毕，排序完成，依次打印出排序完成后的数组元素
for (i = 0; i < N; i++)//变量i清零赋予新的意义：控制打印个数
{
printf("%d ", arr[i]);
}
return 0;
} 加入用户输入程序
//常见代码会让用户输入他要排序的数据个数，但是有时候用户也不知道自己有几个数
//所以我想实现的是用户之输入一次数据，程序自动计算个数，然后在进行排序的一个过程
//但是调试之后你会发现下面的程序 有bug！有bug！有bug！
#include<stdio.h>
int main(void)
{
int arr[1000];//创建一个长度为1000的数组
int length = 0;//存放用户输入数据的个数
int i = 0;//控制用户输入数据个数
int j = 0;
int temp = 0;
printf("请输入您要排序的数列，数与数之间用空格隔开\n");
for(i = 0; getchar() != '\n';i++)
{
scanf("%d", &arr[i]);
if (arr[i] >= 0 && arr[i] < 1000)
{
length++;
}
}
printf("您总共输入了%d个数据，重新排序后的结果如下：\n",length);
for (i = 0; i < length; i++)//i清零赋予新的意义：在这里控制走访论数
{
for (j = 0; j < length - i; j++)
{
if (arr[j] < arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
//for循环执行完毕，排序完成，依次打印出排序完成后的数组元素
for (i = 0; i < length; i++)//变量i清零赋予新的意义：控制打印个数
{
printf("%d ", arr[i]);
}
return 0;
}对于上述程序bug的解决方案
如果你认真测试了这个程序，你会发现有bug，程序会吞入用户输入的第一个字符，那么这个bug该如何解决呢。
（我真的整整搞了一下午才发现，这对于刚入门的我也太太太太难了吧，差点就自闭了）
解决方法一：让用户在输入数据之前先输入一个字符给getchar() 解决方案二：申请一个flag整型变量，在第一次获取用户数据时将getchar()短路掉
//方案二更好一点，下面是按照方案二更改后的正确代码
int main(void)
{
int arr[1000];
int length = 0;
int i = 0;
int j = 0;
int temp = 0;
int flag = 1;//防止getchar（）吞掉用户输入字符
printf("请输入您要排序的数列，数与数之间用空格隔开\n");
for(i = 0; flag||getchar() != '\n';i++)
{
if (i == 0) flag--;//在i==0的时候，把getchar()短路掉,防止吞入用户输入的第一个字符。
scanf("%d", &arr[i]);
if (arr[i] >= 0 && arr[i] < 1000)
{
length++;
}
}
printf("您总共输入了%d个数据，重新排序后的结果如下：\n",length);
for (i = 0; i < length; i++)
{
for (j = 0; j < length - i; j++)
{
if (arr[j] < arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for (i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
return 0;
}对算法进行封装及调用
#include<stdio.h>
int arr[1000] ={ 0 } ;
int length =0;
//对于“获取用户输入函数功能”的封装
void scanf_sort(int* arr)
{
int i = 0;
int flag = 1;
printf("请输入您要排序的数列，数与数之间用空格隔开\n");
for (i = 0; flag || getchar() != '\n'; i++)
{
if (i == 0) flag--;
scanf("%d", &arr[i]);
if (arr[i] >= 0 && arr[i] < 1000)
{
length++;
}
}
printf("您总共输入了%d个数据，重新排序后的结果如下：\n", length);
}
//对于“冒泡排序“算法的封装
void bubble_sort(int* arr)
{
int i = 0;
int j = 0;
int temp = 0;
for (i = 0; i < length; i++)
{
for (j = 0; j < length - i; j++)
{
if (arr[j] < arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
//对于排序完成后“数组打印”功能函数的封装
int print_sort(int* arr,int length)
{
int i = 0;
for (i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
//函数调用
int main(void)
{
scanf_sort(arr);
bubble_sort(arr);
print_sort(arr,length);
return 0;
}
运行结果
虽然就实现了简单的**”计算用户输入数据的个数”和“排序”**的两个功能，但是我真的搞了一天哇，我太菜了……自闭中……
算法优化
以对于3 2 0 1 4 5 6 7 8 9从大到小排序，经过一轮排序后会变成2 0 1 3 4 5 6 7 8 9
可以发现原序列的后半部分是已经排好顺序了，所以在进行第二轮比较中，2没必要和4 5 6 7 8 9再进行多余的比较
用flag代表比较的轮次，k代表该每一轮的比较次数，该优化过程就是在每一轮次中都更新轮次flag的值，不断缩小冒泡排序原始轮次范围N，从而达到排序的最大效率，避免不必要的比较。
#include<stdio.h>
#define N 10
int main()
{
int arr[N] = { 3,0,1,2,4,5,6,7,8,9 };
int i = 0;
int j = 0;
int k = 0;
int temp = 0;
int count = 1;
int flag = 10;
while (flag > 0)
{
k = flag;//用k记录每一轮的比较次数
flag = 0;//while循环结束条件
for (j = 0; j < k - 1; j++)
if (arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = j + 1;//记录符合交换条件的最终位置
}
if (flag)
count++;//记录比较轮次
}
printf("比较轮次:%d\n", count);
for (i = 0; i < N; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}写在后面
啊啊啊啊啊，终于写完了，裂开了，人没了，写了整整一天，文中的那个bug我搞了整整一下午，这也太虐我这个小白了吧，太难了，还有最后一个算法优化我没有完全敲出来，借鉴其他博主的，改了一点点，还没搞懂代码一步步的逻辑，明日再看。应该还有其他的优化方案吧，后面学算法和数据结构的时候再继续搞。
休息去了…….
腾讯云开发者
