冒泡排序和插入排序（详解）

我不是女神ヾ 2024-04-01 15:29 73阅读 0赞

#### 基本排序 ####

*  一.冒泡排序（详解）
 *  二.插入排序

## 一.冒泡排序（详解） ##

![在这里插入图片描述][ef9d7f79736d4941a7ff35f2da5ea1c1.png]

**1.由来**

> **冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。  
> 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。  
> 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。**

**2.算法原理**

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

**简而言之：就就如打擂台一样，两两相比，谁大谁就向后站**

void Order(int* arr, int sz)
    {
        
    	int i = 0;
    	int j = 0;
    	int tmp = 0;
    	for (i = 0; i < sz - 1; i++)
    	{
                                     //每次i循环一次后，最后那个数就会变为
    		int count = 0;            //最大，就不需要再让它跑一趟了
    		for (j = 0; j < sz - 1 - i; j++)
    		{
        //size-1-i是因为每一趟就会少一个数比较
    			if (arr[j] > arr[j + 1])
    			{
        //这是升序，如果条件成立，前一个数就和后一个交换位置
    				tmp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = tmp;
    				count = 1;
    			}
    		}
    		if (count == 0)
    		{
        //如果一趟下来都不需要交换顺序，那么就证明排序完全
    			break;
    		}
    	}
    }

*以下是全部代码*

void Order(int* arr, int sz)
    {
        
    	int i = 0;
    	int j = 0;
    	int tmp = 0;
    	for (i = 0; i < sz - 1; i++)
    	{
        
    		int count = 0;
    		for (j = 0; j < sz - 1 - i; j++)
    		{
        
    			if (arr[j] > arr[j + 1])
    			{
        
    				tmp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = tmp;
    				count = 1;
    			}
    		}
    		if (count == 0)
    		{
        
    			break;
    		}
    	}
    }
    int main()
    {
        
    	int arr[] = {
         10,5,8,1,3,4,9,21,6 };
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	Order(arr, sz);
    
    	int i = 0;
    	for (i = 0; i < sz; i++)
    	{
        
    		printf("%d ", arr[i]);
    	}
    
    	return 0;
    }

![在这里插入图片描述][3ae93925154642e198c9caaaf25375ee.png]

## 二.插入排序 ##

> **插入排序其实就跟我们玩牌时一样，找到一个牌插到比它大的牌的前面。具体操作就是假定一个数组已经有序了，然后拿一个新的数找到比它大的最小的那个，再把比它大的数依次向后移一个，再将新的数插入到空出来的那个位置。**

#include<stdio.h>
    
    void Insert(int* a)
    {
        
    	for (int i = 1; i < 10; i++)
    	{
        
    		int end = i - 1;
    		int tmp = a[i];
    		while (end >= 0)
    		{
        
    			if (a[end] > tmp)
    			{
        
    				a[end + 1] = a[end];
    				end--;
    			}
    			else
    			{
        
    				break;
    			}
    		}
    		a[end + 1] = tmp;
    	}
    	for (int i = 0; i < 10; i++) printf("%d ", a[i]);
    }
    int main()
    {
        
    	int a[10] = {
         2,5,1,7,3,96,5,4,0,4 };
    	Insert(a);
    	return 0;
    }

![在这里插入图片描述][c3a389268c5f402aaecd6277dc95042f.png]

![在这里插入图片描述][f8d38a8581f94ea9a4cf1b2a9baea4bf.png]

[ef9d7f79736d4941a7ff35f2da5ea1c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/10183baf16384a99bf99a03fa001bf97.png
[3ae93925154642e198c9caaaf25375ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4424c7c5b5ef4b9a858ec1b5cb2316f4.png
[c3a389268c5f402aaecd6277dc95042f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a6aba9bea4e84cd88596ca83b6b45ee5.png
[f8d38a8581f94ea9a4cf1b2a9baea4bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0cc78b5d104f416787f008fdf18f5944.png