Chemmy's Blog

chengming0916@gmail.com

0%

发表于 分类于 ， Valine：

堆排序算法（C#实现）

Excerpt

在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。另一种是垃圾收集存储区，是软件系统可以编程的内存区域。本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例堆排序的时间复杂度是O(nlog2n),与快速

在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面：

一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。

另一种是垃圾收集存储区，是软件系统可以编程的内存区域。

本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例

堆排序的时间复杂度是O(nlog2n),与快速排序达到相同的时间复杂度. 但是在实际应用中,我们往往采用快速排序而不是堆排序. 这是因为快速排序的一个好的实现,往往比堆排序具有更好的表现. 堆排序的主要用途,是在形成和处理优先级队列方面. 另外, 如果计算要求是类优先级队列(比如, 只要返回最大或者最小元素, 只有有限的插入要求等), 堆同样是很适合的数据结构.

**堆排序
**堆排序是一种选择排序。是不稳定的排序方法。时间复杂度为O(nlog2n)。
堆排序的特点是：在排序过程中，将排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。

基本思想
1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。

大根堆和小根堆
堆：是一颗完全二叉树。
大根堆：所有节点的子节点比其自身小的堆
小根堆：所有节点的子节点比其自身大的堆

堆与数组的关系

堆是一种逻辑结构（形象的表示数据的存储格式），数组则是数据的实际存储结构（对应数据的存储地址），堆中的根节点与左右子节点在存储数组中的位置关系如下：假设根节点在数组中的位置（数组下标）为 i ，那么左节点在数组中的位置（数组下标）为 i * 2 + 1 ， 右节点在数组中的位置（数组下标）为 i * 2 + 2 。

以上是基本的知识点，具体代码如下所示：

1
<span>        //</span><span>堆排序算法（传递待排数组名，即：数组的地址。故形参数组的各种操作反应到实参数组上）</span><span><br></span><span>　　　　 private </span><span>static </span><span>void</span><span> HeapSortFunction(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                BuildMaxHeap(array);    </span><span>//</span><span>创建大顶推（初始状态看做：整体无序）</span><span><br></span><span>　　　　　　　　　for</span><span> (</span><span>int</span><span> i </span><span>=</span><span> array.Length </span><span>-</span><span>1</span><span>; i </span><span>&gt;</span><span>0</span><span>; i</span><span>--</span><span>)<br>                {<br>                    Swap(</span><span>ref</span><span> array[</span><span>0</span><span>], </span><span>ref</span><span> array[i]); </span><span>//</span><span>将堆顶元素依次与无序区的最后一位交换（使堆顶元素进入有序区）</span><span><br></span><span>                    MaxHeapify(array, </span><span>0</span><span>, i); </span><span>//</span><span>重新将无序区调整为大顶堆</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }<br><br>        </span><span>///</span><span>&lt;summary&gt;</span><span><br>        </span><span>///</span><span> 创建大顶推（根节点大于左右子节点）<br>        </span><span>///</span><span>&lt;/summary&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="array"&gt;</span><span>待排数组</span><span>&lt;/param&gt;</span><span><br></span><span>　　　　 private </span><span>static </span><span>void</span><span> BuildMaxHeap(</span><span>int</span><span>[] array)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>//</span><span>根据大顶堆的性质可知：数组的前半段的元素为根节点，其余元素都为叶节点</span><span><br></span><span>　　　　　　　　　for</span><span> (</span><span>int</span><span> i </span><span>=</span><span> array.Length </span><span>/</span><span>2</span><span>-</span><span>1</span><span>; i </span><span>&gt;=</span><span>0</span><span>; i</span><span>--</span><span>) </span><span>//</span><span>从最底层的最后一个根节点开始进行大顶推的调整</span><span><br></span><span>                {<br>                    MaxHeapify(array, i, array.Length); </span><span>//</span><span>调整大顶堆</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }<br><br>        </span><span>///</span><span>&lt;summary&gt;</span><span><br>        </span><span>///</span><span> 大顶推的调整过程<br>        </span><span>///</span><span>&lt;/summary&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="array"&gt;</span><span>待调整的数组</span><span>&lt;/param&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="currentIndex"&gt;</span><span>待调整元素在数组中的位置（即：根节点）</span><span>&lt;/param&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="heapSize"&gt;</span><span>堆中所有元素的个数</span><span>&lt;/param&gt;</span><span><br></span><span>　　　　 private </span><span>static </span><span>void</span><span> MaxHeapify(</span><span>int</span><span>[] array, </span><span>int</span><span> currentIndex, </span><span>int</span><span> heapSize)<br>        {<br>            </span><span>try</span><span><br>            {<br>                </span><span>int</span><span> left </span><span>=</span><span>2</span><span>*</span><span> currentIndex </span><span>+</span><span>1</span><span>;    </span><span>//</span><span>左子节点在数组中的位置</span><span><br></span><span>　　　　　　　　　int</span><span> right </span><span>=</span><span>2</span><span>*</span><span> currentIndex </span><span>+</span><span>2</span><span>;   </span><span>//</span><span>右子节点在数组中的位置</span><span><br></span><span>　　　　　　　　　int</span><span> large </span><span>=</span><span> currentIndex;   </span><span>//</span><span>记录此根节点、左子节点、右子节点 三者中最大值的位置</span><span><br></span><span><br>                </span><span>if</span><span> (left </span><span>&lt;</span><span> heapSize </span><span>&amp;&amp;</span><span> array[left] </span><span>&gt;</span><span> array[large])  </span><span>//</span><span>与左子节点进行比较</span><span><br></span><span>                {<br>                    large </span><span>=</span><span> left;<br>                }<br>                </span><span>if</span><span> (right </span><span>&lt;</span><span> heapSize </span><span>&amp;&amp;</span><span> array[right] </span><span>&gt;</span><span> array[large])    </span><span>//</span><span>与右子节点进行比较</span><span><br></span><span>                {<br>                    large </span><span>=</span><span> right;<br>                }<br>                </span><span>if</span><span> (currentIndex </span><span>!=</span><span> large)  </span><span>//</span><span>如果 currentIndex != large 则表明 large 发生变化（即：左右子节点中有大于根节点的情况）</span><span><br></span><span>                {<br>                    Swap(</span><span>ref</span><span> array[currentIndex], </span><span>ref</span><span> array[large]);    </span><span>//</span><span>将左右节点中的大者与根节点进行交换（即：实现局部大顶堆）</span><span><br></span><span>                    MaxHeapify(array, large, heapSize); </span><span>//</span><span>以上次调整动作的large位置（为此次调整的根节点位置），进行递归调整</span><span><br></span><span>                }<br>            }<br>            </span><span>catch</span><span> (Exception ex)<br>            { }<br>        }<br><br>        </span><span>///</span><span>&lt;summary&gt;</span><span><br>        </span><span>///</span><span> 交换函数<br>        </span><span>///</span><span>&lt;/summary&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="a"&gt;</span><span>元素a</span><span>&lt;/param&gt;</span><span><br>        </span><span>///</span><span>&lt;param name="b"&gt;</span><span>元素b</span><span>&lt;/param&gt;</span><span><br></span><span>　　　　　private </span><span>static </span><span>void</span><span> Swap(</span><span>ref</span><span>int</span><span> a, </span><span>ref</span><span>int</span><span> b)<br>        {<br>            </span><span>int</span><span> temp </span><span>=</span><span>0</span><span>;<br>            temp </span><span>=</span><span> a;<br>            a </span><span>=</span><span> b;<br>            b </span><span>=</span><span> temp;<br>        }</span>

发表于 分类于 ， Valine：

归并排序算法（C#实现）

Excerpt

自顶向下的归并排序：是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：1）划分子表 2）合并半子表

     归并排序(Merge Sort)是利用”归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。归并排序有两种方式：1): 自底向上的方法 2):自顶向下的方法

 1、 自底向上的方法
（1） 自底向上的基本思想
     自底向上的基本思想是：第1趟归并排序时，将待排序的文件R[1..n]看作是n个长度为1的有序子文件，将这些子文件两两归并，若n为偶数，则得到n/2个长度为2的有序子文件；若n为奇数，则最后一个子文件轮空(不参与归并)。故本趟归并完成后，前n/2 - 1个有序子文件长度为2，但最后一个子文件长度仍为1；第2趟归并则是将第1趟归并所得到的n/2个有序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止。
     上述的每次归并操作，均是将两个有序的子文件合并成一个有序的子文件，故称其为”二路归并排序”。类似地有k(k>2)路归并排序。   

2、自顶向下的方法(本文主要介绍此种方法，下面的文字都是对此种方法的解读)

（1） 自顶向下的基本思想
     采用分治法进行自顶向下的算法设计，形式更为简洁。
     自顶向下的归并排序：是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：

      1）划分子表

      2）合并半子表

（1）分治法的三个步骤
     设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
①分解：将当前区间一分为二，即求分裂点
②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
  递归的终结条件：子区间长度为1（一个记录自然有序）。

如下演示递归的整个过程：

递归便是深度遍历（如下由左至右进行遍历）：假设有这样的一列数组{9,8,7,6,5,4,3,2,1}进行划分的顺序如下：

{9,8,7,6,5,4,3,2,1} –> {9,8,7,6,5}，{4,3,2,1}

{9,8,7,6,5} –> {9,8,7}，{6,5}

                        {9,8,7} –> {9,8}，{7}

                                          {9,8} –> {9}，{8}

                        {6,5} –>{6}，{5}

{4,3,2,1} –> {4,3}，{2,1}

                      {4,3} –>{4}，{3}

                      {2,1} –>{2}，{1}

当深度划分到左右数组都只剩1个元素的时候，进行上述逆序的合并：

{9}，{8} –> {8,9} 然后和 {7} –> {7,8,9}

                                {6}，{5} –> {5,6}    然后 {7,8,9}和{5,6} –> {5,6,7,8,9}

                                     {2}，{1} –> {1,2}

                                     {4}，{3} –> {3,4}   然后 {1,2}和 {3,4} –> {1,2,3,4}

                                                                                                                         最终{5,6,7,8,9}和{1,2,3,4} –> {1,2,3,4,5,6,7,8,9}

具体实现代码如下所示：

1
<span>//</span><span>归并排序（目标数组，子表的起始位置，子表的终止位置）</span><span><br></span>        <span>private</span> <span>static</span> <span>void</span> MergeSortFunction(<span>int</span>[] array, <span>int</span> first, <span>int</span> last)<br>        {<br>            <span>try</span><br>            {<br>                <span>if</span> (first &lt; last)   <span>//</span><span>子表的长度大于1，则进入下面的递归处理</span><span><br></span>                {<br>                    <span>int</span> mid = (first + last) / <span>2</span>;   <span>//</span><span>子表划分的位置</span><span><br></span>                    MergeSortFunction(array, first, mid);   <span>//</span><span>对划分出来的左侧子表进行递归划分</span><span><br></span>                    MergeSortFunction(array, mid + <span>1</span>, last);    <span>//</span><span>对划分出来的右侧子表进行递归划分</span><span><br></span>                    MergeSortCore(array, first, mid, last); <span>//</span><span>对左右子表进行有序的整合（归并排序的核心部分）</span><span><br></span>                }<br>            }<br>            <span>catch</span> (Exception ex)<br>            { }<br>        }<br><br>        <span>//</span><span>归并排序的核心部分：将两个有序的左右子表（以mid区分），合并成一个有序的表</span><span><br></span>        <span>private</span> <span>static</span> <span>void</span> MergeSortCore(<span>int</span>[] array, <span>int</span> first, <span>int</span> mid, <span>int</span> last)<br>        {<br>            <span>try</span><br>            {<br>                <span>int</span> indexA = first; <span>//</span><span>左侧子表的起始位置</span><span><br></span>                <span>int</span> indexB = mid + <span>1</span>;   <span>//</span><span>右侧子表的起始位置</span><span><br></span>                <span>int</span>[] temp = <span>new</span> <span>int</span>[last + <span>1</span>]; <span>//</span><span>声明数组（暂存左右子表的所有有序数列）：长度等于左右子表的长度之和。</span><span><br></span>                <span>int</span> tempIndex = <span>0</span>;<br>                <span>while</span> (indexA &lt;= mid &amp;&amp; indexB &lt;= last) <span>//</span><span>进行左右子表的遍历，如果其中有一个子表遍历完，则跳出循环</span><span><br></span>                {<br>                    <span>if</span> (array[indexA] &lt;= array[indexB]) <span>//</span><span>此时左子表的数 &lt;= 右子表的数</span><span><br></span>                    {<br>                        temp[tempIndex++] = array[indexA++];    <span>//</span><span>将左子表的数放入暂存数组中，遍历左子表下标++</span><span><br></span>                    }<br>                    <span>else</span><span>//</span><span>此时左子表的数 &gt; 右子表的数</span><span><br></span>                    {<br>                        temp[tempIndex++] = array[indexB++];    <span>//</span><span>将右子表的数放入暂存数组中，遍历右子表下标++</span><span><br></span>                    }<br>                }<br>                <span>//</span><span>有一侧子表遍历完后，跳出循环，将另外一侧子表剩下的数一次放入暂存数组中（有序）</span><span><br></span>                <span>while</span> (indexA &lt;= mid)<br>                {<br>                    temp[tempIndex++] = array[indexA++];<br>                }<br>                <span>while</span> (indexB &lt;= last)<br>                {<br>                    temp[tempIndex++] = array[indexB++];<br>                }<br><br>                <span>//</span><span>将暂存数组中有序的数列写入目标数组的制定位置，使进行归并的数组段有序</span><span><br></span>                tempIndex = <span>0</span>;<br>                <span>for</span> (<span>int</span> i = first; i &lt;= last; i++)<br>                {<br>                    array[i] = temp[tempIndex++];<br>                }<br>            }<br>            <span>catch</span> (Exception ex)<br>            { }<br>        }

       对于N个元素的数组来说, 如此划分需要的层数是以2为底N的对数, 每一层中, 每一个元素都要复制到结果数组中, 并复制回来, 所以复制2N次, 那么对于归并排序,它的时间复杂度为O(N*logN), 而比较次数会少得多, 最少需要N/2次,最多为N-1次, 所以平均比较次数在两者之间. 它的主要问题还是在于在内存中需要双倍的空间.

发表于 分类于 ， Valine：

插入排序算法C#实现

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>&lt;</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>&gt;=</span><span>0</span><span>&amp;&amp;</span><span> array[index] </span><span>&gt;</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&gt;=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>  &nbsp;　　　</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>&lt;</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>&lt;=</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>&gt;=</span><span> temp)  </span><span>//</span><span>折半位置的数值 &gt;= 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>&gt;</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]&lt;temp&lt;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>&gt;</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>&lt;</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>&lt;</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>&gt;=</span><span>0</span><span>&amp;&amp;</span><span> array[index] </span><span>&gt;</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>

。。。。

发表于 分类于 ， Valine：

C#排序算法的比较

首先通过图表比较不同排序算法的时间复杂度和稳定性。

排序方法

平均时间

最坏情况

最好情况

辅助空间

稳定性

直接插入排序

O(n2)

O(n2)

O(n)

O(1)

是
冒泡排序

O(n2)

O(n2)

O(n)

O(1)

是
简单选择排序

O(n2)

O(n2)

O(n2)

O(1)

是
希尔排序-

O(nlog2n)~O(n2)

O(nlog2n)~O(n2)

O(1)

否
快速排序

O(nlog2n)

O(n2)

O(nlog2n)

O(log2n)

否
堆排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(1)

否
2-路归并排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(n)

是
基数排序O(d(n + rd))O(d(n + rd))O(d(n + rd))O(rd)是

注：1. 算法的时间复杂度一般情况下指最坏情况下的渐近时间复杂度。

        2. 排序算法的稳定性会对多关键字排序产生影响。

下面通过C#代码说明不同的排序算法

插入排序

时间复杂度：平均情况—O(n2) 最坏情况—O(n2) 辅助空间：O(1) 稳定性：稳定

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

希尔排序(shell)

时间复杂度：理想情况—O(nlog2n) 最坏情况—O(n2) 稳定性：不稳定

希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

冒泡排序

时间复杂度：平均情况—O(n2) 最坏情况—O(n2) 辅助空间：O(1) 稳定性：稳定

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

快速排序

时间复杂度：平均情况—O(nlog2n) 最坏情况—O(n2) 辅助空间：O(log2n) 稳定性：不稳定

快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。

选择排序

时间复杂度：平均情况—O(n2) 最坏情况—O(n2) 辅助空间：O(1) 稳定性：不稳定

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

堆排序

时间复杂度：平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间：O(1) 稳定性：不稳定

我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, …1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法

归并排序

时间复杂度：平均情况—O(nlog2n) 最坏情况—O(nlog2n) 辅助空间：O(n) 稳定性：稳定

归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。

发表于 Valine：
消息格式

每个提交消息都由一个标题、一个正文和一个页脚组成。而标题又具有特殊格式，包括修改类型、影响范围和内容主题：

1
2
3
4
5
修改类型(影响范围): 标题
<--空行-->
[正文]
<--空行-->
[页脚]

标题是强制性的，但标题的范围是可选的。

修改类型

每个类型值都表示了不同的含义，类型值必须是以下的其中一个：

  • feat：提交新功能
  • fix：修复了bug
  • docs：只修改了文档
  • style：调整代码格式，未修改代码逻辑（比如修改空格、格式化、缺少分号等）
  • refactor：代码重构，既没修复bug也没有添加新功能
  • perf：性能优化，提高性能的代码更改
  • test：添加或修改代码测试
  • chore：对构建流程或辅助工具和依赖库（如文档生成等）的更改
代码回滚

代码回滚比较特殊，如果本次提交是为了恢复到之前的某个提交，那提交消息应该以“revert:”开头，后跟要恢复到的那个提交的标题。然后在消息正文中，应该写上“This reverts commit ”，其中“”是要还原的那个提交的SHA值。

影响范围

范围不是固定值，它可以是你提交代码实际影响到的任何内容。例如$location、$browser、$compile、$rootScope、ngHref、ngClick、ngView等，唯一需要注意的是它必须足够简短。

当修改影响多个范围时，也可以使用“*”。

标题

标题是对变更的简明描述：

  • 使用祈使句，现在时态：是“change”不是“changed”也不是“changes”
  • 不要大写首字母
  • 结尾不要使用句号
正文

正文是对标题的补充，但它不是必须的。和标题一样，它也要求使用祈使句且现在时态，正文应该包含更详细的信息，如代码修改的动机，与修改前的代码对比等。

页脚

任何Breaking Changes（破坏性变更，不向下兼容）都应该在页脚中进行说明，它经常也用来引用本次提交解决的GitHub Issue。

Breaking Changes应该以“BREAKING CHANGE:”开头，然后紧跟一个空格或两个换行符，其他要求与前面一致。

智能校园安全物联平台(Intelligent campus security IoT platform)

分支功能描述

master: 长期分支，用于对外版本发布，所有版本出自此版本库。此分支不允许直接提交代码，只从bugfix分支和develop分支合并。

develop: 长期分支，用于日常代码开发，与master分支 保持同步，当新功能开发完成后线合并到此分支，经过测试后再合并到master分支。

bugfix: 临时分支，当出现bug时基于master分支新建bugfix/bug-1,bug分支可根据bug编号命名。bug测试完毕合并进入develop分支和master分支

feature: 临时分支，开发新功能时从develop分支新建feature/feature-1,feature分支可根据功能命名。新特性开发完成合并进入develop分支并删除feature分支。

release: 临时分支，需要发布版本时从master分支新建release/release-1.0.0,release分支根据版本号命名。

release分支禁止再合并功能，只提交bug修改，版本发布完成后合并进入master和develop，并再对应的提交上打版本Tag。

提交规范

参考格式

1
2
3
4
5
<type>: <subject>
<BLANK LINE> 空行
<body>
<BLANK LINE> 空行
<footer>

  • type: 本次commit的类型，如bugfix,docs,style等

  • feat: 添加新特性

  • fix: 修复bug

  • docs: 修改文档

  • style: 修改格式缩进,不改变代码逻辑

  • refactor: 代码重构,没有添加新下功能或者修复bug

  • perf: 增加代码进行性能测试

  • test: 增加测试用例

  • chore: 改变构建流程或者增加依赖库、工具等

  • scope: 本次commit波及范围

  • subject: 简明扼要阐述本次commit的主旨

    • 使用祈使句
    • 首字母不要大写
    • 结尾无需添加标点

  • body: 详细描述本次commit,如需换行则使用|

  • footer: 描述下与之关联的 issue 或 breadk change

标题行： 50个字符以内，描述主要变更内容

主体内容: 更详细下说明文本，建议72个字符以内。需要描述信息包括：

  • 为什么这个变更是必须的，它可能是用来修复一个bug，增加一个feature,提升性能、可靠性、稳定性等
  • 如何解决这个问题，具体描述解决问题的步骤
  • 是否存在副作用、风险

如果需要的话可以添加一个连接到issue或其他文档

示例

1
2
3
4
5
6
7
8
9
10
11
12
docs(README): README添加代码提交规范

添加代码规范，提升提交日志的可读性和功能

#123 #没有关联的issue可以省略

----------------------
feat: 增加XXX功能

增加XXX功能，实现XXX效果

#21

发表于 更新于 Valine：

.NET 出到 6 之后，原本官方的 [SPA 套件]被弃用(https://github.com/dotnet/aspnetcore/issues/12890)，新版改成使用 Vue-CLI + SPA Proxy。

环境

1
2
3
4
5
# 确认.NET版本,此处为 6.0.200
dotnet --version

# 确认Node版本,此处为 v16.4.0
node --version

新建.NET项目

1
2
# 新建react模板项目
dotnet new react

前端文件放在ClientApp目录,清空此目录下所有文件并使用Vue-CLI新建Vue项目并修改对应参数即可

新建Vue项目

1
2
3
4
5
6
7
8
9
10
11
# 安装Vue CLI, 此处使用版本 v5.0.1
npm install -g @vue/cli

# Vue CLI 不允许大写字母，此处使用 client-app作为项目名
vue create client-app

# 安装依赖
npm install

# 运行测试
npm run dev

配置

打开项目.csproj文件,修改SpaRoot节点值为client-app所在目录，并注意这里的SpaProxyServerUrl 节点的值是前端的访问地址，SpaProxyLaunchCommand是npm start是前端的启动命令。

[^注意]若SpaProxyServerUrl是HTTPS需要改成http。
[^注意]每次新建.NET项目时对应的端口都不一样，前端需要改成对应的端口。

1
2
3
4
5
6
7
8
9
...
<PropertyGroup>
  ...
  <SpaRoot>client-app\</SpaRoot>
  <SpaProxyServerUrl>http://localhost:44405</SpaProxyServerUrl>
  <SpaProxyLaunchCommand>npm start</SpaProxyLaunchCommand>
  ...
</PropertyGroup>
...

修改package.json,在scripts中添加启动命令

1
2
3
4
5
"scripts": {
  "start": "vue-cli-service serve",
  "build": "vue-cli-service build",
  "lint": "vue-cli-service lint"
}

修改vue.config.js,将devServer port换成44405。

1
2
3
4
5
6
7
8
9
const { defineConfig }  = require('@vue/cli-service')
module.exports = defineConfig({
  devServer: {
    port: 44405,
  },
  transplieDependencies: [
    'vuetify'
  ]
})

发表于 更新于 Valine：

默认配置

默认安装路径：%AppData%\Roaming\npm
全局缓存路径：%AppData%\Roaming\npm_cache

安装全局包命令: npm install -g <包名>

修改方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 设置全局包安装路径
npm config set prefix "<目标路径>"

# 修改缓存包安装路径
npm config set cache "<目标路径>"

# 查看全局包安装路径
npm config get prefix 

# 查看缓存包安装路径
npm config get cache 

# 查看所有配置
npm config ls

添加环境变量

1
NODE_PATH="<全局安装包路径>\node_modules\"

发表于 更新于 Valine：

npm镜像源地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 官方源
https://registry.npmjs.org

# 淘宝npm镜像
https://registry.npmmirror.com

# 阿里云npm镜像
https://npm.aliyun.com

# 腾讯云npm镜像
https://mirrors.cloud.tencent.com/npm

# 华为云npm镜像
https://mirrors.huaweicloud.com/repository/npm

# 网易npm镜像
https:/mirrors.163.com/npm

修改镜像源

1
2
3
4
5
# 修改镜像源
npm config set registry https://registry.npmmirror.org

# 查看镜像源
npm config get registry

发表于 更新于 Valine： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
sudo vim /etc/sysctl.d/99-sysctl.conf：     #重启后生效
fs.inotify.max_user_watches = 600000
dev.i915.perf_stream_paranoid = 0
vm.swappiness = 1
net.ipv6.conf.all.accept_ra = 2
fs.file-max = 6553560
net.core.rmem_max = 67108864
net.core.wmem_max = 67108864
net.core.rmem_default = 65536
net.core.wmem_default = 65536
net.core.optmem_max = 10000000
net.core.netdev_max_backlog = 8096
net.core.somaxconn = 8096
net.ipv4.ip_default_ttl = 128
net.ipv4.tcp_timestamps = 1
net.ipv4.tcp_syncookies = 1
net.ipv4.icmp_echo_ignore_broadcasts = 1
net.ipv4.icmp_ignore_bogus_error_responses = 1
net.ipv4.conf.default.accept_source_route = 0
net.ipv4.tcp_slow_start_after_idle = 0
net.ipv4.route.gc_timeout = 100
net.ipv4.tcp_tw_reuse = 1
net.ipv4.tcp_tw_recycle = 1
net.ipv4.tcp_fin_timeout = 30
net.ipv4.tcp_keepalive_time = 1200
net.ipv4.tcp_keepalive_probes = 3
net.ipv4.tcp_keepalive_intvl = 15
net.ipv4.tcp_fin_timeout = 30
net.ipv4.tcp_syn_retries = 2
net.ipv4.tcp_synack_retries = 2
net.ipv4.tcp_window_scaling = 1
net.ipv4.tcp_ecn = 1
net.ipv4.tcp_sack = 1
net.ipv4.tcp_fack = 1
net.ipv4.tcp_low_latency = 0
net.ipv4.tcp_max_tw_buckets = 5000
net.ipv4.tcp_fastopen = 3
net.ipv4.tcp_frto = 2
net.ipv4.tcp_frto_response = 0
net.ipv4.tcp_rmem = 4096 87380 67108864
net.ipv4.tcp_wmem = 4096 65536 67108864
net.ipv4.tcp_mtu_probing = 1
net.ipv4.tcp_slow_start_after_idle = 0
net.ipv4.tcp_max_syn_backlog = 30000
net.ipv4.tcp_max_orphans = 262114
net.ipv4.netfilter.ip_conntrack_max = 204800
net.ipv4.conf.all.rp_filter = 1
net.ipv4.conf.default.rp_filter = 1
# for high-latency network Google BBR    #个人PC不建议开启BBR，对网速不会有提升，还会降低wifi吞吐量；还是等BBR2正式版出了再开启BBR2吧，BBR2对wifi就没有影响了
#net.ipv4.tcp_congestion_control = bbr
net.core.default_qdisc = fq_codel
net.ipv4.tcp_congestion_control = cubic
net.ipv6.conf.all.disable_ipv6 = 0
net.ipv6.conf.default.disable_ipv6 = 0
net.ipv6.conf.lo.disable_ipv6 = 0
net.ipv6.ip_default_ttl = 128
1
2
3
4
5
sudo vim /etc/security/limits.conf：
* soft nofile 65536
* hard nofile 65536
* soft noproc 65536 
* hard noproc 65536