前言

There are many ways to achieve sorting,比如：快排,桶排,希尔排序,radix sort etc..Today, we will introduce a kind of more classic bubble sort..冒泡排序,也是一种简单直观的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端.

一.Introduction of life examples

in a certain class in gym class10个人,From the playground1到10的10个位置,Now students randomly stand,The teacher now asks to sort the stations from low to high.for smooth sorting,Sports Committee proposes a way to stand：从起始位置1开始,站在1Comparison of position classmates with neighboring classmates,如果1classmate ratio2number classmate high,1No. 1 student and No. 2 student exchange places,此时原1Classmates are here2号位,Then the students continued to then compare adjacent classmates,Until I met students than the students in a location work not swap places,and stay in place.and then from1Number position starts to repeat the above comparison process.

The above is a concrete example of bubble sort,About the efficiency of bubble sort talks to below.

二、具体实现

1.冒泡排序原理

比较相邻的元素.如果第一个比第二个大,就交换他们两个.
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数.
针对所有的元素重复以上的步骤,除了最后一个.
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.

2.实现方法

1.Bubble sort is to finally determine the element position through continuous comparison,So take a loop to achieve.
Elements need to be compared one by one,Elements need to be swapped after comparing,Therefore, a double-layer cycle should be used..
以 9 8 7 6 5 4 3 2 1Compare as an example,9Each comparison swap places at the same time,9Comparison is finished
Now the element position is：8 7 6 5 4 3 2 1 9,接着从8start comparing again,最后一个数字9不用比较,重复上述步骤,The number of element comparisons gradually decreases.我们可以看出来,比较了8趟,所以有n个元素有n-1趟,to swap places at the same time,when the first exchange9对,依次减少,So the number of elements determines the exchange logarithm,Then it can be found that the number of passes and the number of elements are related,According to this, the idea of ​​​​a double-layer cycle is roughly

（伪代码）代码示例

思路：
*/遍历数组,对数组中相邻的两个元素进行比较,
如果需要升序,前一个数据大于后一个数据时,
交换两个位置上的数据,直到所有的数据比较完,
此时,最大的数据已经放在数组的末尾.
Except that the largest data is already sorted,The rest of the data is still not required,
The remaining data can be processed in a similar way to the above
*/ 
void BubbleSort(int array[], int n)
{
    
    // 外层循环控制冒泡排序的趟数
 
    for(int i = 0; i < n; ++i)
    {
    
        // 具体冒泡的方式：用相邻的两个元素进行比较,
        //前一个大于后一个元素时,交换着两个数据,
        //依次直到数组的末尾
        for(int j = 1; j < n-i; ++j)
        {
    
            if(array[j-1] > array[j])
            {
    
                int temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
            }
        }
    }

 }

3.效率问题

1.什么时候最快
当输入的数据已经是正序时（都已经是正序了,What's the use of bubble sort?）.
什么时候最慢
当输入的数据是反序时（写一个 for 循环反序输出数据不就行了,Why use bubble sort?）
2.算法复杂度
平均算法时间复杂度O(n^2),This is also the worst case time complexity,最好情况下是O(n).
3.优化改进
It is possible that all loops may not be completed during the bubble sort process,already sorted,就可以停下来,Programs can be optimized at this level,set flags to implement.But as said above if it is ordered,No need for bubble sort.In fact, I think it's a bit cheesy.

void BubbleSort(int array[], int size)
{
    
    for(int i = 0; i < size-1; ++i)
    {
    
        int isChange = 0; 

        for(int j = 1; j < size-i; ++j)
        {
    
            if(array[j-1] > array[j])
            {
    
                int temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
                
                isChange = 1;   
                // 如果本次冒泡进行数据交换了
                 //说明本次还是无序的,就将isChange设置为1
            }
        }
        
        // 如果本次冒泡中,元素没有交换
        //则本次开始冒泡时,数据已经有序了,后面的冒泡可以不用进行了
        if(!isChange)
            return;
    }
}

三.总结

1源代码：

#include<stdio.h>

void bubble_sort(int arr[],int n)
{
    
	
	int i = 0;
	for (i = 0; i < n; i++)
	{
    
		int j = 0;
		for (j = 0; j < n - i; j++)
		{
    
			if (arr[j] > arr[j + 1])
			{
    
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
}

int main()
{
    
	int arr[] = {
     3,1,7,5,8,9,0,2,4,6 };
	int n = sizeof(arr) / sizeof(arr[0]) - 1;
	bubble_sort(arr,n);
	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
    
		printf("%d ", arr[i]);
	}
	return

2.归纳
代码中定义的n 是减去1了的.
表示：最后一趟区间中只剩余1个元素,该趟冒泡可以省略
Code implementation is not too difficult,Understand the number of cycles,exchange logarithm,Just figure out the logic.
Sometimes you can draw pictures to help understand
3.The above is my simple understanding of bubble sort,如有错误.欢迎指正,谢谢指教！