堆排序，希尔排序解析

迷南。 2022-03-11 17:42 166阅读 0赞

// shell sort  
// 希尔排序  
void shell\_sort(int arr\[\], int SIZE)  
\{

int i, j, hCnt, h;  
 int increments\[20\], k;

// h： increment         
 // set increments   设置增量个数和值  
 for (h = 1, i = 0; h < SIZE; ++i)                   // <1>  
 \{  
  increments\[i\] = h;  
  h = 3\*h + 1;  
 \}  
// \{12, 34, 4, 3, 18, 7, 41, 27, 23, 35\}  
 for ( i--; i >= 0; --i)                           // <2>  
 \{  
  h = increments\[i\];

for (hCnt = h; hCnt < 2 \* h; ++hCnt)           //<3>  
  \{  
   for (j = hCnt; j < SIZE;j += h)                //<4>  
   \{  
    int temp = arr\[j\];  
    k = j;  
    while (k - h >= 0 && temp < arr\[k - h\])  
    \{  
     arr\[k\] = arr\[k - h\];  
     k = k - h;  
    \}  
    arr\[k\] = temp;  
   \}  
  \}  
 \}  
\}  
/\*  
希尔排序原理：把数组桥面的分割为几个子数组。从原始数组中每隔h个元素挑选一个元素作为一个子数组的一部分。这样分为若干个数组  
，对每个字数组排序。然后降低增量值，继续选取数组，继续排序，最后一次排序的增量是1。

简单的说，希尔排序的算法是这样的：  
==============================================  
确定把数组data分割成子数组的数h\[t\]...h\[1\]               <1>  
 for(h = h\[t\]; t >= 1; t--, h = h\[t\])                 <2>  
  将数组data分成h个子数组                           <3>  
  for(i = 1; i <=h; ++i)                           <4>  
   对子数组data\[i\]排序                           
排序数组data  
=============================================

分析上面的程序，  
<1>  
求出了增量的个数和要用的增量值，并储存在数组increments中，在此求增量的算法用的是  
h\[1\] = 1;  
h\[i+1\] = 3 \* h\[i\] + 1;

<2>  
然后用增量的个数i做循环控制变量，i取值范围i--~0.

<3>  
下面从最大的增量开始进行分割数组,并带入增量值h = increments\[i\]。  
例如，当增量h = 4时，实质上是把数组data分割为4个子数组，每隔4个元素取一个值作为子数组的一部分。

子数组的排序用hCnt做控制变量，因为数组的间隔就是增量h，所以取值范围是 h ~ 2 \* h。这里0~h和从h~2\*h的循环效果，但是下面的  
插入排序一般用到的是数组的第二个元素（data\[1\],而非data\[0\]），也就是代码中的j。  
  for (hCnt = h; 。。。。。。。。。)  
   for (j = hCnt; j < SIZE;j += h)  
   。。。  
可能这也是代码中的hCnt的取值范围用 h ~ 2 \* h的原因吧

<4>  
代码实现的是对子数组的排序，上述代码中用到的是插入排序。在此不再祥述。（参考《排序之3种基本排序》）  
\--------------------------------------------------------  
解析中说的很散乱，是因为原理和伪代码已经能说明出基本问题。解析的目的只是针对代码做一个注释罢了。

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

//heap sort  
// 堆排序  
// \{12, 34, 4, 3, 18, 7, 41, 27, 23, 35\}  
void heap\_sort(int arr\[\], int SIZE)             
\{

// 把数组转化为堆  
 for (int i = SIZE/2 - 1; i >= 0; --i)        <2>  
  moveDown(arr, i, SIZE - 1);

for (int i = SIZE - 1; i >= 0; --i)          <3>  
 \{  
  swap(arr\[0\], arr\[i\]);  // move the largest item to arr\[i\]  
  moveDown(arr, 0, i - 1); // restore the heap property  
 \}  
\}

堆排序原理：使用选择排序固有的方法，选择排序是首先在n个元素中找出小于其他n-1个元素的的元素，再在n-1个数据项中找出最小数据项。而堆排序是通过创建堆，然后将最大的元素放在数组末尾，然后紧接着将第二大的元素放在最大元素前面的位置，依次类推，直到排序结束。

代码分析：  
 <2> 把数组转化为堆。因为叶子节点的计算公式是2\*node +1，i取size/2 -1就是是要取最后一个不是叶子节点的元素。这个时候moveDown（）函数从底部开始创建堆。并时刻把最大的元素放在堆顶部。循环结束，堆也创建起来了。  
 <3> 这段代码是在堆创建好了之后进行排序的。像悬在排序一样，把堆顶部的元素（也是最大的数）放到数组最后的位置，也就是堆最后的位置。然后通过moveDown（。。；i-1）把剩余元素的最大值放到顶部。下次循环的时候继续把这个第二大元素放到最大元素的前面。一直到排序结束。

// 将根元素沿着树向下移动  
void moveDown(int data\[\], int first, int last)     
\{  
 int largest = 2 \* first + 1;                        <2>  
 while (largest <= last)               <3>  
 \{

if (largest < last && data\[largest\] < data\[largest + 1\])  <4>  
   largest++;

if (data\[first\] < data\[largest\])                    <5>  
  \{  
   swap(data\[first\], data\[largest\]);  
   first = largest;     //换根元素  
   largest = 2 \* first;  
  \}  
  else  
   largest = last + 1;                              <6>  
 \}  
\}

代码分析：  
 函数moveDown（）是将根元素沿着树向下移动的实现代码。参数data\[\]是要操作的数组，first是根元素,last是最后一个元素  
<2> largest是根元素的左孩子，数组从0开始，所以根元素的左右孩子是 2\*first+1和 2\*first+2;  
<3> largest <= last 是为了确保largest是堆中的一个元素，如果是就进行根元素下移的操作。  
<4> 从first的左右两个孩子中找到最大的那个元素，并将元素索引赋值给largest。测试largest < last是为了确保first是有左右两个孩子，本身largest是左孩子，如果他是最后一个元素（largest == last）的话那么就没法进行从上述的操作。  
<5> 交换动作。如果first元素小于孩子，则将他们交换。然后继续将first为子树的根元素，重新设置largest，进行下次下移动作  
<6> 如果first元素的值大于孩子largest的值，将largest设置为堆的范围之外是为了保持堆结构，并退出循环。