常用计算机排序算法简单总结

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

 

　　最常见的内排序是冒泡排序，其时间复杂度为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[i] << " ";
    }

    cout <<endl;
    return 0;
}

 

插入排序

 

 void insertion_sort(int A[], int len)
 {
     int i=0;
     int j=0;
     int key=0;
     for (j=1;j<len;j++)
     {
         i=j-1;
         key=A[j];
         while (i>=0&&A[i]>key)
         {
             A[i+1]=A[i];
             i--;
         }
         A[i+1]=key;
     }
 }

选择排序

#include <iostream>

void selectSort(int A[], int len)
{
    int i=0;
    int j=0;
    int nSmallest=0;
    
    for(i=0;i<len;i++)
    {
       nSmallest=i;
       j=i+1;
       for(;j<len;j++)
       {
           if(A[j]<A[nSmallest])
           {
               nSmallest = j;
           }
       }
       
       if(nSmallest !=i)
       {
           int temp=A[nSmallest];
           A[nSmallest]=A[i];
           A[i]=temp;
       }
    }
}

int main()
{    
    int A[10]={12,4,15,3,22,34,2,1,8,10};
    selectSort(A,10);
    for(int i=0;i<10;i++)
    {
     std::cout << A[i] << " ";
    }
    
    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[i];    

    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[i]<=nTemp) && (i<j))                     
        i++;                                            
        if(i<j)                                          
        Swap(ArrayInput[j--],ArrayInput[i]);             
    }while(i!=j);   

    ArrayInput[i]=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[i]<<" ";          
    }                       
    cout<<endl;   
    return 0;
}