新浪微博 登陆  注册   设为首页 加入收藏

学PHP >> 设计模式与算法 >> 排序算法总结

排序算法总结

查看次数22445 发表时间2012-10-08 23:16:23

【1】插入排序:

是一个对少量元素进行排序的有效算法。实现比较简单。时间复杂度:O(n^2),空间复杂度:O(1)。是稳定的排序方法。

代码:

  1. //insertion sort 
  2. #include <iostream> 
  3. using namespace std; 
  4.  
  5. //insertion sort 
  6. void InsertionSort(int *a,int n) 
  7.     int temp; 
  8.     for(int i = 1;i < n;++i) 
  9.     { 
  10.         temp = *(a + i); 
  11.         int j = i - 1; 
  12.         while(j >= 0 && *(a + j) > temp) 
  13.         { 
  14.             *(a + j + 1) = *(a + j); 
  15.             --j; 
  16.         } 
  17.         *(a + j + 1) = temp; 
  18.     } 
  19.  
  20. int main() 
  21.     int n,temp; 
  22.     cout<<"please input the number of the values that need to sort:"<<endl; 
  23.     cin>>n; 
  24.     int *a = (int*)malloc(n *sizeof(int)); 
  25.     cout<<"please input each value:"<<endl; 
  26.     for(int i = 0;i < n;++i) 
  27.     { 
  28.         cin>>temp; 
  29.         *(a + i) = temp; 
  30.     } 
  31.     /*
  32.     //insertion sort
  33.     for(int i = 1;i < n;++i)
  34.     {
  35.         temp = *(a + i);
  36.         int j = i - 1;
  37.         while(j >= 0 && *(a + j) > temp)
  38.         {
  39.             *(a + j + 1) = *(a + j);
  40.             --j;
  41.         }
  42.         *(a + j + 1) = temp;
  43.     }*/ 
  44.     InsertionSort(a,n); 
  45.  
  46.     cout<<"the values after sort:"<<endl; 
  47.     for(int i = 0;i < n;++i) 
  48.         cout<<*(a + i)<<" "
 
  1. free(a); 
 

数据测试:


上述代码可以改进的一个地方是:在查找插入位置的时候可以采用二分查找,但是这样依然不可以把时间复杂度降低为O(nlogn),因为移动元素的复杂度没有降低。所以时间复杂度仍然是O(n^2)。

做此改进需要添加函数InsertLoc用于二分查找需要插入的位置,以及修改函数InsertionSort的实现。具体如下:

  1. //改进:用二分查找来找到插入的位置 
  2. //在数组a[low]---a[high]查找val插入的位置 
  3. int InsertLoc(int *a,int low,int high,int val) 
  4.     if(low == high) 
  5.     { 
  6.         if(val > *(a + low))return (low + 1); 
  7.         else 
  8.             return low; 
  9.     } 
  10.     int mid = (low + high) / 2; 
  11.     if(val > *(a + mid) && val > *(a + mid + 1)) 
  12.         return InsertLoc(a,mid + 1,high,val); 
  13.     else if(val < *(a + mid) && val < *(a + mid + 1)) 
  14.         return InsertLoc(a,low,mid,val); 
  15.     else 
  16.         return mid; 
  17.  
  18. void InsertionSort(int *a,int n) 
  19.     int temp,insert_location; 
  20.     for(int i = 1;i < n;++i) 
  21.     { 
  22.         temp = *(a + i); 
  23.         int j = i - 1; 
  24.         insert_location = InsertLoc(a,0,j,temp); 
  25.         cout<<"insert_location:"<<insert_location<<endl; 
  26.         while(j >= insert_location) 
  27.         { 
  28.             *(a + j + 1) = *(a + j); 
  29.             --j; 
  30.         } 
  31.         *(a + insert_location) = temp; 
  32.         for(int m = 0;m <= i;++m) 
  33.             cout<<*(a + m)<<" "
  34.         cout<<endl; 
  35.     } 

【2】选择排序

第一次找出A[0,...,n-1]的最小的元素,与A[0]交换,接着,找出A[1,...,n-1]的次小得元素,与A[1]互换。对A中头n-1个元素执行这一过程。时间复杂度:O(n^2),空间复杂度O(1)。是不稳定的排序方法。比如序列5 8 5 2 9,第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序是不稳定的排序算法

但是严蔚敏的《数据结构》书上面Page289页说,所有时间复杂度为O(n^2)的简单排序都是稳定的。不知道为什么?求指导~~

其给出的简单排序的伪代码:

  1. void SelectSort(SqList &L) 
  2.     //对顺序表L做简单排序 
  3.     for(i = 1;i < L.length;++i)//选择第i小得记录,并交换到位 
  4.     { 
  5.         j = SelectMinKey(L,i);//在L.r[i..L.length]中选择key最小的记录 
  6.         if(i != j)//与第i个记录交换 
  7.         { 
  8.             temp = L.r[i]; 
  9.             L.r[i] = L.r[j]; 
  10.             L.r[j] = temp; 
  11.         } 
  12.     } 

代码:

  1. //选择排序 
  2. #include <iostream> 
  3. using namespace std; 
  4.  
  5. void ChoseSort(int* a,int n) 
  6.     int temp,minVal,minIndex; 
  7.     for(int i = 0;i < n - 1;++i) 
  8.     { 
  9.         minVal = *(a + i);//记录a[i,...,n-1]之间的最小值 
  10.         minIndex = i;//记录a[i,...,n-1]之间的最小值的下标 
  11.         for(int j = i + 1;j < n;++j) 
  12.         { 
  13.             if(minVal > *(a + j)) 
  14.             { 
  15.                 minVal = *(a + j); 
  16.                 minIndex = j; 
  17.             } 
  18.         } 
  19.         //交换a[i]和a[i,...,n-1]之间的最小值最小值 
  20.         if(minIndex != i) 
  21.         { 
  22.             temp = *(a + i); 
  23.             *(a + i) = *(a + minIndex); 
  24.             *(a + minIndex) = temp; 
  25.         } 
  26.     } 
  27.  
  28. int main() 
  29.     int n,temp; 
  30.     cout<<"please input the number of the values that need to sort:"<<endl; 
  31.     cin>>n; 
  32.     int *a = (int*)malloc(n *sizeof(int)); 
  33.     cout<<"please input each value:"<<endl; 
  34.     for(int i = 0;i < n;++i) 
  35.     { 
  36.         cin>>temp; 
  37.         *(a + i) = temp; 
  38.     } 
  39.     ChoseSort(a,n); 
  40.     cout<<"the values after sort:"<<endl; 
  41.     for(int i = 0;i < n;++i) 
  42.         cout<<*(a + i)<<" "
  43.     free(a); 

【3】合并排序

采用分治法。将n个元素分成各含n/2个元素的子序列,用合并排序法对两个子序列递归的排序(子序列长度为1时递归结束),最后合并两个已排序的子序列得到结果。时间复杂度:O(nlogn),空间复杂度:O(n)。是稳定的排序方法。

代码:

  1. //合并排序 
  2. #include <iostream> 
  3. using namespace std; 
  4.  
  5. #define MAX_VALUE 100000//用于设置哨兵,避免检查是否每一个堆都是空的 
  6.  
  7. //合并两个子数组的函数 
  8. void Merge(int *a,int p,int q,int r) 
  9.     int num1,num2; 
  10.     num1 = q - p + 1; 
  11.     num2 = r - q; 
  12.     int *a1 = (int*)malloc((num1 + 1) *sizeof(int)); 
  13.     int *a2 = (int*)malloc((num2 + 1) *sizeof(int)); 
  14.     for(int i = 0;i < num1;++i) 
  15.         *(a1 + i) = *(a + p + i); 
  16.     *(a1 + num1) = MAX_VALUE;//设置哨兵元素 
  17.     for(int i = 0;i < num2;++i) 
  18.         *(a2 + i) = *(a + q + 1 + i); 
  19.     *(a2 + num2) = MAX_VALUE;//设置哨兵元素 
  20.      
  21.     //进行排序 
  22.     int index1 = 0; 
  23.     int index2 = 0; 
  24.     for(int i = p;i <= r;++i) 
  25.     { 
  26.         if(*(a1 + index1) < *(a2 + index2)) 
  27.         { 
  28.             *(a + i) = *(a1 + index1); 
  29.             ++index1; 
  30.         } 
  31.         else 
  32.         { 
  33.             *(a + i) = *(a2 + index2); 
  34.             ++index2; 
  35.         } 
  36.     } 
  37.     free(a1); 
 
  1. free(a2); 
 
  1. //递归合并排序算法 
  2. void MergeSort(int *a,int p,int r) 
  3.     if(p < r) 
  4.     { 
  5.         int q = (p + r) / 2; 
  6.         MergeSort(a,p,q); 
  7.         MergeSort(a,q + 1,r); 
  8.         Merge(a,p,q,r); 
  9.     } 
  10.  
  11. int main() 
  12.     int n,temp; 
  13.     cout<<"please input the number of the values that need to sort:"<<endl; 
  14.     cin>>n; 
  15.     int *a = (int*)malloc(n *sizeof(int)); 
  16.     cout<<"please input each value:"<<endl; 
  17.     for(int i = 0;i < n;++i) 
  18.     { 
  19.         cin>>temp; 
  20.         *(a + i) = temp; 
  21.     } 
  22.     MergeSort(a,0,n - 1); 
  23.     cout<<"the values after sort:"<<endl; 
  24.     for(int i = 0;i < n;++i) 
  25.         cout<<*(a + i)<<" "
  26.     free(a); 
 

如果不使用哨兵元素,需要修改Merge函数,如下:

  1. //合并两个子数组的函数(不使用哨兵元素) 
  2. void Merge(int *a,int p,int q,int r) 
  3.     int num1,num2; 
  4.     num1 = q - p + 1; 
  5.     num2 = r - q; 
  6.     int *a1 = (int*)malloc(num1 *sizeof(int)); 
  7.     int *a2 = (int*)malloc(num2 *sizeof(int)); 
  8.     for(int i = 0;i < num1;++i) 
  9.         *(a1 + i) = *(a + p + i); 
  10.     for(int i = 0;i < num2;++i) 
  11.         *(a2 + i) = *(a + q + 1 + i); 
  12.      
  13.     //进行排序 
  14.     int index1 = 0; 
  15.     int index2 = 0; 
  16.     int index = p; 
  17.     while(index1 < num1 && index2 <num2) 
  18.     { 
  19.         if(*(a1 + index1) < *(a2 + index2)) 
  20.         { 
  21.             *(a + index) = *(a1 + index1); 
  22.             ++index; 
  23.             ++index1; 
  24.         } 
  25.         else
  26.             *(a + index) = *(a2 + index2); 
  27.             ++index; 
  28.             ++index2; 
  29.         } 
  30.     } 
  31.     while(index1 < num1) 
  32.     { 
  33.         *(a + index) = *(a1 + index1); 
  34.         ++index; 
  35.         ++index1; 
  36.     } 
  37.     while(index2 < num2) 
  38.     { 
  39.         *(a + index) = *(a2 + index2); 
  40.         ++index; 
  41.         ++index2; 
  42.     } 
  43.     free(a1);<pre class="cpp" name="code">  free(a2);</pre> 
  44. <pre></pre> 
  45. <pre class="cpp" name="code">}</pre> 
  46. <p><span style="color: rgb(255, 0, 0); font-family: KaiTi_GB2312; font-size: 24px;"><strong>【4】冒泡排序</strong></span></p> 
  47. <p>每一趟都比较相邻两个元素,若是逆序的,则交换。结束的条件应该是“在一趟排序过程中没有进行过交换元素的操作”。时间复杂度:O(n^2),空间复杂度O(1)。是稳定的排序。</p> 
  48. <pre class="cpp" name="code">#include <iostream> 
  49. using namespace std; 
  50.  
  51. void BubbleSort(int *a,int n) 
  52.     int flag,temp;//标记是否进行过交换操作 
  53.     for(int i = 0;i < n - 1;++i) 
  54.     { 
  55.         flag = 0; 
  56.         for(int j = 0;j < n - 1 - i;++j) 
  57.         { 
  58.             if(*(a + j) > *(a + j + 1)) 
  59.             { 
  60.                 temp = *(a + j); 
  61.                  *(a + j) =  *(a + j + 1); 
  62.                  *(a + j + 1) = temp; 
  63.                  flag = 1; 
  64.             } 
  65.         } 
  66.         if(flag == 0)break
  67.     } 
  68.  
  69. int main() 
  70.     int n,temp; 
  71.     cout<<"please input the number of the values that need to sort:"<<endl; 
  72.     cin>>n; 
  73.     int *a = (int*)malloc(n *sizeof(int)); 
  74.     cout<<"please input each value:"<<endl; 
  75.     for(int i = 0;i < n;++i) 
  76.     { 
  77.         cin>>temp; 
  78.         *(a + i) = temp; 
  79.     } 
  80.     BubbleSort(a,n); 
  81.     cout<<"the values after sort:"<<endl; 
  82.     for(int i = 0;i < n;++i) 
  83.         cout<<*(a + i)<<" "
  84. <pre class="cpp" name="code">   free(a);</pre> 
  85. <pre></pre> 
  86. <pre class="cpp" name="code">}</pre> 
  87. <p><span style="color: rgb(255, 0, 0); font-family: KaiTi_GB2312; font-size: 24px;"><strong>【5】快速排序</strong></span></p> 
  88. <p>它是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将待排序元素分成两个部分,其中一部分元素比另一部分元素小。再分别对这两部分元素进行排序。以达到整个元素序列有序。时间复杂度:O(nlogn),空间复杂度O(logn),是不稳定的算法。</p> 
  89. <p>代码:</p> 
  90. <pre class="cpp" name="code">#include <iostream> 
  91. using namespace std; 
  92.  
  93. int Partition(int *a,int low,int high) 
  94.     int PivotKey = *(a + low);//用第一个元素做枢轴 
  95.     while(low < high) 
  96.     { 
  97.         while(low < high && *(a + high) > PivotKey)--high; 
  98.         *(a + low) = *(a + high); 
  99.         while(low < high && *(a + low) < PivotKey)++low; 
  100.         *(a + high) = *(a + low); 
  101.     } 
  102.     *(a + low) = PivotKey; 
  103.     return low; 
  104.  
  105. void QuickSort(int *a,int low,int high) 
  106.     if(low < high) 
  107.     { 
  108.         int PivotLoc = Partition(a,low,high); 
  109.         QuickSort(a,low,PivotLoc - 1); 
  110.         QuickSort(a,PivotLoc + 1,high); 
  111.     } 
  112.  
  113. int main() 
  114.     int n,temp; 
  115.     cout<<"please input the number of the values that need to sort:"<<endl; 
  116.     cin>>n; 
  117.     int *a = (int*)malloc(n *sizeof(int)); 
  118.     cout<<"please input each value:"<<endl; 
  119.     for(int i = 0;i < n;++i) 
  120.     { 
  121.         cin>>temp; 
  122.         *(a + i) = temp; 
  123.     } 
  124.     QuickSort(a,0,n - 1); 
  125.     cout<<"the values after sort:"<<endl; 
  126.     for(int i = 0;i < n;++i) 
  127.         cout<<*(a + i)<<" "
  128.     free(a);}</pre> 
  129. <p><br> 
  130. </p> 
  131. <p><span style="color: rgb(255, 0, 0); font-family: KaiTi_GB2312; font-size: 24px;"><strong>【6】计数排序</strong></span></p> 
  132. <p>计数排序的思想是对每一个输入元素x,确定出小于x的元素的个数。然后我们就可以直接把它放在嘴中输出数组中相应的位置上。</p> 
  133. <p>但是计数排序基于这样一个假设:n个输入元素的每一个大小范围都是[0,k]。</p> 
  134. <p>代码:</p> 
  135. <p><pre class="cpp" name="code">#include <iostream> 
  136. using namespace std; 
  137.  
  138. //Counting Sort Algorithm 
  139. //A:array before sorting 
  140. //B:array after sorting 
  141. //n:the number of A 
  142. //k:all the elements is in [0,k] 
  143. void CountintSort(int A[],int *B,int n,int k,int *C) 
  144.     //初始化C数组 
  145.     for (int i = 0;i <= k;++i) 
  146.     { 
  147.         C[i] = 0; 
  148.     } 
  149.  
  150.     for (int i = 0;i < n;++i) 
  151.     { 
  152.         ++C[A[i]];//C[i]:值等于i的元素的个数 
  153.     } 
  154.  
  155.     for (int i = 1;i <= k;++i) 
  156.     { 
  157.         C[i] += C[i - 1];//C[i]:值小于等于i的元素的个数 
  158.     } 
  159.      
  160.     for (int i = n - 1;i >= 0;--i) 
  161.     { 
  162.         B[C[A[i]] - 1] = A[i];//注意:下标索引从0开始! 
  163.         --C[A[i]]; 
  164.     } 
  165.  
  166. int main() 
  167.     int A[6] = {2,7,1,4,0,3}; 
  168.     int n = 6; 
  169.     int k = 7; 
  170.     int *B = (int *)malloc(n *sizeof(int)); 
  171.     int *C = (int *)malloc((k + 1) *sizeof(int)); 
  172.     cout << "排序之前的元素:" << endl; 
  173.     for (int i = 0;i < n;++i) 
  174.     { 
  175.         cout << A[i] << " "
  176.     } 
  177.     cout << endl; 
  178.     CountintSort(A,B,n,k,C); 
  179.     cout << "排序之后的元素:" << endl; 
  180.     for (int i = 0;i < n;++i) 
  181.     { 
  182.         cout << B[i] << " "
  183.     } 
  184.     cout << endl; 
  185.     free(B); 
  186.     free(C); 
  187. }</pre><br> 
  188. 运行结果:<p></p> 
  189. <p><img alt="" src="http://my.csdn.net/uploads/201206/10/1339316958_2887.jpg"><br> 
  190. </p> 
  191. <p><strong>时间复杂度分析:</strong></p> 
  192. <p>时间复杂度是O(k + n)。一般,当k = O(n)时,常常采用计数排序。这时候的运行时间为O(n)。</p> 
  193. <p>计数排序是稳定的排序。</p> 
  194. <p><br> 
  195. </p> 
  196. <p>一些好的参考资料:不同排序算法间的比较:<a href="http://commons.wikimedia.org/wiki/File:SortingAlgoComp.png">http://commons.wikimedia.org/wiki/File:SortingAlgoComp.png</a><br> 
  197. 一些排序算法的 C 及 Pascal 实现 :<br> 
  198. <a href="http://www.nocow.cn/index.php/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95">http://www.nocow.cn/index.php/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95</a></p> 
  199. <p>最后,简要比较一下各排序算法,转自维基百科:</p> 
  200. <p><span id=".E7.AE.80.E8.A6.81.E6.AF.94.E8.BE.83"class="mw-headline">简要比较</span> 
  201. <table class="wikitable     "
  202. <tbody> 
  203. <tr> 
  204. <th rowSpan="2">名称</th> 
  205. <th rowSpan="2">数据对象</th> 
  206. <th rowSpan="2">稳定性</th> 
  207. <th colSpan="2">时间复杂度</th> 
  208. <th rowSpan="2">空间复杂度</th> 
  209. <th rowSpan="2">描述</th> 
  210. </tr> 
  211. <tr> 
  212. <th>平均</th> 
  213. <th>最坏</th> 
  214. </tr> 
  215. <tr> 
  216. <td>插入排序</td> 
  217. <td>数组、链表</td> 
  218. <td>√</td> 
  219. <td colSpan="2"><span dir="ltr"class="texhtml"><em>O</em>(<em>n</em><sup>2</sup>)</span></td> 
  220. <td>O(1)</td> 
  221. <td>(有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。对数组:比较得少,换得多。</td> 
  222. </tr> 
  223. (转发请注明转自:学PHP)    


      相关推荐



    1楼 学phper说: 2015-03-10 19:22:14
    1
    2楼 -1'说: 2015-03-10 19:22:15
    1
    3楼 学phper说: 2015-05-04 17:17:51
    1
    4楼 -1'说: 2015-05-04 17:17:51
    1

      发表评论
    昵称:
    (不超过20个字符或10个汉字)
    内容: