冒泡排序（Bubble Sort）基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。直观表达，每一趟遍历，将一个最大的数移到序列末尾。也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，将他们之间小的，或者大的值交换过来。遍历数列的工作是重复地进行，直到没有再需要交换的，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

1.1 算法思想

比较相邻的元素，如果前一个比后一个大，交换之。
第一趟排序第i个和第i+1个比较与交换，随后第i+1个和第i+2个一对比较交换，这样直到倒数第n-1个和最后n个，将最大的数移动到最后一位。
第二趟将第二大的数移动至倒数第二位

……

1.2 动图演示

算法实现：


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 10
 
Swap(int *p1, int * p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void Print(int *a)
{
	for (int i=0;i<N;i++)
	{
		printf("%d ",a[i]);
	}
}
 
void BubbleSort(int* a, int n)
{
	
	for (int j=0;j<n;++j)
	{
		int size = 0;
		for (int i=1;i<N-j;++i)
		{
			if (a[i-1]>a[i])
			{
				Swap(&a[i-1],&a[i]);
				size =1;
			}
		}
		if (size==0)
		{
			break;
		}
	}
}
 
int main()
{
	int a[N] = {0};
	for (int i=0;i<N;++i)
	{
		a[i] = rand();
	}
	BubbleSort(a,N);
	Print(a);
	
	return 0;
}

其中有一段优化程序，是定义一个变量判断排序是否在做无效操作，当内循环处于交换状态时，则数据未排序完毕，否则视为，数据已有序，我们就可以break;中止掉程序，避免做无用遍历。

1.3 冒泡最好的情况

待排序数列有序时，时间复杂度是O(N)。外循环只执行一次，内循环N-1,N-2,N-3……

1.2 冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)

4. 稳定性：稳定

总结：

总的来说，冒泡排序是一种可以的排序，比直接选择排序要好，虽然有优化程序，但是，整体算法效率跟其他排序来比，还是差一些，比较适合新手学习。

2. 交换排序——快速排序

快速排序(Quicksort)是Hoare于1962年提出的一种二叉树结构的交换排序方法，有时候也叫做划分交换排序，是一个高效的算法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。这是一个分治算法，而且它就在原地交换数据排序。

是目前已知最快的排序算法，会比一般的排序更节省时间。

2.1 快速排序——挖坑法

算算法实现：


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//打印
void Print(int *a,int n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
}
 
//挖坑法
void QuickSort(int* a,int left,int right)//升序
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		int pivot = begin;//记录坑位的下标
		int key = a[begin];//坑值
 
		while (begin < end)
		{
			//右边找小，放到左边
			while (begin < end && a[end] >= key)//与坑值比较
			{
				--end;
			}
			//小的放在左边的坑里，自己形成了新的坑位
			a[pivot] = a[end];
			pivot = end;
 
			//左边找大，放在右边
			while (begin < end && a[begin] <= key)//与坑值比较
			{
				++begin;
			}
			//大的放在右边的坑里，自己形成了新的坑位
			a[pivot] = a[begin];
			pivot = begin;
		}
		//最后将坑值给到坑位
		a[pivot] = key;
		//[left,right]
		//[left,pivot-1]  [pivot+1,right]
		//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
		QuickSort(a, left, pivot - 1);
		QuickSort(a, pivot + 1, right);
	}
	else
	{
		return;
	}
}
 
int main()
{
	int a[10] = {0,9,5,6,3,2,1,7,8,4};
	//挖坑法
	QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);
    //打印
	Print(a,sizeof(a) / sizeof(a[0]));
	return 0;
}

快排的缺点

根据上面的代码，我们来分析一下快排的缺点：

如何解决快排对有序数据排序效率很差的方法？

三数取中法

所谓三数取中，不是取最大值，最小值，以及他们的中间值，而是取左边（begin）、右边（end）和中间（begin+end）/2;

在有序的情况下中间的值刚好就是二分，将取出的值作为坑位，就不会出现最差的这种情况。我们依旧使用区间的开头作为“坑值”，但是要使用三数取中的逻辑。

选坑位：


int begin = left;
int end = right;
//使用三数取中选“坑值”，用mid存储其下标
int mid = GetMidIndex(a, begin, end);
//将区间首值当作坑位
//坑值与首值交换，避免算法混乱
//一般我们会将区间首值作为坑值
Swap(&a[begin], &a[mid]);//传地址调用
//存储坑值
int key = a[begin];

三数取中 GetMidIndex();


int GetMidIndex(int *a,int left,int right)
{
    //二分
	int mid = (right - left) / 2;
	if (a[left]<a[mid])
	{
		if (a[left]<a[right])
		{
			if (a[mid]<a[right])
			{
				return mid;
			}
			else  //a[mid]>=a[right]
			{
				return right;
			}
		}
		else   //a[left]>=a[right]
		{
			return left;
		}
	}
	else  //a[left]>=a[mid]
	{
		if (a[mid]<a[right])
		{
			if (a[left]<a[right])
			{
				return left;
			}
			else  //a[left]>=a[right]
			{
				return right;
			}
		}
		else  //a[mid]>=a[right]
		{
			return mid;
		}
	}
}

交换Swap()；


//交换
void Swap(int* p1, int*p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

经过三数取中的处理，就不会出现快排的最坏情况，但也几乎不会成为最好的情况，有利有弊，我们在面试的过程中只需要写基础版的快排即可，以防时间不够。

小区间优化：

关于如果处理数据多，相应的递归次数多，会不会影响操作快排的性能？

当我们在使用快排对大量数据进行排序时，我们可以采用小区间优化，减少递归次数，达到优化程序得到目的。

对当待处理数据大于10的子序列进行快排递归。

对当待处理数据低于10的子序列进行直接插入排序进行排序，避免递归次数过多。

这个10不是固定的，可以根据处理的数据量调整。


//区间[left,right]
//左区间[left,pivot-1]  右区间[pivot+1,right]
//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
// 小区间优化
if (pivot - 1 - left > 10)//对当待处理数据大于于10的子序列进行快排递归排序
{
	//快排
	QuickSort(a,left,pivot-1);
}
else
{
	//采用直接插入排序，对当待处理数据低于10的子序列进行排序，避免递归
	InsertSort(a+left,pivot-1-left+1);//为什么最后要加1,例如：区间[0,9]实际上有10个数
}
 
if (right - (pivot + 1) > 10)
{
	QuickSort(a,pivot+1,right);
}
else
{
	InsertSort(a + pivot+1, right-(pivot+1)+1);
 
}

如果大家有想了解直接插入排序可以查看博主的另一篇：

常见排序算法之插入排序——直接插入排序、希尔排序：http://t.csdn.cn/X2mlq

2.3 快速排序——左右指针法

根据上图的示例我们应该能够理解左右指针法是什么样的逻辑，跟挖坑法是一样的思想，单趟排序完毕实现左边比坑位小，右边比坑位大。但是即使左右指针法跟挖坑法的思想是一样的，但是他们单趟的运算结果是不一样的。

算法实现：


void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		//选坑位
		int mid = GetMidIndex(a, begin, end);//三数取中
		Swap(&a[begin], &a[mid]);
		int key = begin;
		while (begin < end)
		{
			while (begin < end && a[end] <= a[key])
				--end;
			while (begin < end && a[begin] >= a[key])
				++begin;
			Swap(&a[begin], &a[end]);
		}
		Swap(&a[begin], &a[key]);
		//分治递归
		QuickSort(a, left, begin - 1);
		QuickSort(a, begin + 1, right);
	}
}

2.4 前后指针法

采用perv记录区间第一个元素的下标，采用cur记录区间第二个元素的下标。
cur找小，每次遇到比key(坑值)小的值就停下来，++prev。
交换prev和cur位置的值

算法实现：


//左右指针法
void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		//选坑位
		int mid = GetMidIndex(a, left,right);//三数取中
		Swap(&a[left], &a[mid]);
		int key = left;
		//初始化指向
		int prev = left, cur = left + 1;
		while (cur<=right)
		{
			if (a[cur] <= a[key])//&&++prev!=cur
			{
				++prev;
				//避免无效操作
				if(cur!=prev)
				Swap(&a[prev],&a[cur]);
			}
			++cur;
		}
		Swap(&a[key], &a[prev]);
		//分治递归
		QuickSort(a, left, prev - 1);
		QuickSort(a, prev + 1, right);
	}
}

快速排序的特性总结：

1.快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2.时间复杂度：O(N*logN)

3.空间复杂度：O(logN)

4.稳定性：不稳定

总结：

快排是我们一定要掌握的一种排序算法，在面试、笔试中也是很常见的，博主分享的三种方法：挖坑法，左右指针法，前后指针法，只少要掌握一种，但是要其他的方法也要知道算法思想。还有两种优化方式，小区间优化和三数取中，也要知道是什么逻辑，解决什么问题。

感谢每一个观看本篇文章的朋友，更多精彩敬请期待：保护小周ღ *★,°*:.☆(￣▽￣)/$:*.°★*

文章存在借鉴，如有侵权请联系修改删除！

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】