现在的位置: 首页 > 综合 > 正文

【数据结构与算法】——排序算法篇

2013年12月10日 ⁄ 综合 ⁄ 共 6105字 ⁄ 字号 小 中 大 ⁄ 评论关闭

 由于研究生考试的需要，加上我对算法的情有独钟，这段时间一直在研究算法。跟大家分享一些我的经验和想法：一、欢迎大家批评指正我错误的地方；二、欢迎大家补偿自己的见解进来，我如果发现有独到见解的评论，我会编辑添加到文章中来，并注明。希望给大家带来好的知识分享！

    为什么我们需要排序?存放数据就像我们在日常生活中存放东西一样，时不时需要整理一下，你下次拿东西的时候才方便。如果你的东西是一堆乱麻，你自己找个东西估计是很费时间的。

    我什么情况下需要排序？其实很多的情况下，是否使用排序是一个重要的策略问题。很早以前人们使用排序，多数情况下是希望能够使用二分查找在logn的时间内取得想要的数据。乱序的情况下，只能使用顺序查找，需要n的时间才能够完成，平均情况下也是n/2，与logn差距太大。于是 排序+二分查找 成为了早期程序员的数据管理标准配置。但是随着算法理论的推进。现在的情况发生了相当巨大的变化。正如《孙子兵法》中阐述的那样，战争的最高境界是【不战而屈人之兵】，那么排序的最高境界就是【不排】：

    1.【如果仅仅是为了取得数据方便】，那么Hash才是最佳的选择，因为如果使用好的解决Hash冲突方法，能够做到1+a/2 时间内取得数据，其中a为Hash表的填装因子。这远远好于二分查找带给你的logn时间复杂度。当然，你别想在Hash表找最大值，最小值，或者最大的10个数之类的问题，如果你需要这些操作，Hash不应该是你的选择。但通常情况下，人们存放用户数据的时候，往往关心的是如何取出而已。这种单纯的存取关系下，Hash绝对是最好的选择！

    2.【非重复关键字数据】，其实现实生活中这种情况是非常多见的，例如电话号码、身份证数据，他们往往可以成为关键字，而且排序往往是有意义的。如电话号码中0826可能是某个特定的地区，身份证511可能有特定的含义，对这些数据的如果是有序的，往往可以从中取得有用的信息。但是，这些数据真的需要排序吗？在《编程珠玑》中记载了这样一个案例，Boss需要程序员在一台老机子上对1,000,000条电话号码进行排序，要求不超过0.5秒就要完成，可用的内存为1M。问题来了？一来是，那个年代的老机子，1百万条数据，0.5秒排完，即使是快速排序都不可能。二者是，1M内存，就算电话号码是integer都存不下1百万条。面对这样的一个难题，作者是如何解决的呢？答案是根本不排序！首先，使用bit表示电话号码，比如有个电话是
000 000 03 那么就是第3个bit为1，相应的没有电话号码时为0，后面类推。其次，在读取数据放到内存的过程中，电话号码，就能够做到已经有序了，因为 100 100 10 一定是存放在 100 100 11前面的，这样就是天然有序的，所以完全不需要排序了！而我们的程序中，其时有非常多的情况下是非重复关键字的，这种情况下，是可以有更好的解决方案的，不是吗？

    3.【大规模频繁变更数据排序】，有时候我们存了相当大规模的数据， 而且随时可能有新的数据插入进来，或者旧的数据需要更新值，而我们又需要这个数据集是有序的，于是我们会经常调用排序算法来排序。这个大规模数据的情况下，性能往往是关键而敏感的，于是我们开始疯狂的优化排序算法。我们开始尝试各种混合优化排序方法，以期能够提升整个程序的性能。但是这样的工作真的是可取的吗？这样的大规模数据情况下，使用 树 这样的结构其实往往是更加科学的选择。因为诸如 红黑树 一类的高级树形结构往往能够在插入的过程中保持树本身的性质，而不需要调用排序算法。这种自动排序结构比优化排序算法更能从本质上改成程序的效率。

    说了这么多，但很多时候我们还是需要一个高效的排序算法的，至少在我们不明确需求情况下，我们有可用的解决方案，也许以后可用找到更加特定的方案，但我们需要先将一个程序跑起来不是？那么先来看看我们有些什么排序算法：

    上图传说是来自《大话数据结构》一书，但我没看过，这里借来引用特此说明。总体说来，我们有四大类排序算法：插入、选择、交换、合并。这是根据这些算法的基本操作来分类的。其实这上述的算法都是基于“比较” 的算法，还有一类特殊的算法是 基数排序。基于“比较”的算法，算法理论证明至少需要“log(n!) 上取整”次比较，而基数排序可以做到线性时间排序。但是基数排序在实践中并没有很好的表现，而且实现起来比较复杂，所以一直很少应用于实际编程。而我们这里讨论的也主要是“比较”排序。下面先来初看下这些“比较”排序的特征：

    上表同样据说来自《大话数据结构》，特此说明。我们可以看出，最主要的平均时间复杂度上，n²  和 nlogn 是两个重要的分水岭。通常n²  复杂度得排序算法被称为简单排序算法，因为通常能够比较简单地编写出来。而nlogn级的排序算法，被称为高级排序算法，因为通常需要一定算法基础的程序员才能够编写。下面我们来一一分析：

    前奏：引入一个简单的操作函数，交换swap，功能是交换传入的两个值，这个简单的操作可以方便后面的程序编码：

[cpp] view
plaincopy

  1. inline void swap(int &a,int &b)  
  2. {  
  3.     a = a^b;  
  4.     b = a^b;  
  5.     a = a^b;      
  6. };  


    上面的 ^ 是 异或 操作，这个交换实现是一种不使用中间变量进行交换的hack code，娱乐性质和实用性质都有一点儿。

  

1.冒泡排序

   

[cpp] view
plaincopy

  1. void bubblesort(int *arr,int n)  
  2. {  
  3.     for( int i=0; i<n; ++i)  
  4.     {  
  5.         for(int j=0; j<n-1-i; ++j)  
  6.         {  
  7.             if( arr[j] > arr[j+1] )  
  8.                 swap(arr[j],arr[j+1]);  
  9.         }     
  10.     }  
  11. }  


 这个版本的冒泡排序是正统的实现方式，其实可以实现地更加简洁好看一点儿：

[cpp] view
plaincopy

  1. void bubblesort(int *arr,int n)  
  2. {  
  3.     for( int i=0; i<n; ++i)  
  4.         for(int j=0; j<n-1-i; ++j)  
  5.             if( arr[j] > arr[j+1] )  
  6.                 swap(arr[j],arr[j+1]);  
  7. }  


     是不是很有层次感，是我最喜欢的风格，也许是受python的影响吧，我觉得短代码时，不要括号更加具有可读性。所以在C语言编程时，在短代码情况下，我也会偶尔这样去掉括号来增强可读性和层次感。冒泡排序应该是大家比较熟悉的，其特点如下：

   （1）稳定的，即如果有 [...,5,5...] 这样的序列，排完序后，这两个5的顺序一定不会改变，这在一般情况下是没有意义的，但当 5 这个节点不仅仅是一个数值，是一个结构体或者类实例，而结构体有附带数据的时候，这两个节点的顺序往往是有意义的，如果能够稳定有时候是关键的。因为如果不稳定则可能破坏附带数据的顺序结构。

    （2）比较次数恒定，总是比较 n²/2 次，哪怕数据已经完全有序了

    （3）最好的情况下，一个数据也不用移动，冒泡排序的最好情况是： 【数据已经有序】

    （4）最坏的情况下，移动 n²/2 次数据，冒泡排序的最坏情况是：【数据是逆序的】。

      需要说明的是的 n²/2  这个结果是：1+2+3+...+n-1 = n(n-1)/2，等差数列求和得到。

 

2.简单选择排序

   不准备分析，因为我比较懒，但有可能后续会补上。

 

3.直接插入排序

[cpp] view
plaincopy

  1. void insertsort(int *arr,int n)  
  2. {  
  3.     for(int i=1; i<n; ++i)  
  4.     {  
  5.         int temp = arr[i];  
  6.         int j = i-1;  
  7.         for(; j>=0 && temp<arr[j] ; --j)  
  8.         {   arr[j+1] = arr[j];  }  
  9.         arr[j+1] = temp;  
  10.     }     
  11. }  


直接插入排序，是一种十分有用的简单排序算法，由于其一些优秀的特性，在高级排序中往往会混合 直接插入排序，那么我们就来详细看看，直接插入排序的特点：

（1）稳定的，这点不多做解释，参见冒泡排序的说明

（2）最好情况下，只做 n-1 次比较，不做任何移动，比如 [ 1, 2, 3, 4, 5 ] 这个序列，算法a.检查2 能否插入1 前==>不能；b.检查3能否插入到2前==>不能；...以此类推，只需做完 n-1 次比较就完成排序，0次移动数据操作。直接插入排序的最好情况是【数据完全有序】

（3）最坏情况下，做 n²/2 次比较，做 n²/2 次移动数据操作，比如 [ 5, 4, 3, 2, 1 ]这个序列，4需要插入到5前，3需要插入到4,5前，...1需要插入到2,3,4,5前，同样由等差数列求和公式，可得比较次数和移动次数都是n(n-1)/2,简记为n²/2。直接插入排序的最好情况是【数据完全逆序】

（4）有人说直接插入排序是在序列越有序表现越好，数据越逆序表现越差，其实这种说法是错误的。举个例子说明，序列a [ 6,1,2,3,4,0 ] ，数据其实已经基本有序，只是0,6的位置不对，简单0,6交换即可得到正确序列，但插入排序会把 1,2,3,4以此插入到6前，在把0插入到1,2,3,4,6前，几乎有2n次移动操作。可见直接插入排序要想达到高效率，要求的有序不是基本有序，而前半部分完全有序，只有尾部有部分数据无序，例如 [ 0,1,2,3,4,5,5,6,7,8,9,........,107,99,96,101]
对这样一个只有尾部有部分数据无序，且尾部数据不会干扰到序列首部的 [0,1,2,3,4....] 的位置时，直接插入排序 是其他任何算法都无法匹敌的。

 

4.希尔排序

   这是一个神奇的排序，shell排序起初的设计目的就是改进直接插入排序（另外有一种二分插入排序也是对直接插入排序的改进），因为直接插入排序在诸如 [ 6,1,2,3,4,5,0 ] 这样的基本有序数列上表现不佳，人们设想是不是可以让插入的步长更大一些，比如步长为3，则相当于将序列分组为  [ 6,3 ,0 ]  [1,4 ] [ 2,5 ]这样三个子序列进行插入排序，这样[ 6,3,0 ] 一组可以很快地变换到 [ 0,3,6 ] 于是整个序列都很快有序了。

[cpp] view
plaincopy

  1. void shellsort(int *arr,int n)  
  2. {  
  3.     const int dltalen = 9;  
  4.     /*The best known sequence according to research by Marcin Ciura is 
  5.       1, 4, 10, 23, 57, 132, 301, 701, 1750.*/  
  6.     int dlta[dltalen] = {1750,701,301,132,57,23,10,4,1};  
  7.     int temp;  
  8.   
  9.     for(int t=0; t<dltalen; ++t)  
  10.     {  
  11.         int dk = dlta[t];  
  12.         for( int i=dk; i<n; ++i)  
  13.         {     
  14.             temp = arr[i]; /*临时存放*/  
  15.   
  16.             int j = i-dk;  
  17.             for( ; j>=0 && temp<arr[j]; j-=dk)/*移动位置*/  
  18.             {   arr[j+dk] = arr[j]; }  
  19.   
  20.             arr[j+dk] = temp;/*插入*/                       
  21.         }  
  22.     }  
  23. }  



希尔排序最有趣的地方在于她的步长序列选择上，步长序列选择的好坏直接决定了算法的效率，这也是为什么希尔排序效率是一个n²/2 ~nlog²n的原因，纠正一下传说来自《大话数据结构》的表中将希尔排序记作了n²/2 ~nlogn，这是不对的，目前的理论研究证明的希尔排序最好效率是nlog²n，这个logn上的平方是不能少的，差距很大的。上面的希尔排序中使用一个特殊的序列，是Marcin Ciura发布的研究报告中得到的目前已知最好序列，在使用这个特别的步长序列时，希尔排序的效率是nlog²n。论文的原文在：http://oeis.org/A102549，大家可以详细研究一下。那么希尔排序有哪些特点呢？



（1）希尔排序是不稳定的



（2）希尔排序特别适合于，大部分数据基本有序，只有少量数据无序的情况下，如 [ 6,1,2,3,4,5,0 ] 希尔排序能迅速定位到无序数据，从而迅速完成排序



（3）希尔排序的步长序列，无论如何选择最后一个必须是1，因为希尔排序的最后一步本质上就是直接插入排序，只是通过前面的步长排序，将序列尽量调整到直接插入排序的最高效状态。



（4）研究表明优良的步长序列选择下，在中小规模数据排序时，希尔排序是可以快过快速排序的。因为希尔排序的最佳步长下效率是 n*logn*logn*a(非常小常数因子) ，而快速排序的效率是 n*logn*b(小常数因子)，在 n 小于一定规模时，logn*a 是可能小于b的，比如 a=0.25，b=4，n = 65535；此时logn*a<4 ，b=4；当然我一直没有看到希尔排序的确切常数因子报告，倒是隐约记得在什么地方看到快速排序的常数因子是4，但无法确定，如果谁知道快速排序的确切常数因子，麻烦告知。



 



5.堆排序



    堆排序是由于其最坏情况下nlogn时间复杂度，以及o(1)的空间复杂度而被人们记住的。在数据量巨大的情况下，堆排序的效率在慢慢接近快速排序。下面先看正统的堆排序实现：







[cpp] view

 plaincopy










    

  1. 
void heapAdjust( int *heap, int low, int high )  
    2. 

  2. 
{  
    3. 

  3. 
    int temp = heap[low];  
    4. 

  4. 
    for( int i=low*2+1; i<=high; i*=2)  
    5. 

  5. 
    {                                     /************************/  
    6. 

  6. 
        if( i<high && heap[i]<=heap[i+1] )/*         A点          */  
    7. 











														

							

			

				返回
			

			

			
			
			
		

		

			
			
		

                

		





















			

		

	
	




	
	


		
						
		

			【上篇】
【下篇】			
			
			
			
		

		
								
		

		

			

				


				

				

				

					
作者: 

				

			

			
				
			
			
			
			

		

		

			
			
		

		
	

	
			
		
抱歉!评论已关闭.

							







	
	

	返回首页

		
	





	Copyright © 2013-2018 学步园  保留所有权利.

	软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
		

必威体育

	

必威电竞