冒泡排序的改进算法和快速排序

朴灿烈づ我的快乐病毒、 2022-08-21 06:36 155阅读 0赞

## 冒泡排序的基本思想 ##

冒泡排序和快速排序的性能分析：

平均情况    最好情况   最坏情况        稳定性
    冒泡排序  o(n^2)        o(n)         o(n^2)       稳定
    快速排序  o(n*logn)   o(n*logn)      o(n^2)       不稳定

.从最好情况来看冒泡排序比快速排序性能更好，也就是说如果你的排序元素基本有序，你应该考虑的就是冒泡排序

.从平均情况来看，快速排序反而优于冒泡排序.

.从根本上来说快速排序就是冒泡排序的一种优化.

首先先给出程序的测试代码：

int main()
    {
    	printf("请输入5个你要比较的数据:");
    	for(i=0;i<sz;i++)
    	{
    		scanf("%d",&arr[i]);
    	}
    	quick_sort(arr,0,sz-1);
    	for(i=0;i<sz;i++)
    	{
    		printf("%d ",arr[i]);
    	}
    	system("pause");
    	return 0;
    }

.冒泡排序的基本思想是：两两比较相邻记录的关键字，如果反序就交换，如果没有则继续比较直到比较完成

.在程序中我们用双重的for循环来控制实现，一个变量i控制比较的趟数,一个变量j控制每趟比较的次数

.如果有n个数字需要比较，那仫我们就需要比较(n-1)趟，每一趟我们需要比较(n-1-i)次

.但是如果排序是降序排列，而给出的待排序的元素为 0，9,8,7,6,5,4,3,2,1，我们发现只要将第一个数字交换到数组末位置就可以了，那仫冒泡排序的每次比较就成为多余的了，虽然它的比较成立的次数很少，如果我们添加一个标志位，用来判断条件是否成立，如果元素本身就是有序的就直接跳出

下面我们就来实现优化之后的冒泡排序

void bubble_sort(int arr[],int sz)
    {
    	int flag=1;  //添加标志位
    	for(i=0;i<sz-1;i++)  //控制比较的趟数
    	{
    		flag=1;
    		for(j=0;j<sz-1-i;j++)  //控制每趟比较的次数
    		{
    			if(arr[j] < arr[j+1])  //降序排列
    			{
    				int tmp=arr[j];
    				arr[j]=arr[j+1];
    				arr[j+1]=tmp;
    				flag=0;
    			}
    		}
    		if(flag == 1) break;
    	}
    }

## 快速排序的基本思想 ##

先选择一个待排序的元素中的一个做为轴枢（一般选择第一个元素），通过一趟快速排序将元素分成两个独立的部分，一部分均比轴枢小，一部分均比轴枢大，然后分别再对这两部分进行快速排序，以达到整个有序的目的.

下面我们来看一组元素的快速排序过程.

![Center][]

快速排序的实现:

int Partition(int *arr,int left,int right)   //快速排序实现升序排序数据
    {
    	int key=arr[left];  
    	while(left < right)
    	{
    		while(left < right && arr[right] >= key)  //从元素右面查找第一个比轴枢小的元素
    		{
    			--right;
    		}
    		arr[left]=arr[right];
    		while(left < right && arr[left] <= key) //从元素左面查找第一个比轴枢大的元素
    		{
    			++left;
    		}
    		arr[right]=arr[left];
    	}
    	return left;
    }
    
    void quick_sort(int arr[],int left,int right)  
    {
    	int key=0;  
    	if(left < right)
    	{
    		key=Partition(arr,left,right);  //轴枢key
    		quick_sort(arr,left,key-1);  //位于轴枢左面的数字进行排序
    		quick_sort(arr,key+1,right);  //位于轴枢右面的数字进行排序
    
    	}
    }

以上就是我个人对冒泡排序和快速排序的理解，如果有不对和需要优化的地方希望大家指出。

看完了记得点评奥![吐舌头][tongue.gif]

[Center]: /images/20220724/0271fb22af734c809faf7a232a8dbbf8.png
[tongue.gif]: /images/20220724/7eb6c94cd026463abcda4d43289dc77d.png