C语言---冒泡排序和快速排序

雨点打透心脏的1/2处 2023-09-23 23:58 138阅读 0赞

### 文章目录 ###

*  前言
 *  一、冒泡排序
 *   *  1.简介
     *  2.算法思路
     *  3.代码实现
 *  二、快速排序
 *   *  1.简介
     *  2.算法思路
     *   *  2.1左右指针法
         *  2.2挖坑法
         *  2.3前后指针法
 *  总结

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

# 前言 #

交换排序有冒泡排序和快速排序这两种，  
**基本思想**：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列前部移动。

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

# 一、冒泡排序 #

## 1.简介 ##

> 冒泡排序是一种计算机科学领域的较简单的排序算法。  
> **基本原理**：对元素个数为 N 的待排序序列进行排序时，共进行N-1次循环。在第 k 次循环中，对从第1到第N-k个元素从前往后进行比较，每次比较相邻的两个元素，若前一个元素大于后一个元素，则两者互换位置，否则保持位置不变。  
> *时间复杂度：O(n²） 空间复杂度：O(1) 稳定性：稳定*

## 2.算法思路 ##

动态显示图，充分理解冒泡排序  
![在这里插入图片描述][fee9c7f21d19497dbc4324328406593b.gif_pic_center]  
从图中我们可以看见

1.每一次比较都是相邻的两个数，例如图中有15个元素，则比较的下标值是\[0,1\],\[1,2\],\[2,3\],\[3,4\],\[4,5\],\[5,6\],\[6,7\],\[7,8\],\[8,9\],…,\[13,14\]。共14趟。  
2. \*\*第一趟：\*\*先从下标值0开始，每一次比较都是和后一个元素，如果后一个元素大于前一个元素，则进行交换，然后再进行后一个元素的比较，直到与末尾元素比较。此时末尾元素是最大值。  
3. **第二趟**开始，**不需要比较末尾元素了**，因为第一趟就是将最大值放在末尾。也就是说需要比较剩余的14个元素，重复步骤二，找到第二大的元素。  
4. 依次下去，将大的元素排在后面，就形成了从小到大的有序序列

## 3.代码实现 ##

#include <stdio.h>
    void Swap(int* px, int* py)
    {
        
    	int tmp = *px;
    	*px = *py;
    	*py = tmp;
    }
    void BubbleSort(int* a, int n)
    {
        
    	int end = n;
    	while (end > 0)
    	{
        
    		int exchange = 0;
    		for (int i = 1; i < end; ++i)
    		{
        
    			//当下一个元素大于当前元素时，进行交换
    			if (a[i - 1] > a[i])
    			{
        
    				exchange = 1;
    				Swap(&a[i - 1], &a[i]);
    			}
    		}
    		--end;
    		//当元素未进行交换，则本就是有序，直接结束循环
    		if (exchange == 0)
    		{
        
    			break;
    		}
    	}
    }
    int main()
    {
        
    		int a[] = {
         26, 2, 5, 3, 9, 4, 8, 5, 1, 7 };
    		BubbleSort(a, 10);
    		for (int i = 0; i < 10; i++)
    		{
        
    			printf("%d ", a[i]);
    		}
    }

注：如果序列是有序的，可以局部变量来判断，可以减少运行时间，提高效率。  
**运行结果：**  
![在这里插入图片描述][56e07d5cb6ae4bb6a2234d313816117a.png]

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

# 二、快速排序 #

## 1.简介 ##

> **快速排序**是Hoare于1962年提出的一种二又树结构的交换排序方法。  
> **基本思想**: 任取待排序元素序列中为某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。  
> 时间复杂度：O(N\*logN) 空间复杂度：O(logN) 稳定性：不稳定

## 2.算法思路 ##

快速排序一般有三种方法：**左右指针法、挖坑法、前后指针法**。而这三种都需要利用到递归方法。

### 2.1左右指针法 ###

思路：

1.  在待排序序列中，取一个元素为key，key为初始元素或者末尾元素。
2.  此时取初始元素为key，右边开始遍历，当遍历到比key值小的元素时，停止；开始左边遍历，当左边遍历到比key元素小的时候，进行左右交换。
3.  然后重复操作，直到两边指针相遇。此时左指针的值和key进行交换。然后再按照以上方法进行递归实现【left,keyi】和【keyi+1,right】,keyi是key的下标值

注：key选初始元素，右边先开始遍历；选末尾元素，则左边先开始遍历  
**动态展示图**：  
![在这里插入图片描述][1161ed3c16864241b70cb81343e6bbb2.gif_pic_center]  
图片详解图：  
![在这里插入图片描述][cd94b9bb1465492695b7e698626c47a7.png]  
绿色交换，是指左指针和右指针相遇之后和key交换；  
红色（黄色）交换，是指左右指针的值交换。  
从图我们可以看出来，每一次排序，都是将待排序分成2部分，一部分是比key小的，一部分是比key大的，再通过递归的方法，逐次排序。  
**代码实现**：

void swap(int* w, int* t)
    {
        
    	int tem = *w;
    	*w = *t;
    	*t = tem;
    }
    int Partion1(int* p, int left, int right)
    {
        
    	//keyi值可进行改进，在文章结尾
    	int keyi = left;
    	while (left < right)
    	{
        
    		while (left < right && p[right] >= p[keyi])
    		{
        
    			right--;
    		}
    		while (left < right && p[left] <= p[keyi])
    		{
        
    			left++;
    		}
    
    		swap(&p[left], &p[right]);
    	}
    	swap(&p[left], &p[keyi]);
    	return left;
    }
    void Text1(int *p,int left,int right)
    {
        
    	if (left >= right)
    		return;
    	int key=Partion1(p, left, right);
    	//递归方法
    	Text1(p, left, key - 1);
    	Text1(p, key + 1,right);
    
    }
    int main()
    {
        
    	int arr[10]={
        6,1,2,7,9,3,5,10,8};
    	Text1(arr,0,9);	
    	for(int i=0;i<10;i++)
    	{
        
    	printf("%d ",arr[i]);
    	}
    }

### 2.2挖坑法 ###

思路:

1.  先将最左边的值保存下来，作为key值。
2.  将最左边的值抽出来了，然后右边遍历，遍历到比key小的值，填入坑中。相当于把数移到了坑里，而自身留下了坑位，然后左遍历，遍历到比key大的值，再移到右边的坑里。
3.  重复上述操作，直到左右指针相遇，再把key的值填入相遇的位置。

注：思路和左右指针法是相似的。key选初始元素，右边先开始遍历；选末尾元素，则左边先开始遍历  
![在这里插入图片描述][2922a6a451dd47a0bf609fb021156f1a.gif_pic_center]  
**代码实现**：

void swap(int* w, int* t)
    {
        
    	int tem = *w;
    	*w = *t;
    	*t = tem;
    }
    int Partion2(int* p, int left, int right)
    {
        
    	//记录keyi的值。keyi值可进行改进，在文章结尾
    	int keyi = p[left];
    	int priot = left;
    	while (left < right)
    	{
        
    		while (left < right && p[right] >= keyi)
    		{
        
    			right--;
    		}
    		p[priot] = p[right];
    		priot = right;
    		while (left < right && p[left] <= keyi)
    		{
        
    			left++;
    		}
    		p[priot] = p[left];
    		priot = left;
    	}
    	swap(&p[left], &keyi);
    	return left;
    }
    void Text1(int *p,int left,int right)
    {
        
    	if (left >= right)
    		return;
    	int key=Partion2(p, left, right);
    	//递归方法
    	Text1(p, left, key - 1);
    	Text1(p, key + 1,right);
    
    }
    int main()
    {
        
    	int arr[10]={
        6,1,2,7,9,3,5,10,8};
    	Text1(arr,0,9);	
    	for(int i=0;i<10;i++)
    	{
        
    	printf("%d ",arr[i]);
    	}
    }

### 2.3前后指针法 ###

思路：

1、选出一个key，一般是最左边或是最右边的。

2、起始时，prev指针指向序列开头，cur指针指向prev+1。

3、若cur指向的内容小于key，则prev先向后移动一位，然后交换prev和cur指针指向的内容，然后cur指针++；若cur指向的内容大于key，则cur指针直接++。如此进行下去，直到cur到达end位置，此时将key和++prev指针指向的内容交换即可。

经过一次单趟排序，最终也能使得key左边的数据全部都小于key，key右边的数据全部都大于key。

然后也还是将key的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时，便停止操作

**简单而言就是：cur找到比key小的就停下来，然后++prev，然后cur的值和prev的值交换，cur就再次继续向前移动，直到cur到最右边。**  
**图片展示：**  
![在这里插入图片描述][5b3c14a4d72c4e3f80fed7731620f770.png]  
注：图中是两种前后指针的示意图，如果右边做key，cur指向下标为1，prev则是在后面；如果左边做key，cur则指向下标为2的值，prev也是在后面。

**代码展示**

void swap(int* w, int* t)
    {
        
    	int tem = *w;
    	*w = *t;
    	*t = tem;
    }
    int Partion3(int* p, int left, int right)
    {
        
    	int prev = left;
    	int cur = left + 1;
    	int keyi = left;
    	while (cur <= right)
    	{
        
    		while (cur<=right&&a[cur] >= a[keyi])
    		{
        
    			cur++;
    		}
    		if (cur <= right)
    		{
        
    			swap(&a[cur], &a[++prev]);
    			cur++;
    		}
    	}
    	swap(&a[prev], &a[keyi]);
    	return prev;
    }
    void Text1(int *p,int left,int right)
    {
        
    	if (left >= right)
    		return;
    	int key=Partion3(p, left, right);
    	//递归方法
    	Text1(p, left, key - 1);
    	Text1(p, key + 1,right);
    
    }
    int main()
    {
        
    	int arr[10]={
        6,1,2,7,9,3,5,10,8};
    	Text1(arr,0,9);	
    	for(int i=0;i<10;i++)
    	{
        
    	printf("%d ",arr[i]);
    	}
    }

改进：在左右指针和挖坑法里，有时候数组的第一个元素或者最后一个元素是序列里最小的，就面对了最坏的情况，如此效率就会下降，为了提高效率，我们将key为三数取中，即第一个元素，中间元素和最后一个元素里取值中的元素。先找到中间元素，然后与key进行互换。  
方法如下：

int midnum(int* a, int left, int right)
    {
        
    	int mid = left + ((right - left) >> 1);
    	if (a[left] < a[mid])
    	{
        
    		if (a[mid] < a[right])
    		{
        
    			return mid;
    		}
    		else if (a[left] > a[right])
    		{
        
    			return left;
    		}
    		else
    		{
        
    			return right;
    		}
    	}
    	else
    	{
        
    		if (a[mid] > a[right])
    		{
        
    			return mid;
    		}
    		else if (a[left] < a[right])
    		{
        
    			return left;
    		}
    		else
    		{
        
    			return right;
    		}
    	}
    }
    //找到中间值的下标，赋值给min，然后与left的值进行交换
    int min = midnum(a, left, right);
    	swap(&a[min], &a[left]);

# 总结 #

插入排序虽然有三种方式，但都是大同小异，可以通过画图来消化。  
文章的动态图全是小小作者我在网上寻找到的，认为最为合适并且容易理解的图。  
而静态图则是小小作者我自己画的，可能并不完美，但是认真看，自己画一下，我相信你们一定可以明白的。

> 排序难以理解，千位要画图理解，要动手处理，不能只看，只敲代码，一定要要画图

---------来自菜鸟TQ02的提示

[fee9c7f21d19497dbc4324328406593b.gif_pic_center]: https://img-blog.csdnimg.cn/fee9c7f21d19497dbc4324328406593b.gif#pic_center
[56e07d5cb6ae4bb6a2234d313816117a.png]: https://img-blog.csdnimg.cn/56e07d5cb6ae4bb6a2234d313816117a.png
[1161ed3c16864241b70cb81343e6bbb2.gif_pic_center]: https://img-blog.csdnimg.cn/1161ed3c16864241b70cb81343e6bbb2.gif#pic_center
[cd94b9bb1465492695b7e698626c47a7.png]: https://img-blog.csdnimg.cn/cd94b9bb1465492695b7e698626c47a7.png
[2922a6a451dd47a0bf609fb021156f1a.gif_pic_center]: https://img-blog.csdnimg.cn/2922a6a451dd47a0bf609fb021156f1a.gif#pic_center
[5b3c14a4d72c4e3f80fed7731620f770.png]: https://img-blog.csdnimg.cn/5b3c14a4d72c4e3f80fed7731620f770.png