插入排序算法–直接插入算法，折半排序算法，希尔排序算法（C#实现） - Eric Sun - 博客园
Excerpt
插入排序算法主要分为：直接插入算法，折半排序算法（二分插入算法），希尔排序算法，后两种是直接插入算法的改良。因此直接插入算法是基础，这里先进行直接插入算法的分析与编码。直接插入算法的排序思想：假设有序数组从小到大为array[0],array[1],array[2],….,array[n-2],
插入排序算法主要分为：直接插入算法，折半排序算法（二分插入算法），希尔排序算法，后两种是直接插入算法的改良。因此直接插入算法是基础，这里先进行直接插入算法的分析与编码。
直接插入算法的排序思想：假设有序数组从小到大为array[0],array[1],array[2],….,array[n-2],array[n-1]，那么将待排数值array[n]与前面的有序数组从后向前依次比较，直到在有序数组中找到小于待排数值array[n]的位置，将array[n]插入到此位置，并入组合成新的有序数组。
直接插入算法--代码如下所示：
1 | <span> //</span><span>直接插入排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）</span><span><br></span><span> private </span><span>static </span><span>void</span><span> InsertSortionFunction(</span><span>int</span><span>[] array)<br> {<br> </span><span>try</span><span><br> {<br> </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>; </span><span>//</span><span>临时变量，存储待排的数值</span><span><br></span><span> for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>1</span><span>; i </span><span><</span><span> array.Length; i</span><span>++</span><span>) </span><span>//</span><span>将无序的所有数值依次插入到有序数组中，注：下标从1开始，因为操作的是同一个数组</span><span><br></span><span> {<br> temp </span><span>=</span><span> array[i]; </span><span>//</span><span>记录待插入前面有序数组的数值</span><span><br></span><span> int</span><span> index </span><span>=</span><span> i </span><span>-</span><span>1</span><span>; </span><span>//</span><span>记录前方有序数组的末尾位置</span><span><br></span><span> while</span><span> (index </span><span>>=</span><span>0</span><span>&&</span><span> array[index] </span><span>></span><span> temp) </span><span>//</span><span>循环遍历前面的有序数组，并且从大到小依次与待排数值进行比较</span><span><br></span><span> {<br> array[index </span><span>+</span><span>1</span><span>] </span><span>=</span><span> array[index]; </span><span>//</span><span>如果index>=0并且此时的值大于待排数值，将此处的值向后移动一位</span><span><br></span><span> index</span><span>--</span><span>; </span><span>//</span><span>index--向前遍历有序数组</span><span><br></span><span> }<br> array[index </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp; </span><span>//</span><span>由于前面的index--，所以temp插入的位置是index+1</span><span><br></span><span> }<br> }<br> </span><span>catch</span><span> (Exception ex)<br> { }<br> }</span> |
折半排序算法是对直接插入算法的一种优化，优化的核心是：通过折半查看有序数组中间位置的数值（a）与待插入的数值（temp）的大小，如果a>=temp，则转向折半的左区间继续折半查找； 如果a<temp，则转向折半后的右区间继续折半查找。直到左右下标相同时，此时折半的下标也指向相同的位置，再做最后一次循环，最终的结果是：左右下标相差1，并且原来左侧的下标指向大于temp的位置，原来右侧的下标指向了小于temp的位置，即：array[biggerIndex] < temp < array[smallerIndex]。
折半排序算法--代码如下：
1 | <span> </span><span>//</span><span>折半排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）</span> |
1 | <span> private </span><span>static </span><span>void</span><span> BinaryInsertionSortFunction(</span><span>int</span><span>[] array)<br> {<br> </span><span>try</span><span><br> {<br> </span><span>int</span><span> smallerIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录有序数组的起始位置</span><span><br></span><span> int</span><span> biggerIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录有序数组的终止位置</span><span><br></span><span> int</span><span> midIndex </span><span>=</span><span>0</span><span>; </span><span>//</span><span>记录获取有序数组的中间位置（折半法的关键：折半的位置）</span><span><br></span><span> int</span><span> temp; </span><span>//</span><span>记录带排的数值</span><span><br></span><span> for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>1</span><span>; i </span><span><</span><span> array.Length; i</span><span>++</span><span>) </span><span>//</span><span>循环向有序数组中插入数值（i从1开始，因为操作的是同一个数组）</span><span><br></span><span> {<br> temp </span><span>=</span><span> array[i]; </span><span>//</span><span>记录待插入有序数组的数值</span><span><br></span><span> biggerIndex </span><span>=</span><span> i </span><span>-</span><span>1</span><span>;<br> </span><span>//</span><span>当smallerIndex==biggerIndex时，进入最后一次循环：smallerIndex指向大于temp的数组位置，biggerIndex指向小于temp的数组位置</span><span><br></span><span> while</span><span> (smallerIndex </span><span><=</span><span> biggerIndex) <br> {<br> midIndex </span><span>=</span><span> (smallerIndex </span><span>+</span><span> biggerIndex) </span><span>/</span><span>2</span><span>; </span><span>//</span><span>确定折半的位置</span><span><br></span><span> if</span><span>(array[midIndex] </span><span>>=</span><span> temp) </span><span>//</span><span>折半位置的数值 >= temp</span><span><br></span><span> {<br> biggerIndex </span><span>=</span><span> midIndex </span><span>-</span><span>1</span><span>; </span><span>//</span><span>biggerIndex以midIndex为基础向前移动一位</span><span><br></span><span> }<br> </span><span>else</span><span><br> {<br> smallerIndex </span><span>=</span><span> midIndex </span><span>+</span><span>1</span><span>; </span><span>//</span><span>smallerIndex以midIndex为基础向后移动一位</span><span><br></span><span> }<br> }<br> </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span> i </span><span>-</span><span>1</span><span>; j </span><span>></span><span>biggerIndex; j</span><span>--</span><span>) </span><span>//</span><span>将有序数组中大于temp的数值分别向后移动一位</span><span><br></span><span> {<br> array[j </span><span>+</span><span>1</span><span>] </span><span>=</span><span> array[j]; </span><span>//<br></span><span> }<br> array[biggerIndex </span><span>+</span><span>1</span><span>] </span><span>=</span><span> temp; </span><span>//</span><span>将temp插入biggerIndex + 1，因为此时array[biggerIndex]<temp<array[smallerIndex]</span><span><br></span><span> }<br> }<br> </span><span>catch</span><span> (Exception ex)<br> { }<br> }</span> |
希尔排序同样是直接插入排序算法的一种改进，基本思想是：将无序的数列划分为若干小的子序列，然后对子序列进行直接插入排序。
时间性能优于直接插入排序算法，但是一种不稳定的排序，时间复杂度为O(nlogn)。
希尔排序算法主要分为3重循环：
第一重循环–>按照gap的大小进行分组，初始化从array.Length/2开始，依次递减到1
第二重循环–>对所有分组进行排序
第三重循环–>组内进行直接插入排序
希尔排序算法--代码如下：
1 | <span> private </span><span>static </span><span>void</span><span> ShellSortFunction(</span><span>int</span><span>[] array)<br> {<br> </span><span>try</span><span><br> {<br> </span><span>int</span><span> length </span><span>=</span><span> array.Length;<br> </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;<br> </span><span>for</span><span> (</span><span>int</span><span> gap </span><span>=</span><span> length </span><span>/</span><span>2</span><span>; gap </span><span>></span><span>0</span><span>; gap</span><span>--</span><span>) </span><span>//</span><span>第一重循环，按照gap的大小进行分组</span><span><br></span><span> {<br> </span><span>for</span><span> (</span><span>int</span><span> i </span><span>=</span><span>0</span><span>; i </span><span><</span><span> gap; i</span><span>++</span><span>) </span><span>//</span><span>第二重循环，对所有分组进行排序</span><span><br></span><span> {<br> </span><span>for</span><span> (</span><span>int</span><span> j </span><span>=</span><span> i; j </span><span><</span><span> length; j </span><span>=</span><span> j </span><span>+</span><span> gap) </span><span>//</span><span>第三重循环，组内进行直接插入排序</span><span><br></span><span> {<br> temp </span><span>=</span><span> array[j];<br> </span><span>int</span><span> index </span><span>=</span><span> j </span><span>-</span><span> gap;<br> </span><span>while</span><span> (index </span><span>>=</span><span>0</span><span>&&</span><span> array[index] </span><span>></span><span> temp)<br> {<br> array[index </span><span>+</span><span> gap] </span><span>=</span><span> array[index];<br> index </span><span>=</span><span> index </span><span>-</span><span> gap;<br> }<br> array[index </span><span>+</span><span> gap] </span><span>=</span><span> temp;<br> }<br> }<br> }<br> }<br> </span><span>catch</span><span> (Exception ex)<br> { }<br> }</span> |
。。。。
