排序1: 冒泡排序及其优化

一. 概述

（1）冒泡排序是一种排序是一种排序是一种交换排序。

交换排序：数据两两比较，交换不满足次序要求的数据，直到整组数据都满足排序要求。

二．算法思想

假设有一个大小为 N 的无序序列。以升序冒泡排序为例，冒泡排序就是要每趟排序过程中通过两两比较相邻元素，将小的数字放到前面，大的数字放在后面。

假设有一个无序序列： 4，3，1，2，5

排序1: 冒泡排序及其优化

三．时间复杂度和空间复杂度

排序1: 冒泡排序及其优化

冒泡排序就是把小的元素往前调或者把大的元素往后调。当数据越接近正序，冒泡排序性能越好。

比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，

所以冒泡排序是一种稳定排序算法。

/*
Data:2018/12/26
code: bubble sort
From:mohican
*/

#include<stdio.h>

//普通冒泡排序 两两交换 
//降序排列
void Bubble(int *arr,int len)
{
	int temp = 0;
	int num =0;
	for(int i = 0 ;i<len-1;++i)  //最后一个元素  位置 i  i+1越界
	{
		for(int j =0 ;j<len-1;++j)
		{
			if(arr[j]>arr[j+1])
			{
			    temp = arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
			}
		}
	}
}


//冒泡排序优化
//设置一个flag 如果不再发生交换，说明已经有序，不再需要排序，直接退出

void BubbleBetter(int *arr,int len)
{
	int temp = 0;
	int num =0;
	bool flag = false;
	for(int i = 0 ;i<len-1;++i)  //最后一个元素  位置 i  i+1越界
	{
		flag =false;
		for(int j =0 ;j<len-1;++j)
		{
			if(arr[j]>arr[j+1])
			{
			    temp = arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=temp;
			}
			flag = true;
		}
		if(!flag)
		{
			return ;
		}
	}
	

}
void show(int *arr,int len)
{
	for(int i =0;i<len;++i)
	{
		printf("%d\t",arr[i]);
	}
}

int main()
{
	int arr[]={7,3,4,6,4,2.876,3,5346,345};
	int len = sizeof(arr)/sizeof(arr[0]);
	Bubble(arr,len);
	BubbleBetter(arr,len);
	show(arr,len);
	getchar();
	return 0;
}

排序1: 冒泡排序及其优化

相关推荐