中级程序员必须懂的20大基础算法（1）——排序

XDSoft

算法的入门级研究一般都是从“排序”和“查找”开始的。“排序算法”和她的姊妹“查找算法”是很多复杂算法的基础，也是很多复杂系统的基础。比如Linux中最复杂的虚拟内存管理就是基于“红-黑树”查找算法的；Solaris是基于AVL树查找算法；MySQL是基于B树查找算法；P2P技术是基于DHT哈希算法……（待补充。。。）

今天推出的中级程序员必须懂的20大基础算法专题，通过介绍各种基本排序和查找算法，梳理一下计算机算法的基础，为后面介绍那些复杂算法做铺垫。这里首先从各种排序算法的梳理开始.。
对于排序的算法我想先做一点简单的比较，首先是感性比较（比较符合我的性格一点），通过编程把《数据结构》中9大经典排序算法的时间性能进行比较，我的环境是
VC6.0(Release)＋win2000pro+128MDDR+P4(1.6G)
因为在多任务操作系统下，系统将进行进程序调度，影响实验结果。以下是经过稍微修正过的值。如果要取得更准确的值，我们得多次实验求其平均值
。

排序算法实验比较(单位：秒)

方法	1K	10K	100K	200K	100K
					正序	逆序
冒泡排序	0	0.422	44.790	188.462	0	31.459
冒泡排序2	0	0.281	30.335	131.771	0	27.568
快速排序	0	0	0.016	0.047	5.095	7.002
直接选择排序	0	0.141	16.878	79.332	16.785	33.242
堆排序	0	0	0.031	0.109	0.031	0.015
直接插入排序	0	0.047	8.705	57.800	0	24.865
Shell排序	0	0	0.047	0.110	0.015	0.015
归并排序	0	0	0.031	0.094	0.032	0.032
基数排序	0	0	0.47	0.109	0.047	0.046

有了感性认识，我们再来理性认识它：
(1)稳定性比较
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的
选择排序、希尔排序、快速排序、堆排序是不稳定的

(2)时间复杂性比较
插入排序、冒泡排序、选择排序的时间复杂性为O(n^2)
其它非线形排序的时间复杂性为O(nlog2n)
线形排序的时间复杂性为O(n)（线性排序包括计数排序、基数排序后面会介绍）;

(3)辅助空间的比较
线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);

(4)其它比较
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
若待排序的记录的关键字在一个明显有限范围内时，且空间允许是用桶排序。
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。宜用归并排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

综上，我们编程时，最常见的情况是n较大时，元素比较随机，但对稳定性一般不作要求，所以引出快速排序。

快速排序的算法思想如下：首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。 通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多。
[cpp] view plaincopy

• #include <iostream.h>   
•   
• void run(int* pData,int left,int right)   
• {   
•     int i,j;   
•     int middle,iTemp;   
•     i = left;   
•     j = right;   
•     middle = pData[(left+right)/2]; //求中间值   
•     do{   
•         while((pData<middle) && (i<right))//从左扫描大于中值的数   
•             i++;        
•         while((pData[j]>middle) && (j>left))//从右扫描大于中值的数   
•             j--;   
•         if(i<=j)//找到了一对值   
•         {   
•             //交换   
•             iTemp = pData;   
•             pData = pData[j];   
•             pData[j] = iTemp;   
•             i++;   
•             j--;   
•         }   
•      }while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）   
•   
•      //当左边部分有值(left<j)，递归左半边   
•      if(left<j)   
•          run(pData,left,j);   
•      //当右边部分有值(right>i)，递归右半边   
•      if(right>i)   
•          run(pData,i,right);   
• }   
•   
• void QuickSort(int* pData,int Count)   
• {   
•      run(pData,0,Count-1);   
• }   
•   
• void main()   
• {   
•     int data[] = {10,9,8,7,6,5,4};   
•     QuickSort(data,7);   
•     for (int i=0;i<7;i++)   
•         cout<<data<<" ";   
•     cout<<"/n";   
• }   
  
  

快速排序是冒泡排序的改进，它通过一次交换能消除多个逆序，这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下，它的排序时间复杂度为Ｏ(nlog2n)。即每次划分序列时，能均匀分成两个子串。但最差情况下它的时间复杂度将是Ｏ(n^2)。即每次划分子串时，一串为空，另一串为m-1（程序中的100K正序和逆序就正是这样，如果程序中采用每次取序列中部数据作为划分点，那将在正序和逆时达到最优）。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢，这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”，在理论上讲，如果每次能均匀划分序列，它将是最快的排序算法，因此称它作快速排序。虽然很难均匀划分序列，但就平均性能而言，它仍是基于关键字比较的内部排序算法中速度最快者。

冒泡排序的核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好：
[cpp] view plaincopy

• #include <iostream.h>   
•   
• void BubbleSort(int* pData,int Count)   
• {   
•     int iTemp;   
•     for(int i=1;i<Count;i++)   
•     {   
•         for(int j=Count-1;j>=i;j--)   
•         {   
•             if(pData[j]<pData[j-1])   
•             {   
•                 iTemp = pData[j-1];   
•                 pData[j-1] = pData[j];   
•                 pData[j] = iTemp;   
•             }   
•         }   
•     }   
• }   
•   
• void main()   
• {   
•     int data[] = {10,9,8,7,6,5,4};   
•     BubbleSort(data,7);   
•     for (int i=0;i<7;i++)   
•         cout<<data<<" ";   
•     cout<<"/n";   
• }   
  
  

在最优情况下只需要经过n-1次比较即可得出结果，（这个最优情况那就是序列己是正序，从100K的正序结果可以看出结果正是如此），但在最坏情况下，即倒序（或一个较小值在最后），下沉算法将需要n(n-1)/2次比较。所以一般情况下，特别是在逆序时，它很不理想。它是对数据有序性非常敏感的排序算法。

通常的冒泡是单向的，还有一种双向的冒泡算法，也就是说还要进行反向的工作。双向冒泡代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。写这段代码的作者认为这样可以在冒泡的基础上减少一些交换：
[cpp] view plaincopy

• #include <iostream.h>   
• void Bubble2Sort(int* pData,int Count)   
• {   
•     int iTemp;   
•     int left = 1;   
•     int right =Count -1;   
•     int t;   
•     do   
•     {   
•         //正向的部分   
•         for(int i=right;i>=left;i--)   
•         {   
•            if(pData<pData[i-1])   
•            {   
•                iTemp = pData;   
•                pData = pData[i-1];   
•                pData[i-1] = iTemp;   
•                t = i;   
•            }   
•         }   
•         left = t+1;   
•   
•         //反向的部分   
•         for(i=left;i<right+1;i++)   
•         {   
•             if(pData<pData[i-1])   
•             {   
•                 iTemp = pData;   
•                 pData = pData[i-1];   
•                 pData[i-1] = iTemp;   
•                 t = i;   
•             }   
•         }   
•         right = t-1;   
•     }while(left<=right);   
• }   
•   
• void main()   
• {   
•     int data[] = {10,9,8,7,6,5,4};   
•     Bubble2Sort(data,7);   
•     for (int i=0;i<7;i++)   
•         cout<<data<<" ";   
•     cout<<"/n";   
• }   
  
  

它是冒泡排序的改良（一次下沉再一次上浮），最优情况和最坏情况与冒泡排序差不多，但是一般情况下它要好过冒泡排序，它一次下沉，再一次上浮，这样避免了因一个数的逆序，而造成巨大的比较。如（2,3,4,…,n-1,n,1），用冒泡排序需要n(n-1)/2次比较，而此排序只要3轮,共比较(n-1)+(n-2)+(n-3)次，第一轮1将上移一位，第二轮1将移到首位，第三轮将发现无数据交换，序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法，只适合于数据基本有序的排序。

介绍完了快速排序以及其稳定版的冒泡排序，接下来附带介绍三个简单的比较排序。这三个方法很简单，作为跟快速排序对比的排序方法。
（1）直接选择排序
算法思想：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。
这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从省下的部分中选择最小的与第二个交换，这样往复下去。
[cpp] view plaincopy

• #include <iostream.h>   
• void SelectSort(int* pData,int Count)   
• {   
•     int iTemp;   
•     int iPos;   
•     for(int i=0;i<Count-1;i++)   
•     {   
•         iTemp = pData;   
•         iPos = i;   
•         for(int j=i+1;j<Count;j++)   
•         {   
•             if(pData[j]<iTemp)   
•             {   
•                 iTemp = pData[j];   
•                 iPos = j;   
•             }   
•         }   
•         pData[iPos] = pData;   
•         pData = iTemp;   
•     }   
• }   
•   
• void main()   
• {   
•     int data[] = {10,9,8,7,6,5,4};   
•     SelectSort(data,7);   
•     for (int i=0;i<7;i++)   
•         cout<<data<<" ";   
•     cout<<"/n";   
• }   
  
  

简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数据可以发现它耗时相差不多，相差的只是数据移动时间），可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。
（2）直接插入排序
插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张。算法思想：经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L和L[i-1]，如果L[i-1]≤ L，则L[1..i]已排好序，第i遍处理就结束了；否则交换L与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。

[cpp] view plaincopy

• #include <iostream.h>   
• void InsertSort(int* pData,int Count)   
• {   
•     int iTemp;   
•     int iPos;   
•     for(int i=1;i<Count;i++)   
•     {   
•         iTemp = pData;   
•         iPos = i-1;   
•         while((iPos>=0) && (iTemp<pData[iPos]))   
•         {   
•             pData[iPos+1] = pData[iPos];   
•             iPos--;   
•         }   
•         pData[iPos+1] = iTemp;   
•     }   
• }   
•   
• void main()   
• {   
•     int data[] = {10,9,8,7,6,5,4};   
•     InsertSort(data,7);   
•     for (int i=0;i<7;i++)   
•         cout<<data<<" ";   
•     cout<<"/n";   
• }   
  
  

简单的插入排序，每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。
（3）归并排序
归并算法(merge)，也叫合并算法，指的是将两个已经排序的序列合并成一个序列的操作。 　　
如　设有数列{6，202，100，301，38，8，1} 　　
初始状态： [6] [202] [100] [301] [38] [8] [1]
比较次数 　i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ]　   3 　　
           i=2 [ 6 100 202 301 ] [ 1 8 38 ]　        4 　　
           i=3 [ 1 6 8 38 100 202 301 ]              4 　　
总计：　11次
[cpp] view plaincopy

• void MergeSort(int array[], int first, int last)  
• {  
• 　　int mid = 0;  
• 　　if(first<last)  
• 　　{  
• 　　    mid = (first+last)/2;  
• 　　    MergeSort(array, first, mid);  
• 　　    MergeSort(array, mid+1,last);  
• 　　    Merge(array,first,mid,last);  
• 　　}  
• }   
  

我们可以看到，归并算法运用了递归非常简单，归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。
最后，我在网上找到一个最漂亮的快速排序代码，使用C++模板类来写的，以作为本篇文章的结尾：
[cpp] view plaincopy

• //MyData.h文件   
• ///////////////////////////////////////////////////////   
• class CMyData   
• {   
• public:   
•     CMyData(int Index,char* strData);   
•     CMyData();   
•     virtual ~CMyData();   
•   
•     int m_iIndex;   
•     int GetDataSize(){ return m_iDataSize; };   
•     const char* GetData(){ return m_strDatamember; };   
•     //这里重载了操作符：   
•     CMyData& operator =(CMyData &SrcData);   
•     bool operator <(CMyData& data );   
•     bool operator >(CMyData& data );   
•   
• private:   
•     char* m_strDatamember;   
•     int m_iDataSize;   
• };   
• ////////////////////////////////////////////////////////   
•   
• MyData.cpp文件   
• ////////////////////////////////////////////////////////   
• CMyData::CMyData():   
• m_iIndex(0),   
• m_iDataSize(0),   
• m_strDatamember(NULL)   
• {   
• }   
•   
• CMyData::~CMyData()   
• {   
•     if(m_strDatamember != NULL)   
•         delete[] m_strDatamember;   
•     m_strDatamember = NULL;   
• }   
•   
• CMyData::CMyData(int Index,char* strData):   
• m_iIndex(Index),   
• m_iDataSize(0),   
• m_strDatamember(NULL)   
• {   
•     m_iDataSize = strlen(strData);   
•     m_strDatamember = new char[m_iDataSize+1];   
•     strcpy(m_strDatamember,strData);   
• }   
•   
• CMyData& CMyData::operator =(CMyData &SrcData)   
• {   
•     m_iIndex = SrcData.m_iIndex;   
•     m_iDataSize = SrcData.GetDataSize();   
•     m_strDatamember = new char[m_iDataSize+1];   
•     strcpy(m_strDatamember,SrcData.GetData());   
•     return *this;   
• }   
•   
• bool CMyData::operator <(CMyData& data )   
• {   
•     return m_iIndex<data.m_iIndex;   
• }   
•   
• bool CMyData::operator >(CMyData& data )   
• {   
•     return m_iIndex>data.m_iIndex;   
• }   
• ///////////////////////////////////////////////////////////   
•   
• //////////////////////////////////////////////////////////   
• //主程序部分   
• #include <iostream.h>   
• #include "MyData.h"   
•   
• template <class T>   
• void run(T* pData,int left,int right)   
• {   
•     int i,j;   
•     T middle,iTemp;   
•     i = left;   
•     j = right;   
•     //下面的比较都调用我们重载的操作符函数   
•     middle = pData[(left+right)/2]; //求中间值   
•     do{   
•         while((pData<middle) && (i<right))//从左扫描大于中值的数   
•             i++;        
•         while((pData[j]>middle) && (j>left))//从右扫描大于中值的数   
•             j--;   
•         if(i<=j)//找到了一对值   
•         {   
•             //交换   
•             iTemp = pData;   
•             pData = pData[j];   
•             pData[j] = iTemp;   
•             i++;   
•             j--;   
•         }   
•     }while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）   
•   
•     //当左边部分有值(left<j)，递归左半边   
•     if(left<j)   
•         run(pData,left,j);   
•     //当右边部分有值(right>i)，递归右半边   
•     if(right>i)   
•         run(pData,i,right);   
• }   
•   
• template <class T>   
• void QuickSort(T* pData,int Count)   
• {   
•     run(pData,0,Count-1);   
• }   
•   
• void main()   
• {   
•     CMyData data[] = {   
•       CMyData(8,"xulion"),   
•       CMyData(7,"sanzoo"),   
•       CMyData(6,"wangjun"),   
•       CMyData(5,"VCKBASE"),   
•       CMyData(4,"jacky2000"),   
•       CMyData(3,"cwally"),   
•       CMyData(2,"VCUSER"),   
•       CMyData(1,"isdong")   
•     };   
•     QuickSort(data,8);   
•     for (int i=0;i<8;i++)   
•         cout<<data.m_iIndex<<" "<<data.GetData()<<"/n";   
•     cout<<"/n";   
• }