计算机排序算法主要分为内排序和外排序，内排序主要指数据存储在内存中的排序，外排序通常指待排序的数据量很大，而且大部分数据存储于文件中，排序时需要读写文件的排序。通常大家讨论的都是内排序，因为内排序是外排序的根基，通常外排序过程都程序要辅助内排序。

　　最常见的内排序是冒泡排序，其时间复杂度为O(n^2), 空间复杂度为O(1)，基本上属于就地排序，而且该算法具有稳定性，在数据量不大，而且顺序基本已经排列好的情况下，该算法应该被优先考虑，其实现代码如下：

冒泡排序（Bubble Sort）

• //Data swop function
• void Swap(int &p,int &q)
• {
•     p=p^q;
•     q=p^q;
•     p=p^q;
• }
• //Bubble sort
• void BuubleSort(int ArrayInput[],int nNum)
• {
•     int i = 0, j=0;
•     for( i=0; i<nNum-1; i++ )
•     {
•          for(j=0; j<nNum-i-1; j++)
•          {
•               if(ArrayInput[j] > ArrayInput[j+1])
•               {
•                   Swap( ArrayInput[j], ArrayInput[j+1] );
•               }
•          }
•     }
• }
• int _tmain(int argc, _TCHAR* argv[])
• {
•     int nNum = 10;
•     int ArrayInput[] = {2,3,1,4,8,8,9,7,6,5};
•     BuubleSort(ArrayInput, nNum);
•     for(int i=0; i<nNum; i++)
•     {
•          cout << ArrayInput << " ";
•     }
•     cout <<endl;
•     return 0;
• }
• 
  

　　另一个比较常用的内排序是快速排序，其平均时间复杂度为O(nlgn), 最坏时间复杂度为O(n^2), 该算法为不稳定排序算法，通常对大量数据进行排序时，时间优势还是比较明显的。

快速排序（Quick Sort）

N个元素被分成3组：left, right, pivot，其中Left<=pivot<=right，所以left和right可以分别排序，而且Quick Sort中可以省去对结果组合的步骤,代码如下:

• //Data swop function
  
• void Swap(int &p,int &q)                           
  
• {                                                  
  
•     p=p^q;
  
•     q=p^q;     
  
•     p=p^q;                                       
  
• }  
  
• 
  
• //Partition function
  
• int Partition(int ArrayInput[],int nLow,int nHigh)                 
  
• {                                                  
  
•     int i = 0, j=0, nTemp=0;                                                
  
•     i=nLow;
  
•     j=nHigh;                                 
  
•     nTemp=ArrayInput;   
  
• 
  
•     do                                                
  
•     {                                                
  
•         //From right to left
  
•         while((ArrayInput[j]>nTemp) && (i<j))                     
  
•         j--;                                            
  
•         if(i<j)                                          
  
•         Swap(ArrayInput[i++],ArrayInput[j]);  
  
• 
  
•         //From left to right
  
•         while((ArrayInput<=nTemp) && (i<j))                     
  
•         i++;                                            
  
•         if(i<j)                                          
  
•         Swap(ArrayInput[j--],ArrayInput);            
  
•     }while(i!=j);   
  
• 
  
•     ArrayInput=nTemp;                                       
  
•     return i;                                         
  
• }
  
• 
  
• //Quick sort
  
• void Quick_sort(int ArrayInput[],int nLow,int nHigh)            
  
• {                                                  
  
•     int i = 0;                                                         
  
•     if(nLow < nHigh)                                         
  
•     {                                                
  
•         i=Partition(ArrayInput , nLow, nHigh);                          
  
•         Quick_sort(ArrayInput , nLow, i-1);                           
  
•         Quick_sort(ArrayInput , i+1, nHigh);                           
  
•     }                                                
  
• }
  
• 
  
• int _tmain(int argc, _TCHAR* argv[])
  
• {
  
•     int ArrayInput[] = {2,3,1,4,8,8,9,7,6,5};                                      
  
•     int i= 0;
  
•     int nNum = 10;                                                   
  
•                         
  
•     Quick_sort(ArrayInput, 0, nNum-1);   
  
•    
  
•     for(i=0; i<nNum; i++)                                
  
•     {
  
•         cout<<ArrayInput<<" ";         
  
•     }                       
  
•     cout<<endl;   
  
•     return 0;
  

来挣黑马币