排序算法之初级排序

曾经终败给现在 2022-07-14 10:21 243阅读 0赞

该系列是我看人民邮电出版社的《算法》这本书的一些理解，不写下来感觉很快就忘掉，代码来自原书。

初级排序主要包括简单的选择排序和插入排序，以及插入排序的一个优化：希尔排序。

这里所说的排序，都是基于在原数组上的操作，比较和交换，不是新建一个数组来保存排序的结果。

一：选择排序

总的思想非常简单，就是在当前序列中，找到最小的元素，然后与首位元素交换位置。然后将无序的序列逐渐缩小。

假如有n个元素。

1、在n个元素中找到最小的元素，与第一个交换位置。

2、在n-1个元素中找到最小的元素，与第二个交换位置。

3、与此类推，直到最后一个元素。

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> 
    <div>
      18 
    </div> 
    <div>
      19 
    </div> 
    <div>
      20 
    </div> 
    <div>
      21 
    </div> 
    <div>
      22 
    </div> 
    <div>
      23 
    </div> 
    <div>
      24 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>public</code> 
      <code> static</code> 
      <code>void</code> 
      <code>sort(</code> 
      <code>int</code> 
      <code>a[]){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>N = a.length;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//每个循环交换一个，既是每个位置只交换一次，共N次</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=</code> 
      <code>0</code> 
      <code>;i&lt;N;i++){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>min = i;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//将a[i]和a[i+1]到a[n]中最小的元素交换</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//每一次for循环，可以获得i+1到n中最小元素的下标</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>j=i+</code> 
      <code>1</code> 
      <code>;j&lt;N;j++){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(a[j]&lt;a[min])</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>min=j;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//当前序列最小的值，与i交换位置</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>Example.exch(a, i, min);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

这里寻找最小的元素是通过记录下标的形式，所以整个排序只需要N次的交换即可，是所有排序之中最少的。

时间复杂度：平方级

稳定性：不稳定

举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

当然，要是你新开一个数组来保存结果，每找到一个当前最小的就放到新数组里面，那肯定是稳定的，所以不要太纠结这个。

二：插入排序

假定前面都是已经有序的数组，后面是无序的，后面的元素需要一个个插入到有序数组里面合适的位置中去。

当然这里的插入不是平时理解的插入，不然每插入一次，后面的元素都要不断的往后挪，太过复杂，当然你用链表可以这样做。

简便的做法是，当前元素不断交换位置来“插入”到一个合适的位置。

因为前面的序列都是有序的，所以只要一直比较大小，就能找到合适的位置。而更明智的比法是从后面比起（当前排序是增序），为什么呢？从右边起，数组里面的小，就交换位置，然后一直遇到一个不小的值，就可以确定位置了。说明当前位置，你比后一个小，不小于前一个。

如果是从左边比起，不说了太麻烦了。

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>public</code> 
      <code> static</code> 
      <code>void</code> 
      <code>sort(</code> 
      <code>int</code> 
      <code>a[]){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>N = a.length;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=</code> 
      <code>0</code> 
      <code>;i&lt;N;i++){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//将a[i]插入到a[i-1],a[i-2]....a[0]里面合适的位置</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>j=i;j&gt;</code> 
      <code>0</code> 
      <code>&amp;&amp;a[j]&lt;a[j-</code> 
      <code>1</code> 
      <code>];j--)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>Example.exch(a, j, j-</code> 
      <code>1</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

时间复杂度：平方级

稳定性：稳定，因为元素都是挨个来比较和交换的，并且交换的条件是小于，所以同样大小的数不会交换到前面去。当然，交换条件是小于等于就不行了。

三：希尔排序

选择一个增量（间隔）h，将大数组分为 间隔为h的元素组成的 h个数组，然后对这些数组分别进行插入排序

例如：h=5

![844215-20161206174728085-696577845.png][]

然后h不断对半减小，直至为1，排序结束，例如5、2、1

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> 
    <div>
      18 
    </div> 
    <div>
      19 
    </div> 
    <div>
      20 
    </div> 
    <div>
      21 
    </div> 
    <div>
      22 
    </div> 
    <div>
      23 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>public</code> 
      <code> static</code> 
      <code>void</code> 
      <code>sort(</code> 
      <code>int</code> 
      <code>a[]){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>N = a.length;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>h = N/</code> 
      <code>2</code> 
      <code>;</code> 
      <code>//增量，这里选择总元素的一半作为增量</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(h&gt;=</code> 
      <code>1</code> 
      <code>){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//原数组被分为h个数组，每相隔h个元素组成一个数组，对每个数组进行插入排序</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//对每个数组的元素轮流遍历，可以避免三层循环</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=h;i&lt;N;i++)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>j=i;j&gt;=h&amp;&amp;a[j]&lt;a[j-h];j-=h)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>Example.exch(a, j, j-h);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>h=h/</code> 
      <code>2</code> 
      <code>;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

这个代码非常巧妙，一开始说，原数组被分为h个数组，每相隔h个元素组成一个数组，对每个数组进行插入排序

但是完全这样做的话，会变成3个for的嵌套，我们来看看百度百科上的代码：

![844215-20161206175416366-1603841446.png][]

但是我提供的代码是从h开始的，然后对后续的所有元素进行间隔为h的插入排序即可，简洁高效。

时间复杂度：大于n，小于n的平方，与增量序列的选择有关，N/2并不是最快的，但是便于理解这里使用N/2，关于什么增量最快，还在研究。

稳定性，不稳定。

这是我写给排序算法的辅助类，包括了初始化数组，打印数组，和交换元素

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> 
    <div>
      18 
    </div> 
    <div>
      19 
    </div> 
    <div>
      20 
    </div> 
    <div>
      21 
    </div> 
    <div>
      22 
    </div> 
    <div>
      23 
    </div> 
    <div>
      24 
    </div> 
    <div>
      25 
    </div> 
    <div>
      26 
    </div> 
    <div>
      27 
    </div> 
    <div>
      28 
    </div> 
    <div>
      29 
    </div> 
    <div>
      30 
    </div> 
    <div>
      31 
    </div> 
    <div>
      32 
    </div> 
    <div>
      33 
    </div> 
    <div>
      34 
    </div> 
    <div>
      35 
    </div> 
    <div>
      36 
    </div> 
    <div>
      37 
    </div> 
    <div>
      38 
    </div> 
    <div>
      39 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>public</code> 
      <code> class</code> 
      <code>Example { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//初始化数组</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>static</code> 
      <code>void</code> 
      <code> initArray(</code> 
      <code>int</code> 
      <code>[] a){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>N = a.length;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=</code> 
      <code>0</code> 
      <code>;i&lt;N;i++)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>a[i] = (</code> 
      <code>int</code> 
      <code>)(Math.random()*</code> 
      <code>10</code> 
      <code>);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//打印数组</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>static</code> 
      <code>void</code> 
      <code> print(</code> 
      <code>int</code> 
      <code>[] a){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>N = a.length;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>for</code> 
      <code>(</code> 
      <code>int</code> 
      <code>i=</code> 
      <code>0</code> 
      <code>;i&lt;N;i++)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>System.out.print(a[i]);</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>System.out.println();</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>//交换</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>public</code> 
      <code>static</code> 
      <code>void</code> 
      <code> exch(</code> 
      <code>int</code> 
      <code>[]a,</code> 
      <code>int</code> 
      <code>i,</code> 
      <code>int</code> 
      <code> j){ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>int</code> 
      <code>temp = a[i];</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>a[i] = a[j];</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>a[j] = temp;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code>&nbsp; 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div>
       &nbsp; 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

所以在直接使用的时候避免了很多的重复代码：

补一张算法时间复杂度的图片

![844215-20161206180454804-829219313.png][]

[844215-20161206174728085-696577845.png]: /images/20220714/002c601723664304a8d45595432346fd.png
[844215-20161206175416366-1603841446.png]: /images/20220714/294cbe5a04954d94a2c885a54a49cd76.png
[844215-20161206180454804-829219313.png]: /images/20220714/83e31de367c3450f9712038c2208099b.png