排序 - [选择排序 - 堆排序]

逃离我推掉我的手 2022-01-12 11:53 413阅读 0赞

跟之前一样，我的文章力求通俗易懂。

今天讨论堆排序。

堆排序是选择排序的一种。堆排序大致分为两个步骤：

1. 构建初始堆 (大顶堆 或 小顶堆)；

2. 逐渐从堆中取出顶部元素，重新构造堆，然后再取出顶部元素，循环直到堆为空。

正式开始，首先我们来如何构建初始堆。因为堆是一个二叉树，为了更清楚的描述，在这篇文中我用了一些图片，希望能够讲清楚。

今天待排序的数组为：15, 19, 10, 7, 17, 6

我们用二叉树来表示这个数组，方法很简单，原则就是：

\* 给每个元素加上编号，比如编号为1的元素是 15，编号为2的元素是19，以此类推，给每个元素加上编号；

\* 1号元素为二叉树的根，他的左孩子是\#2 (左孩子位置：2 \* i)，右孩子是\#3 (右孩子位置：2 \* i + 1) ；

\* 2 号元素的左孩子是\#4, 右孩子是\#5；3号元素的左孩子是\#6, 右孩子是\#7，照这样的算法我们可以得到这样的二叉树：

![SouthEast][]

这个二叉树是未经排序的，在我们真正开始堆排序之前，这个应该是满足堆的要求的二叉树。

那么什么是堆呢? 什么又是大顶堆、小顶堆呢？

堆就是二叉树，每个节点是一个元素。

大顶堆就是每个节点的值都大于他的左右孩子的值；

小顶堆就是每个节点的值 小于 他的左右孩子的值。（个人见解，不保证一定准确，具体还劳烦大家google。）

那么如何将这个堆变成大顶堆呢？

我们从二叉树的“最右面”的元素开始调整。

什么是“最右面"？

最右面就是指：这个二叉树倒数第二层的最右面一个元素。

为什么从最右面开始呢？

因为最后一层所有的元素都是没有子节点的，那么也没有必要对没有子节点（或者说只有一个节点）的二叉树进行调整。

那么哪个元素是最右面的呢？很简单，就是size / 2。 对本例来说，元素个数为6. 6 / 2 = 3.

那么\#3元素就是最右面，也就是我们开始调整的地方。

从图上我们可以看到\#3元素是10. 如何调整呢？

因为我们要调整成一个大顶堆，那么调整的思想就是将这个元素的值 同 他的子节点进行比较，如果子节点中较大的值大于自己，那么交换他们。

对于我们的情况是这样的：

要比较的元素是10 和 16.

比较前：

![Image 1][]![L13ex-Fig02.jpg][]

交换后结果：

![L13ex-Fig03.jpg][]

![Image 1][]

从图中我们可以看到，16 大于10，我们对他们做了交换。

接下来我们要做调整的是2号元素：19，他的左右孩子分别为7 和 17，

因为 19 大于他的左右两个孩子，故对19这个节点，我们不需要改变二叉树的结构，故此时的结构不做改变。

为清楚起见，我们也将19比较的过程图画出来：

![L13ex-Fig04.jpg][]![Image 1][]

接下来要看的是1号元素，15.

我们拿1号元素的两个孩子：2号和3号跟1号元素比较，可以得到，2号元素19是最大的孩子。

故15应该跟19交换位置。

交换后：

![L13ex-Fig06.jpg][]

![Image 1][]

咦？图上有条虚线？

是的，因为19被调动了位置，那么7 和17的父节点也就改变了，此时需要对 15 --> (7, 17) 这棵二叉树进行重新调整。

同理，我们知道17是孩子中较大的值，所以我们将15跟17交换位置，交换后结果为：

![L13ex-Fig07.jpg][]

![Image 1][]

此时，这棵二叉树已经满足大顶堆的条件了，树上任意一棵二叉树都是 根节点的值大于左右孩子的值。

对了，忘了说了，图上左面是代表对树做调整时，数组的变化。

到此，我们完成了堆的初始化工作，接下里我们要对他进行排序了。

排序的思想就是逐渐把堆中最大的数字（就是堆顶的元素）跟数组”最后面"(最后面是指未经排序子数组的最后面)的元素进行调换，

然后再把被调换的元素放到堆顶，也就是树根位置，再重新调整为大顶堆，然后循环。

好了，开始排序啦。

![L13ex-Fig08.jpg][]

我们把19拿出来了，然后跟10进行交换位置：

![L13ex-Fig09.jpg][]

此时，我们需要再把10放到树根的位置，我们可以看到他的左右孩子分别为 17 和 16.

那么显然，17是较大的孩子，且17大于10，那么我们需要将17和10调换位置，我们得到：

![L13ex-Fig10.jpg][]

对于10这个元素，我们还没有调整完，因为当10和17对调后，10的左右孩子变为了7和15.

那么15又是左右孩子中较大的值，且他大于10，故我们仍然需要将10和15对调，我们得到：

![L13ex-Fig12.jpg][]

到此，元素 10 的调整已经完成，我们可以看到，原来的堆顶：19已经在数组的末尾了（我们认为19已经是有序的了）。

那么此时的堆顶是17。同理我们将17跟无序子数组的最后一个元素交换位置。最后一个元素是10，我们得到：

![L13ex-Fig14.jpg][]

同理啦，此时我们需要把10放到堆顶，再进行调整。

我们简单说下步骤吧：

\* 10放到堆顶；

\* 左右孩子分别为15,16，很明显16是较大的孩子，我们需要用他跟10进行交换。

那么我们得到：

![L13ex-Fig16.jpg][]

此时的堆顶元素是16.

继续，我们用16跟无序子数组的末位元素（7）交换，交换后状态如下：

![L13ex-Fig18.jpg][]

接下来：

\* 7放到堆顶，此时他的左右孩子分别为15和10；

\* 15为较大的元素，跟7交换位置，得到：

![L13ex-Fig20.jpg][]

此时堆顶为15，我们用15跟无序子数组的末位元素（10）交换，交换后状态如下：

![L13ex-Fig22.jpg][]

同理，此时10会处于堆顶位置，我们需要重新调整堆。

他的左右孩子。。。 哦，他只有左孩子没有右孩子，左孩子为7，7小于10，好的那么我们不需要调整，状态为：

![L13ex-Fig23.jpg][]

将10跟无序子数组的末位交换，我们得到：

![L13ex-Fig26.jpg][]

此时，因为二叉树中只有一个元素，那么我们认为他是有序的，不需要再调整，故最终结果为：

![L13ex-Fig27.jpg][]

java程序实现:

public class HeapSort {
    
      
      public static final int[] toSort = {5, 90, 12, 23, 1, 2, 66, 32}; 
          //{15, 19, 10, 7, 17, 16};
      
      public static int leftChild = 0;
      public static int rightChild = 0;
      public static int biggerChild = leftChild;
      
      
      public static int[] initHeap(int[] sort) {
        
        int rightMost = (sort.length - 1) / 2;
        
        
        for (int i = rightMost; i >=0; i--) {
          sortItem(sort, i, sort.length);
        }
    
        return sort;
      }
    
      private static void sortItem(int[] sort, int i, int limit) {
        
        // 确定要排序的元素的左右孩子的下标
        leftChild = 2 * i + 1;
        rightChild = leftChild + 1;
        
        if (leftChild < limit) {
          biggerChild = leftChild;
          
          if (rightChild < limit) {
            if (sort[rightChild] > sort[leftChild]) {
              biggerChild = rightChild;
            }
          }
    
          if (sort[i] < sort[biggerChild])
            swap(sort, i, biggerChild);
          
          sortItem(sort, biggerChild, limit);
        }
      }
      
      /**
       * 交换
       * @param sort
       * @param a
       * @param b
       */
      private static void swap(int[] sort, int a, int b) {
        int tmp = sort[a];
        sort[a] = sort[b];
        sort[b] = tmp;
      }
    
      /**
       * 堆排序
       * @param sort
       */
      public static void heapSort(int[] sort) {
        initHeap(sort);
        
        for (int i = 0; i < sort.length; i++) {
          // 将堆顶跟最后一个未排序的元素交换
          swap(sort, 0, sort.length - i - 1);
          
          percolate(sort, 0, sort.length - i - 1);
        }
      }
      
      /**
       * 将元素往下渗透
       * @param sort
       * @param i
       */
      private static void percolate(int[] sort, int i, int stopIndex) {
        sortItem(sort, i, stopIndex);
        
      }
    
      /**
       * @param args
       */
      public static void main(String[] args) {
    
        heapSort(toSort);
        
        for (int i : toSort) {
          System.out.print(i + ", ");
        }
      }
    
    }

这篇是不是长了点？

接下来我想讨论的是归并排序。

Good night.

[SouthEast]: /images/20220109/11607729b785426b85c897a3b3f676bb.png
[Image 1]: 
[L13ex-Fig02.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig02.jpg
[L13ex-Fig03.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig03.jpg
[L13ex-Fig04.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig04.jpg
[L13ex-Fig06.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig06.jpg
[L13ex-Fig07.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig07.jpg
[L13ex-Fig08.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig08.jpg
[L13ex-Fig09.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig09.jpg
[L13ex-Fig10.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig10.jpg
[L13ex-Fig12.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig12.jpg
[L13ex-Fig14.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig14.jpg
[L13ex-Fig16.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig16.jpg
[L13ex-Fig18.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig18.jpg
[L13ex-Fig20.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig20.jpg
[L13ex-Fig22.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig22.jpg
[L13ex-Fig23.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig23.jpg
[L13ex-Fig26.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig26.jpg
[L13ex-Fig27.jpg]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L13ex-Fig27.jpg