冒泡排序

@[TOC]

无内鬼，直入主题！

冒泡排序的思想核心是：比较两两相邻的元素，并且可能的话需要交换

说人话就是

把原本是9，8，7，6，5，4，3，2，1，0的数组

变成0 ，1，2，3，4，5，6，7，8，9

也可以把无序的数组排列为有序（从小到大or从大到小）

基本的流程如下图：

同时我们可以计算出，0·9这十个数字，重新排列完需要循环9次

也就是N个数字需要N-1趟的排列

代码实现

说完了原理，还是需要敲代码来实现

“老铁们int main return 0走一波！”

#include<stdio.h>
int main()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 }；//排序为升序 - 冒泡排序
    int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz);//冒泡排序的自定义函数
	return 0;
}

一维数组[]中的元素个数可以省略

SZ的位置问题

这里必须要注意的一点是

sizeof必须在主函数中计算元素个数

因为如果在自定义函数中计算的话

void bubble_sort(int arr[])
{
	int sz = sizeof(arr) / sizeof(arr[0]);//放在此处sz计算为1，err
    for (i = 0; i < sz; i++)
}

SZ计算出来的结果是1

arr数组名，传送的是数组首元素的地址
arr作为形参，无法计算内部元素个数
对后续要进行的操作如for循环中的 i<sz来说自定义函数中计算的sz是无效的

更具体的原因在上一篇博客《什么是数组名？》中有介绍

排除此问题后，sz计算出的元素个数就是我们的N

这里以i为趟数，i<sz指趟数需小于元素个数

void bubble_sort(int arr[], int sz)//形参arr本质是指针
{
	//确定趟数
	int i = 0;
	for (i = 0; i < sz; i++)
	{
        //
	}
}

接着书写第二环的for循环，即每一趟冒泡排序的操作

       //一趟冒泡排序
int j = 0;
for (j = 0; j < sz - 1 - i; j++)
{
	if (arr[j] > arr[j + 1] )
	{
              //
	}
}

这里需要注意的是j与sz的大小关系

按照前面的流程图，每运行一趟冒泡序列，就会有一个数字被移动到数组的最后面

N个元素需要进行N-1次冒泡排序，同时经过一趟后，新的最后一个元素无需重新比对排序

所以 j<sz-1-i

比较&交换

因为int arr传入的是指针变量，如果想要自定义函数影响函数外的内容，也必须使用指针变量

          //交换
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;

实际进行两个数字之间的比较和交换的是上述代码

tmp这个空盒子也是我们的老朋友了

总结起来完整的自定义函数如下

void bubble_sort(int arr[], int sz)//因为在主函数中计算sz，这里需要加上int sz
{
	//确定趟数
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		//一趟冒泡排序
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1] )
			{
				//交换
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}