内部排序

分手后的思念是犯贱 2022-08-26 03:52 138阅读 0赞

参考资料：[http://www.cnblogs.com/easonliu/archive/2012/10/19/2731358.html][http_www.cnblogs.com_easonliu_archive_2012_10_19_2731358.html]

常用的内部排序方法有：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序（一关键字、多关键字）。

===========================================================

时间复杂度

排序方法                 最好情况                最坏情况             平均情况              稳定性

冒泡排序                   O(n)                      O(n2)                 O(n2)                 稳定

快速排序                   O(nlogn)               O(n2)                  O(nlogn)            不稳定

简单选择排序                                                                   O(n2)               不稳定

堆排序                                                O(nlogn)                                      不稳定

直接插入排序            O(n)                      O(n2)                  O(n2)                  稳定

希尔排序                                                                       O(n1.3)              不稳定

归并排序                    O(nlogn)               O(nlogn)             O(nlogn)               稳定

基数排序                                                                       O(d(r+n))              稳定

===================================================================

冒泡排序：

1.基本思想：

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

2.排序过程：

设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

不多说了，上代码：

[view source][]

[print][] [?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>#include &lt;iostream&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>03</code></td> 
   <td><code>using</code> <code> namespace</code> <code>std;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>11</code></td> 
   <td><code>void</code> <code> popSort(</code><code>int</code> <code>*index,</code><code>int</code> <code>len){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>13</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>16</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>bool</code> <code>flag = </code><code>false</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>18</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(index[j-1] &gt; index[j]){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>19</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>swap(index[j-1],index[j]);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>24</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>31</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>index[] = {1,2,3,4,5,6,7,8,9,0};</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>32</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>popSort(index,</code><code>sizeof</code><code>(index)/</code><code>sizeof</code><code>(</code><code>int</code><code>));</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>34</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>cout &lt;&lt; index[i] &lt;&lt; </code><code>" "</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>37</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>1;</code></td> 
  </tr> 
 </tbody> 
</table>

快速排序：

1.基本思想：

在 当前无序区R\[1..H\]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R\[1..I-1\]和 R\[I+1..H\]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即 R\[1..I-1\]≤X.Key≤R\[I+1..H\](1≤I≤H)，当R\[1..I-1\]和R\[I+1..H\]均非空时，分别对它们进行上述的划分过 程，直至所有无序子区中的数据元素均已排序为止。

2.排序过程：

【示例】：

初始关键字 \[49 38 65 97 76 13 27 49］

第一次交换后 ［27 38 65 97 76 13 49 49］

第二次交换后 ［27 38 49 97 76 13 65 49］

J向左扫描，位置不变，第三次交换后 ［27 38 13 97 76 49 65 49］

I向右扫描，位置不变，第四次交换后 ［27 38 13 49 76 97 65 49］

J向左扫描 ［27 38 13 49 76 97 65 49］

（一次划分过程）

初始关键字 ［49 38 65 97 76 13 27 49］

一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］

二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］

三趟排序之后 13 27 38 49 49 ［65］76 97

最后的排序结果 13 27 38 49 49 65 76 97

上代码：

[view source][]

[print][] [?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>#include &lt;iostream&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>03</code></td> 
   <td><code>using</code> <code> namespace</code> <code>std;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>11</code></td> 
   <td><code>int</code> <code> partition(</code><code>int</code> <code> *index,</code><code>int</code> <code>begin,</code><code>int</code> <code>end){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>12</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>i = begin;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>15</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(i&lt;j){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>16</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(index[i]&lt;=index[j]&amp;&amp;i&lt;j){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>20</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>swap(index[i],index[j]);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>22</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>while</code><code>(index[i]&lt;=index[j]&amp;&amp;i&lt;j){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>26</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>swap(index[i],index[j]);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>29</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>i;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>33</code></td> 
   <td><code>void</code> <code> quickSort(</code><code>int</code> <code> *index,</code><code>int</code> <code>begin,</code><code>int</code> <code>end){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>34</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(begin&gt;=end){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>35</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>37</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>q = partition(index,begin,end);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>38</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>quickSort(index,begin,q-1);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>39</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>quickSort(index,q+1,end);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>44</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>index[] = {2,6,2,3,6,7,8,3,1,2};</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>45</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>quickSort(index,0,9);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>47</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>cout &lt;&lt; index[i] &lt;&lt; </code><code>" "</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>50</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>1;</code></td> 
  </tr> 
 </tbody> 
</table>

选择排序

1.基本思想：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2.排序过程：

【示例】：

初始关键字 \[49 38 65 97 76 13 27 49\]

第一趟排序后 13 ［38 65 97 76 49 27 49\]

第二趟排序后 13 27 ［65 97 76 49 38 49\]

第三趟排序后 13 27 38 \[97 76 49 65 49\]

第四趟排序后 13 27 38 49 \[49 97 65 76\]

第五趟排序后 13 27 38 49 49 \[97 97 76\]

第六趟排序后 13 27 38 49 49 76 \[76 97\]

第七趟排序后 13 27 38 49 49 76 76 \[ 97\]

最后排序结果 13 27 38 49 49 76 76 97

上代码：

[view source][]

[print][] [?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>#include &lt;iostream&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>03</code></td> 
   <td><code>using</code> <code> namespace</code> <code>std;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>11</code></td> 
   <td><code>void</code> <code> selectSort(</code><code>int</code> <code> *index,</code><code>int</code> <code>len){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>15</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(index[j]&lt;index[pMin]){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>26</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>index[] = {2,6,2,3,6,7,8,3,1,2};</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>27</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>selectSort(index,</code><code>sizeof</code><code>(index)/</code><code>sizeof</code><code>(</code><code>int</code><code>));</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>29</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>cout &lt;&lt; index[i] &lt;&lt; </code><code>" "</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>32</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>1;</code></td> 
  </tr> 
 </tbody> 
</table>

堆排序

1.基本思想：

堆排序是一树形选择排序，在排序过程中，将R\[1..N\]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

2.堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：

Ki≤K2i Ki ≤K2i+1(1≤ I≤ \[N/2\])

堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个 堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等 于其孩子的关键字，则称之为大根堆。

3.排序过程：

堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无 序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐 步向前扩大到整个记录区。

【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

上代码：

[view source][]

[print][] [?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>#include &lt;iostream&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>03</code></td> 
   <td><code>using</code> <code> namespace</code> <code>std;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>11</code></td> 
   <td><code>//堆中的元素在数组中从索引1开始，索引0中存储的是</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>12</code></td> 
   <td><code>//堆中当前的元素个数。</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>13</code></td> 
   <td><code>void</code> <code> heapAdjust(</code><code>int</code> <code> *index,</code><code>int</code> <code>pIndex,</code><code>int</code> <code>end){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>14</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code><code>(</code><code>int</code> <code>j = 2*pIndex ; j &lt;= end ; j = 2*pIndex){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>15</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(j&lt;end &amp;&amp; index[j]&lt;index[j+1]){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>18</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(index[pIndex]&gt;=index[j]){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>19</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>break</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>21</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>swap(index[pIndex],index[j]);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>22</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>pIndex = j;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>27</code></td> 
   <td><code>void</code> <code> heapSort(</code><code>int</code> <code> *index,</code><code>int</code> <code>len){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>29</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>heapAdjust(index,i,len);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>32</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>swap(index[1],index[i]);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>33</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>heapAdjust(index,1,i-1);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>38</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>index[] = {10,2,6,2,3,6,7,8,3,1,2};</code><code>//10表示有十个元素</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>39</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>heapSort(index,</code><code>sizeof</code><code>(index)/</code><code>sizeof</code><code>(</code><code>int</code><code>)-1);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>41</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>cout &lt;&lt; index[i] &lt;&lt; </code><code>" "</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>44</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>1;</code></td> 
  </tr> 
 </tbody> 
</table>

直接插入排序

1. 基本思想：

每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

2. 排序过程：

【示例】：

\[初始关键字\] \[49\] 38 65 97 76 13 27 49

J=2(38) \[38 49\] 65 97 76 13 27 49

J=3(65) \[38 49 65\] 97 76 13 27 49

J=4(97) \[38 49 65 97\] 76 13 27 49

J=5(76) \[38 49 65 76 97\] 13 27 49

J=6(13) \[13 38 49 65 76 97\] 27 49

J=7(27) \[13 27 38 49 65 76 97\] 49

J=8(49) \[13 27 38 49 49 65 76 97\]

代码：

[view source][]

[print][] [?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>#include &lt;iostream&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>03</code></td> 
   <td><code>using</code> <code> namespace</code> <code>std;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>11</code></td> 
   <td><code>void</code> <code> insertSort(</code><code>int</code> <code> *index,</code><code>int</code> <code>len){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>13</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>16</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>temp = index[i];</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>18</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>for</code><code>(;j&gt;=0 &amp;&amp; temp&lt;index[j];--j){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>19</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>index[j+1] = index[j];</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>21</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>index[j+1] = temp;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>26</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>index[] = {2,6,2,3,6,7,8,3,1,2};</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>27</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>insertSort(index,</code><code>sizeof</code><code>(index)/</code><code>sizeof</code><code>(</code><code>int</code><code>));</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>32</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>1;</code></td> 
  </tr> 
 </tbody> 
</table>

归并排序

1.排序思想：

设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R\[low..m\]，R\[m+1..high\]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R\[low..high\]中。

2.排序过程：

【示例】：

初始关键字    \[46\]\[38\]\[56\]\[30\]\[88\]\[80\]\[38\]

第一趟归并后\[38 46\]\[30 56\]\[80 88\]\[38\]

第二趟归并后\[30 38 46 56\]\[38 80 88\]

最终归并结果\[30 38 38 46 56 80 88\]

代码：

[view source][]

[print][] [?][Link 1]

<table> 
 <tbody> 
  <tr> 
   <td><code>01</code></td> 
   <td><code>#include &lt;iostream&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>03</code></td> 
   <td><code>using</code> <code> namespace</code> <code>std;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>05</code></td> 
   <td><code>//index为合并后的队列，</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>06</code></td> 
   <td><code>//indexA为合并数组A,lenA为其长度</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>07</code></td> 
   <td><code>//indexB为合并数组B,lenB为其长度</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>08</code></td> 
   <td><code>void</code> <code> merge(</code><code>int</code> <code>*index,</code><code>int</code> <code>*indexA,</code><code>int</code> <code> lenA,</code><code>int</code> <code>*indexB,</code><code>int</code> <code>lenB){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>10</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>*right = </code><code>new</code> <code>int</code><code>[lenB];</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>13</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>memcpy</code><code>(left,indexA,lenA*</code><code>sizeof</code><code>(</code><code>int</code><code>));</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>14</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>memcpy</code><code>(right,indexB,lenB*</code><code>sizeof</code><code>(</code><code>int</code><code>));</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>17</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(i&lt;lenA &amp;&amp; j&lt;lenB &amp;&amp; left[i]&lt;right[j]){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>18</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>index[k] = left[i];</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>21</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>index[k] = right[j];</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>24</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>index[k] = right[j];</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>27</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>index[k] = left[i];</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>32</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>delete</code><code>[] left;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>33</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>delete</code><code>[] right;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>36</code></td> 
   <td><code>void</code> <code> mergeSort(</code><code>int</code> <code> *index,</code><code>int</code> <code>begin,</code><code>int</code> <code>end){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>37</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>if</code><code>(begin&gt;=end){ </code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>38</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>40</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>pMid = begin + ((end-begin)&gt;&gt;1);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>41</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>mergeSort(index,begin,pMid);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>42</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>mergeSort(index,pMid+1,end);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>43</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>merge(&amp;index[begin],&amp;index[begin],pMid-begin+1,&amp;index[pMid+1],end-pMid);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>48</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>int</code> <code>index[] = {2,6,2,3,6,7,8,3,1,2};</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>49</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>mergeSort(index,0,9);</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>51</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>cout &lt;&lt; index[i] &lt;&lt; </code><code>" "</code><code>;</code></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td><code>54</code></td> 
   <td><code>&nbsp;&nbsp;&nbsp;&nbsp;</code><code>return</code> <code>1;</code></td> 
  </tr> 
 </tbody> 
</table>

[http_www.cnblogs.com_easonliu_archive_2012_10_19_2731358.html]: http://www.cnblogs.com/easonliu/archive/2012/10/19/2731358.html
[view source]: http://my.oschina.net/dapengking/blog/120263#viewSource
[print]: http://my.oschina.net/dapengking/blog/120263#printSource
[Link 1]: http://my.oschina.net/dapengking/blog/120263#about