三大基础排序算法——我欲修仙（功法篇）

刺骨的言语ヽ痛彻心扉 2024-04-14 06:03 57阅读 0赞

> 个人主页：[【?个人主页】][Link 1]  
> 系列专栏：[【❤️我欲修仙】][Link 2]  
> 学习名言：莫等闲、白了少年头，空悲切。——岳飞

--------------------

## 系列文章目录 ##

第一章 ❤️ [学习前的必知知识][Link 3]  
第二章 ❤️ [二分查找][Link 4]

--------------------

#### 文章目录 ####

*  系列文章目录
 *  前言???
 *  冒泡排序
 *   *  介绍
     *  运行原理
     *  基本概念
     *  代码实现
 *  插入排序
 *   *  介绍
     *  运行原理
     *  基本概念
     *  代码实现
 *  选择排序
 *   *  介绍
     *  运行原理
     *  基本概念
     *  代码实现

--------------------

## 前言??? ##

> 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。今天就让我们学习其中最基础的三种算法吧！

--------------------

## 冒泡排序 ##

### 介绍 ###

> 冒泡排序（Bubble Sort）是一种简单的排序算法。**它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成**。  
> *这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端*

### 运行原理 ###

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

![在这里插入图片描述][c2b13f9fcee2408a9292e023347d7957.gif_pic_center]

### 基本概念 ###

依次比较相邻的两个数，将小数放在前面，大数放在后面。

> 即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。  
> 至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。  
> 这里特别说明：冒泡排序是有改进算法的，感兴趣的道友可以自己感悟感悟

### 代码实现 ###

#include<stdio.h>
    typedef  int Elemtype;
    #define  MAX 10
    typedef struct
    {
        
    	int *arr;
    	int length;
    }num;
    num Sort_bobble(int *arr,int n){
        
    
    	int end = n;
    	int i = 0;
    	while (end)
    	{
        
    		int flag = 0;
    		for (i = 1;i < end;i++)
    		{
        
    
    			if (arr[i - 1] > arr[i])
    			{
        
    			/*	int tem = arr[i];
    				arr[i] = arr[i - 1];
    				arr[i - 1] = tem;*/
    				swap(&arr[i], &arr[i - 1]);
    				flag = 1;
    			}
    
    	    }
    		if (flag == 0)
    			break;
    		end--;
    	}
    	num retult = {
         arr,n };
    	return retult;
    }//冒泡排序
    int main()
    {
        
    	int arr[MAX] = {
         2,3,4,5,1,3 };
    	int n = 6;
    	int i = 0;
    	num retult = Sort_bobble(arr, n);  
    	for(i = 0;i < retult.length;i++)
    	{
        
    	    printf("%d",retult.arr[i]);
    	}
    	return 0;
    }

## 插入排序 ##

### 介绍 ###

> 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。**插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素，但将最后一个元素除外(让数组多一个空间才有插入的位置)，而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。**  
> *插入排序的基本思想是:每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。*

### 运行原理 ###

> 插入排序算法的运作如下：
> 
> 1.  从第一个元素开始，该元素可以认为已经被排序
> 2.  取出下一个元素，在已经排序的元素序列中从后向前扫描
> 3.  如果该元素（已排序）大于新元素，将该元素移到下一位置
> 4.  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
> 5.  将新元素插入到下一位置
> 6.  重复步骤2  
>     *如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。*

![在这里插入图片描述][b8775acf8463409b8ad7a4b81d983e27.gif_pic_center]

### 基本概念 ###

> 假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后，可以保证a\[1…k\]是局部有序的，保证了插入过程的正确性.  
> 插入算法还分为：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。

### 代码实现 ###

#include<stdio.h>
    typedef  int Elemtype;
    #define  MAX 10
    typedef struct
    {
        
    	int *arr;
    	int length;
    }num;
    void swap(int* a, int* b)
    {
        
    	int tem = *a;
    	*a = *b;
    	*b = tem;
    }//交换位置
    num Sort_insert(int * arr, int n) {
        
    	int i = 0;
    	for (i = 0;i < n - 1 ;++i)
    	{
        
    		int end = i;
    		int tem = arr[end + 1];
    		while (end >= 0)
    		{
        
    			if (tem < arr[end])
    			{
        
    				arr[end + 1] = arr[end];
    				end--;
    			}
    			else
    				break;
    
    		}
    
    		arr[end + 1] = tem;
    	}
    	num result = {
         arr,n };
    	return result;
    }//插入排序
    int main()
    {
        
    	int arr[MAX] = {
         2,3,4,5,1,3 };
    	int n = 6;
    	int i = 0;
    	num retult = Sort_insert(arr, n);  
    	for(i = 0;i < retult.length;i++)
    	{
        
    	    printf("%d",retult.arr[i]);
    	}
    	return 0;
    }

## 选择排序 ##

### 介绍 ###

> 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列\[5， 5， 3\]第一次就将第一个\[5\]与\[3\]交换，导致第一个5挪动到第二个5后面)。

### 运行原理 ###

> n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
> 
> 1.  初始状态:无序区为R\[1…n\]，有序区为空。
> 2.  第1趟排序
> 3.  在无序区R\[1…n\]中选出关键字最小的记录R\[k\]，将它与无序区的第1个记录R\[1\]交换，使R\[1…1\]和R\[2…n\]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
> 4.  第i趟排序第i趟排序开始时，当前有序区和无序区分别为R\[1…i-1\]和R(i…n)。该趟排序从当前无序区中选出关键字最小的记录 R\[k\]，将它与无序区的第1个记录R交换，使R\[1…i\]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

![在这里插入图片描述][9ade750ea4084539b6a8657d1514dfea.gif_pic_center]

### 基本概念 ###

> 对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面"后一个元素"现变成了"前一个元素"，继续跟他的"后一个元素"进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。

### 代码实现 ###

#include<stdio.h>
    typedef  int Elemtype;
    #define  MAX 10
    typedef struct
    {
        
    	int *arr;
    	int length;
    }num;
    num Sort_selection(int* arr, int n)
    {
        
    	int  i = 0;
    
    	int begin = 0, end = n - 1;
    	while (begin < end)
    	{
        
    		int max = begin;
    		int min = begin;
    		for (i = begin;i <= end;i++)
    		{
        
    			if (arr[i] < arr[min])
    				min = i;
    			if (arr[i] > arr[max])
    				max = i;
    		}
    
    		swap(&arr[min], &arr[begin]);
    		if (begin == max)
    			max = min;
    		swap(&arr[max], &arr[end]);
    		++begin;
    		--end;
    	}
    	num retult = {
         arr,n };
    	return retult;
    
    }//选择排序
    int main()
    {
        
    	int arr[MAX] = {
         2,3,4,5,1,3 };
    	int n = 6;
    	int i = 0;
    	num retult = Sort_selection(arr, n);  
    	for(i = 0;i < retult.length;i++)
    	{
        
    	    printf("%d",retult.arr[i]);
    	}
    	return 0;
    }

![在这里插入图片描述][840df9e8cf4f4540add70281a7f06557.gif_pic_center]

[Link 1]: https://blog.csdn.net/weixin_73602725?type=blog
[Link 2]: https://blog.csdn.net/weixin_73602725/category_12259807.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/weixin_73602725/article/details/129406349
[Link 4]: https://blog.csdn.net/weixin_73602725/article/details/129731407?spm=1001.2014.3001.5501
[c2b13f9fcee2408a9292e023347d7957.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/81950962aa134e96aba12f8afddce9e1.gif
[b8775acf8463409b8ad7a4b81d983e27.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/eb63b11a67044c75a392e64971ca648a.gif
[9ade750ea4084539b6a8657d1514dfea.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/186479c3bb9b43a5af0ce92360fc6b4e.gif
[840df9e8cf4f4540add70281a7f06557.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/11/3628db185bf84074bef4ef183f0d42b8.gif