frendguo's blog

常见算法之排序算法(一)---冒泡排序

排序看起来是个很简单的问题,其实[并不简单]。。。

以下便来聊聊常见的排序算法:

1.冒泡排序(Bubble sort)

冒泡排序是个非常简单的算法,简单的来说,就是依次比较,找出最大值(最小值),然后移动最右端(左端),再用相同的道理找出第二大的,第三大的...依次放到第二、第三个位置(从右往左数)。详细的描述参看维基百科(英文版,中文需 FQ ) 》》》

参考代码:

void bubble_sort(int* arr, int size)
{
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size - 1 - i; ++j)
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = arr[j];
			}
}

也可以使用以下助记码来帮助记忆:

i∈[0,N-1)               //循环N-1遍
   j∈[0,N-1-i)           //每遍循环要处理的无序部分
     swap(j,j+1)          //两两排序(升序/降序)

最后再来分析下冒泡排序的复杂度:

  • 最优时间复杂度:当序列已经处于排序状态时,时间复杂度最优。此时,时间复杂度时O(n^2). 但这里维基百科上写的时O(n) 啊,为什么呢?实质上,要想实现最优O(n)的冒泡排序啊,必须得对上面的代码做点小的优化,比如加个标志位啊!于是就有下面的代码:
  • void bubble_sort(int* arr, int size)
    {
    	bool isComplate = true;
    	for (int i = 0; i < size; ++i, isComplate = true)
    		for (int j = 0; j < size - 1 - i; ++j)
    			if (arr[j] > arr[j + 1])
    			{
    				isComplate = false;
    				int tmp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = arr[j];
    			}
    }
  • 最坏时间复杂度:很显然,最坏的情况也只能是O(n^2)。
  • 平均时间复杂度:O(n^2)
  • 空间复杂度:指的额外耗费的空间,这里也很明显耗费的空间只是一个常量值(在这里,也就是不随 size 的大小而改变),也就是O(1)

优化:

 这里介绍下冒泡的简单变形:鸡尾酒排序(cocktail_sort),根据上面的冒泡排序,我们每次循环都是一个方向的,那么很自然的想到,我们每次可不可两个方向来比较呢?于是就有了鸡尾酒排序。排序过程如下:

写出代码如下:

template<typename T>
void cocktail_sort(T* arr, int n)
{
	int start = 0;
	int end = n - 1;

	while (start < end)
	{
		for (long i = start; i < end; ++i)
		{
			if (arr[i] > arr[i + 1])
			{
				T t = arr[i];
				arr[i] = arr[i + 1];
				arr[i + 1] = t;
			}
		}
		--end;

		for (long i = end; i > start; --i)
		{
			if (arr[i] < arr[i - 1])
			{
				int t = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = t;
			}
		}
		++start;
	}
}

算法复杂度跟冒泡排序也是一样一样的。总的来说性能还是有些许提升的。下面是我用冒泡和鸡尾酒排序来排序100,000个随机数的结果(VS2017):

可以看出效果也的确不是很显著。

Happy Coding!o(* ̄▽ ̄*)o

Add comment

Loading