【算法】冒泡排序(从小到大) 排序范围(0~n-1)n为数组元素个数

不念不忘少年蓝@ 2022-06-13 07:18 190阅读 0赞

今天要谈的是基本排序算法中的冒泡排序。除了冒泡排序，基本排序算法还包括：[选择排序][Link 1]、[插入排序][Link 2]。

插入排序算法的思想也是很简单的，它把排序过程模拟成了从水底冒气泡的过程。一趟排序过程结束后，最小(最轻)的元素就已经“浮”到水面上了。接下来就是不断缩小排序范围，把每个排序范围中最小的元素交换到数组头。

接下来就来分析算法，我们使用的数据是1 3 2 8 0 6 共6个元素

![20170630210542184][]

我们总的排序范围为0~5，即0~n-1，我们令一个指针j指向数组的最后一个元素，至于j有啥“特异功能”，慢慢往后看~

![20170630210735669][]

1、第一趟，排序范围(0,5)，目标是将其中的最小值0，交换至数组头。将a\[j\]与a\[j-1\]的值相比较，如果a\[j-1\] > a\[j\]则将a\[j\]的值与a\[j-1\]的值进行交换,**要把小的值往前推嘛~**

![20170630211839810][]

显然j指针就是为了在不断比较当中寻找待排序数组中的最小值，并把它存于数组头。

2、第二趟，排序范围(1,5)，目标是将其中的最小值1，交换至数组头。

![20170630212150442][]

3、第三趟，排序范围(2,5)，目标是将其中的最小值2，交换之数组头。

![20170630212250725][]

4、第四趟，排序范围(3,5)，目标是将其中的最小值3，交换至数组头

![20170630212351766][]

5、第五趟，排序范围(4,5)，目标是将其中的最小值6，交换至数组头

![20170630212447103][]

至此，排序结束，最终序列为

![20170630212529024][]

我们通过观察，发现我们总共6个元素，排序进行了5趟；每趟排序开始前，j指针总指向末尾；交换数据的条件为a\[j-1\] >a\[j\]；a\[j\]总指向当前**遍历过的最小的值**

不想太多，直接根据我们的结论写代码。我们可以分成两个部分实现：

void pop(Elemtype a[] , int begin , int end)
    {
    	int j;
    	for(j = end ; j > begin ; j--)
    	{
    		//将最小值往前推
    		if(a[j-1] > a[j])
    		{
    			swap(&a[j-1],&a[j]);
    		}
    	}
    }
    
    void sort(Elemtype a[] , int begin , int end)
    {
    	int i;
    	//执行n-1次
    	for(i = begin ; i < end ; i++)
    	{
    		pop(a,i,end);
    	}
    }
    
    void swap(Elemtype *a , Elemtype *b)
    {
    	Elemtype t = *a;
    	*a = *b;
    	*b = t;
    }

完整程序如下：

#include <stdio.h>
    #define Elemtype int
    void swap(Elemtype *a , Elemtype *b);
    
    void pop(Elemtype a[] , int begin , int end)
    {
    	int j;
    	for(j = end ; j > begin ; j--)
    	{
    		//将最小值往前推
    		if(a[j-1] > a[j])
    		{
    			swap(&a[j-1],&a[j]);
    		}
    	}
    }
    
    void sort(Elemtype a[] , int begin , int end)
    {
    	int i;
    	//执行n-1次
    	for(i = begin ; i < end ; i++)
    	{
    		pop(a,i,end);
    	}
    }
    
    void swap(Elemtype *a , Elemtype *b)
    {
    	Elemtype t = *a;
    	*a = *b;
    	*b = t;
    }
    
    void display(Elemtype a[] , int begin , int end)
    {
    	int i;
    	for(i = begin ; i <= end ; i++)
    	{
    		printf("%d ",a[i]);
    	}
    	printf("\n");
    }
    
    int main()
    {
    	Elemtype a[] = {1,3,2,8,0,6};
    	sort(a,0,5);
    	display(a,0,5);
    	return 0;
    }

程序运行效果如下：

![20170630215101781][]

冒泡排序的时间复杂度为O(*n^2*)

PS.不要胡思乱想不要胡思乱想，跟着分析走就好，不然会绕进死胡同。。。

[Link 1]: http://blog.csdn.net/mgsky1/article/details/73866163
[Link 2]: http://blog.csdn.net/mgsky1/article/details/73919745
[20170630210542184]: /images/20220613/3f4626efea3347c4ab210b1927cf7786.png
[20170630210735669]: /images/20220613/c0844b85bccf45b38ca27ca48ebbc0ef.png
[20170630211839810]: /images/20220613/5a41a78327c842b0922f3e47c4ce000d.png
[20170630212150442]: /images/20220613/d6484f9e34fb4cd099a18f5b16abd51a.png
[20170630212250725]: /images/20220613/7b7eb1900665452f94e51971c898ac23.png
[20170630212351766]: /images/20220613/0c6793ed4f26449b889a5810e7e0565f.png
[20170630212447103]: /images/20220613/6d2892e15e2b425d8f573599c521fb8f.png
[20170630212529024]: /images/20220613/a929a705243f43ea88833215e0a082d4.png
[20170630215101781]: /images/20220613/48f2c9405d714337a003c1362f0c01ff.png