滴水逆向联盟

标题: 排序算法简单总结 [打印本页]
作者: 大禹治水    时间: 2014-10-17 12:13
标题: 排序算法简单总结
计算机排序算法主要分为内排序和外排序，内排序主要指数据存储在内存中的排序，外排序通常指待排序的数据量很大，而且大部分数据存储于文件中，排序时需要读写文件的排序。通常大家讨论的都是内排序，因为内排序是外排序的根基，通常外排序过程都程序要辅助内排序。

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

冒泡排序（Bubble Sort）
  1. //Data swop function
  2. void Swap(int &p,int &q)                           
  3. {                                                  
  4.     p=p^q;
  5.     q=p^q;     
  6.     p=p^q;                                       
  7. }  

  9. //Bubble sort
  10. void BuubleSort(int ArrayInput[],int nNum)
  11. {
  12.     int i = 0, j=0;

  14.     for( i=0; i<nNum-1; i++ )
  15.     {
  16.          for(j=0; j<nNum-i-1; j++)
  17.          {
  18.               if(ArrayInput[j] > ArrayInput[j+1])
  19.               {
  20.                   Swap( ArrayInput[j], ArrayInput[j+1] );
  21.               }
  22.          }
  23.     }

  25. }
  26. int _tmain(int argc, _TCHAR* argv[])
  27. {
  28.     int nNum = 10;
  29.     int ArrayInput[] = {2,3,1,4,8,8,9,7,6,5};
  30.    
  31.     BuubleSort(ArrayInput, nNum);
  32.     for(int i=0; i<nNum; i++)
  33.     {
  34.          cout << ArrayInput << " ";
  35.     }

  37.     cout <<endl;
  38.     return 0;
  39. }
复制代码




　　另一个比较常用的内排序是快速排序，其平均时间复杂度为O(nlgn), 最坏时间复杂度为O(n^2), 该算法为不稳定排序算法，通常对大量数据进行排序时，时间优势还是比较明显的。
快速排序（Quick Sort）
N个元素被分成3组：left, right, pivot，其中Left<=pivot<=right，所以left和right可以分别排序，而且Quick Sort中可以省去对结果组合的步骤,代码如下:


  1. //Data swop function
  2. void Swap(int &p,int &q)                           
  3. {                                                  
  4.     p=p^q;
  5.     q=p^q;     
  6.     p=p^q;                                       
  7. }  

  9. //Partition function
  10. int Partition(int ArrayInput[],int nLow,int nHigh)                 
  11. {                                                  
  12.     int i = 0, j=0, nTemp=0;                                                
  13.     i=nLow;
  14.     j=nHigh;                                 
  15.     nTemp=ArrayInput;   

  17.     do                                                
  18.     {                                                
  19.         //From right to left
  20.         while((ArrayInput[j]>nTemp) && (i<j))                     
  21.         j--;                                            
  22.         if(i<j)                                          
  23.         Swap(ArrayInput[i++],ArrayInput[j]);  

  25.         //From left to right
  26.         while((ArrayInput<=nTemp) && (i<j))                     
  27.         i++;                                            
  28.         if(i<j)                                          
  29.         Swap(ArrayInput[j--],ArrayInput);            
  30.     }while(i!=j);   

  32.     ArrayInput=nTemp;                                       
  33.     return i;                                         
  34. }

  36. //Quick sort
  37. void Quick_sort(int ArrayInput[],int nLow,int nHigh)            
  38. {                                                  
  39.     int i = 0;                                                         
  40.     if(nLow < nHigh)                                         
  41.     {                                                
  42.         i=Partition(ArrayInput , nLow, nHigh);                          
  43.         Quick_sort(ArrayInput , nLow, i-1);                           
  44.         Quick_sort(ArrayInput , i+1, nHigh);                           
  45.     }                                                
  46. }

  48. int _tmain(int argc, _TCHAR* argv[])
  49. {
  50.     int ArrayInput[] = {2,3,1,4,8,8,9,7,6,5};                                      
  51.     int i= 0;
  52.     int nNum = 10;                                                   
  53.                         
  54.     Quick_sort(ArrayInput, 0, nNum-1);   
  55.    
  56.     for(i=0; i<nNum; i++)                                
  57.     {
  58.         cout<<ArrayInput<<" ";         
  59.     }                       
  60.     cout<<endl;   
  61.     return 0;
复制代码


作者: OneTime    时间: 2014-11-17 18:38
其实排序算法中包含着汇编的很多知识:lol:lol



欢迎光临 滴水逆向联盟 (http://dtdebug.com/) Powered by Discuz! X3.2