您的位置: 首页  >  文章  >  Java--常见排序算法

Java--常见排序算法

分类: 文章 • 2024-01-05 21:52:10

前言    堆排序 (Heap Sort)

      最近遇到一个求解Top N的场景，从1亿条数据中，找出最大或者最小的10个数。 怎么办？不可能对数据进行全排序吧，哪里有那么大的内存空间！谷歌搜索了相关的解决方案，最终定位在使用堆排序解决这个问题。

摘要

     1、什么是二叉树？

     2、什么是堆？

     3、堆排序原理？

     4、堆排序的Java实现。

     5、堆排序的Scala实现。

主要内容

   一、什么是二叉树

     参考：https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91

      要了解堆首先需要了解下二叉树（英语：Binary tree），在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树（不存在度大于 2 的结点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第 i 层至多有 2i - 1 个结点；深度为 k 的二叉树至多有 2k - 1 个结点；对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则n0 = n2 + 1。

树和二叉树的三个主要差别：

  • 树的结点个数至少为 1，而二叉树的结点个数可以为 0
  • 树中结点的最大度数没有限制，而二叉树结点的最大度数为 2
  • 树的结点无左、右之分，而二叉树的结点有左、右之分

二叉树又分为完全二叉树（complete binary tree）和满二叉树（full binary tree）

(1)满二叉树：一棵深度为 k，且有 2k - 1 个节点称之为满二叉树

Java--常见排序算法

深度为 3 的满二叉树 full binary tree。

(2)完全二叉树：深度为 k，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至 n 的节点对应时，称之为完全二叉树

Java--常见排序算法

深度为 3 的完全二叉树 complete binary tree


二、什么是堆？

堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。

如下图，是一个堆和数组的相互关系：

Java--常见排序算法

《算法导论》中谈到：对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、左孩子结点和右孩子节点的下标(基于下标以1开始)：

  • Parent(i) = floor(i/2)，i 的父节点下标(向下取整)
  • Left(i) = 2i，i 的左子节点下标
  • Right(i) = 2i + 1，i 的右子节点下标

二叉堆一般分为两种：最大堆和最小堆。

最大堆：

  • 最大堆的最大元素在根结点（堆顶）
  • 堆中每个父节点的元素值都大于等于其孩子结点
Java--常见排序算法

最小堆：

  • 最小堆的最小元素值在根结点（堆顶）
  • 堆中每个父节点的元素值都小于等于其孩子结点

Java--常见排序算法

三、 堆排序原理

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。

在堆中定义以下几种操作：

  • 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点，保证最大堆性质
  • 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
  • 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

这里我们需要注意：数组都是 Zero-Based，这就意味着我们的堆数据结构模型要发生改变。

Java--常见排序算法

相应的，几个计算公式也要作出相应调整：

  • Parent(i) = floor((i-1)/2)，i 的父节点下标
  • Left(i) = 2i + 1，i 的左子节点下标
  • Right(i) = 2(i + 1)，i 的右子节点下标

下面我们一个一个地看关于堆排序的3个操作：

(1)操作一：最大堆调整（Max-Heapify），保证最大堆的性质

Java--常见排序算法

Java代码实现如下：

[java] view plain copy
 print?
  1. package com.ngaa.bigdata.common.utils.sort;  
  2.   
  3. /** 
  4.  * Created by yangjf on 20171030. 
  5.  * Update date: 
  6.  * Time: 22:03 
  7.  * Project: ngaa-cdn-java-sdk 
  8.  * Package: com.ngaa.utils 
  9.  * Describe : 最大堆和最小堆的排序 
  10.  * <p> 
  11.  * Result of Test: test ok 
  12.  * Command: 
  13.  * </p><p> 
  14.  * Email:  [email protected] 
  15.  * Status：Using online 
  16.  * </p><p> 
  17.  * Please note: 
  18.  * Must be checked once every time you submit a configuration file is correct! 
  19.  * Data is priceless! Accidentally deleted the consequences! 
  20.  */  
  21. public class HeapSortUtil {  
  22.     // i节点的父亲节点下标  
  23.     private int parent(int i) {  
  24.         return (int) (Math.floor(i / 2) - 1);  
  25.     }  
  26.   
  27.     // i节点的左节点下标  
  28.     private int left(int i) {  
  29.         return 2 * i + 1;  
  30.     }  
  31.   
  32.     // i节点的右节点下标  
  33.     private int right(int i) {  
  34.         return 2 * (i + 1);  
  35.     }  
  36.   
  37.     // 交换下标为i的元素和下标为i的数组元素的值  
  38.     private void swap(int[] a, int i, int j) {  
  39.         int temp = a[i];  
  40.         a[i] = a[j];  
  41.         a[j] = temp;  
  42.     }  
  43.   
  44.     // 使以i为根的子树成为最大堆，并保持最大堆的性质  
  45.     private void maxHeapify(int[] a, int index, int heapSize) {  
  46.         int l = left(index);        // 左儿子的下标  
  47.         int r = right(index);       // 右儿子的下标  
  48.         int largestIndex;        // 最大值的下标  
  49.   
  50.         //如果左儿子节点小于等于堆大小，左节点大于当前值;  
  51.         if (l < heapSize && a[l] > a[index]) {  
  52.             largestIndex = l;  
  53.         } else {  
  54.             largestIndex = index;  
  55.         }  
  56.   
  57.         // 如果右儿子节点小于等于堆大小，右节点大于最大节点值;  
  58.         if (r < heapSize && a[r] > a[largestIndex]) {  
  59.             largestIndex = r;  
  60.         }  
  61.   
  62.         // 如果最大值的index不等于当前根i，则交换根节点位置  
  63.         if (largestIndex != index) {  
  64.             swap(a, index, largestIndex);  
  65.   
  66.             // 递归调用避免违反最大堆的性质  
  67.             maxHeapify(a, largestIndex, heapSize);  
  68.         }  
  69.     }  
  70. }  
  71. </p>  

(2)操作二：创建最大堆（Build-Max-Heap）

创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。流程如下：

Java--常见排序算法

Java实现的代码如下：

[java] view plain copy
 print?
  1. package com.ngaa.bigdata.common.utils.sort;  
  2.   
  3. /** 
  4.  * Created by yangjf on 20171030. 
  5.  * Update date: 
  6.  * Time: 22:03 
  7.  * Project: ngaa-cdn-java-sdk 
  8.  * Package: com.ngaa.utils 
  9.  * Describe : 最大堆和最小堆的排序 
  10.  * <p> 
  11.  * Result of Test: test ok 
  12.  * Command: 
  13.  * </p><p> 
  14.  * Email:  [email protected] 
  15.  * Status：Using online 
  16.  * </p><p> 
  17.  * Please note: 
  18.  * Must be checked once every time you submit a configuration file is correct! 
  19.  * Data is priceless! Accidentally deleted the consequences! 
  20.  */  
  21. public class BuildMaxheap {  
  22.     // i节点的父亲节点下标  
  23.     private int parent(int i) {  
  24.         return (int) (Math.floor(i / 2) - 1);  
  25.     }  
  26.   
  27.     // i节点的左节点下标  
  28.     private int left(int i) {  
  29.         return 2 * i + 1;  
  30.     }  
  31.   
  32.     // i节点的右节点下标  
  33.     private int right(int i) {  
  34.         return 2 * (i + 1);  
  35.     }  
  36.   
  37.     // 交换下标为i的元素和下标为i的数组元素的值  
  38.     private void swap(int[] a, int i, int j) {  
  39.         int temp = a[i];  
  40.         a[i] = a[j];  
  41.         a[j] = temp;  
  42.     }  
  43.   
  44.     // 使以i为根的子树成为最大堆，并保持最大堆的性质  
  45.     private void maxHeapify(int[] a, int index, int heapSize) {  
  46.         int l = left(index);        // 左儿子的下标  
  47.         int r = right(index);       // 右儿子的下标  
  48.         int largestIndex;     // 最大值的下标  
  49.   
  50.         //如果左儿子节点小于等于堆大小，左节点大于当前值;  
  51.         if (l < heapSize && a[l] > a[index]) {  
  52.             largestIndex = l;  
  53.         } else {  
  54.             largestIndex = index;  
  55.         }  
  56.   
  57.         // 如果右儿子节点小于等于堆大小，右节点大于最大节点值;  
  58.         if (r < heapSize && a[r] > a[largestIndex]) {  
  59.             largestIndex = r;  
  60.         }  
  61.   
  62.         // 如果最大值的index不等于当前根i，则交换根节点位置  
  63.         if (largestIndex != index) {  
  64.             swap(a, index, largestIndex);  
  65.   
  66.             // 递归调用避免违反最大堆的性质  
  67.             maxHeapify(a, largestIndex, heapSize);  
  68.         }  
  69.     }  
  70.     // 创建最大堆  
  71.     private void buildMaxHeapify(int[] a, int heapSize) {  
  72.         int parentIndex = parent(a.length);  
  73.         for (int i = parentIndex; i >= 0; i--) {  
  74.             maxHeapify(a, i, heapSize);  
  75.         }  
  76.     }  
  77. }  
  78. </p>  

(3)操作三：堆排序（Heap-Sort）

堆排序（Heap-Sort）是堆排序的接口算法，Heap-Sort先调用Build-Max-Heap将数组改造为最大堆，然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用Max-Heapify保持最大堆性质。由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆，重复n-1次之后，数组排列完毕。整个流程如下图：

Java--常见排序算法


Java实现如下：

[java] view plain copy
 print?
  1. package com.ngaa.bigdata.common.utils.sort;  
  2.   
  3. /** 
  4.  * Created by yangjf on 20171030. 
  5.  * Update date: 
  6.  * Time: 22:03 
  7.  * Project: ngaa-cdn-java-sdk 
  8.  * Package: com.ngaa.utils 
  9.  * Describe : 最大堆和最小堆的排序 
  10.  * <p> 
  11.  * Result of Test: test ok 
  12.  * Command: 
  13.  * </p><p> 
  14.  * Email:  [email protected] 
  15.  * Status：Using online 
  16.  * </p><p> 
  17.  * Please note: 
  18.  * Must be checked once every time you submit a configuration file is correct! 
  19.  * Data is priceless! Accidentally deleted the consequences! 
  20.  */  
  21. public class HeapSort {  
  22.     // i节点的父亲节点下标  
  23.     private int parent(int i) {  
  24.         return (int) (Math.floor(i / 2) - 1);  
  25.     }  
  26.   
  27.     // i节点的左节点下标  
  28.     private int left(int i) {  
  29.         return 2 * i + 1;  
  30.     }  
  31.   
  32.     // i节点的右节点下标  
  33.     private int right(int i) {  
  34.         return 2 * (i + 1);  
  35.     }  
  36.   
  37.     // 交换下标为i的元素和下标为i的数组元素的值  
  38.     private void swap(int[] a, int i, int j) {  
  39.         int temp = a[i];  
  40.         a[i] = a[j];  
  41.         a[j] = temp;  
  42.     }  
  43.   
  44.     // 使以i为根的子树成为最大堆，并保持最大堆的性质  
  45.     private void maxHeapify(int[] a, int index, int heapSize) {  
  46.         int l = left(index);        // 左儿子的下标  
  47.         int r = right(index);       // 右儿子的下标  
  48.         int largestIndex;     // 最大值的下标  
  49.   
  50.         //如果左儿子节点小于等于堆大小，左节点大于当前值;  
  51.         if (l < heapSize && a[l] > a[index]) {  
  52.             largestIndex = l;  
  53.         } else {  
  54.             largestIndex = index;  
  55.         }  
  56.   
  57.         // 如果右儿子节点小于等于堆大小，右节点大于最大节点值;  
  58.         if (r < heapSize && a[r] > a[largestIndex]) {  
  59.             largestIndex = r;  
  60.         }  
  61.   
  62.         // 如果最大值的index不等于当前根i，则交换根节点位置  
  63.         if (largestIndex != index) {  
  64.             swap(a, index, largestIndex);  
  65.   
  66.             // 递归调用避免违反最大堆的性质  
  67.             maxHeapify(a, largestIndex, heapSize);  
  68.         }  
  69.     }  
  70.   
  71.     // 创建最大堆  
  72.     private void buildMaxHeapify(int[] a, int heapSize) {  
  73.         int parentIndex = parent(a.length);  
  74.         for (int i = parentIndex; i >= 0; i--) {  
  75.             maxHeapify(a, i, heapSize);  
  76.         }  
  77.     }  
  78.   
  79.     // 对a数组升序排序：使用最大堆  
  80.     public void heapAscSort(int[] a, int headSize) {  
  81.         buildMaxHeapify(a, headSize);  
  82.         for (int i = a.length - 1; i > 0; i--) {  
  83.             swap(a, 0, i);  
  84.             headSize = headSize - 1;     // 通过减小headSize，去掉节点i  
  85.             maxHeapify(a, 0, headSize);  // 还原位置，避免违反最大堆性质  
  86.         }  
  87.     }  
  88. }  
  89. </p>  

四、堆排序的Java实现

(1)堆排序算法实现

[java] view plain copy
 print?
  1. package com.ngaa.bigdata.common.utils.sort;  
  2.   
  3. /** 
  4.  * Created by yangjf on 20171030. 
  5.  * Update date: 
  6.  * Time: 22:03 
  7.  * Project: ngaa-cdn-java-sdk 
  8.  * Package: com.ngaa.utils 
  9.  * Describe : 最大堆和最小堆的排序 
  10.  * <p> 
  11.  * Result of Test: test ok 
  12.  * Command: 
  13.  * </p><p> 
  14.  * Email:  [email protected] 
  15.  * Status：Using online 
  16.  * </p><p> 
  17.  * Please note: 
  18.  * Must be checked once every time you submit a configuration file is correct! 
  19.  * Data is priceless! Accidentally deleted the consequences! 
  20.  */  
  21. public class HeapSortUtil {  
  22.     // i节点的父亲节点下标  
  23.     private int parent(int i) {  
  24.         return (int) (Math.floor(i / 2) - 1);  
  25.     }  
  26.   
  27.     // i节点的左节点下标  
  28.     private int left(int i) {  
  29.         return 2 * i + 1;  
  30.     }  
  31.   
  32.     // i节点的右节点下标  
  33.     private int right(int i) {  
  34.         return 2 * (i + 1);  
  35.     }  
  36.   
  37.     // 交换下标为i的元素和下标为i的数组元素的值  
  38.     private void swap(int[] a, int i, int j) {  
  39.         int temp = a[i];  
  40.         a[i] = a[j];  
  41.         a[j] = temp;  
  42.     }  
  43.   
  44.     // 使以i为根的子树成为最大堆，并保持最大堆的性质  
  45.     private void maxHeapify(int[] a, int index, int heapSize) {  
  46.         int l = left(index);        // 左儿子的下标  
  47.         int r = right(index);       // 右儿子的下标  
  48.         int largestIndex;     // 最大值的下标  
  49.   
  50.         //如果左儿子节点小于等于堆大小，左节点大于当前值;  
  51.         if (l < heapSize && a[l] > a[index]) {  
  52.             largestIndex = l;  
  53.         } else {  
  54.             largestIndex = index;  
  55.         }  
  56.   
  57.         // 如果右儿子节点小于等于堆大小，右节点大于最大节点值;  
  58.         if (r < heapSize && a[r] > a[largestIndex]) {  
  59.             largestIndex = r;  
  60.         }  
  61.   
  62.         // 如果最大值的index不等于当前根i，则交换根节点位置  
  63.         if (largestIndex != index) {  
  64.             swap(a, index, largestIndex);  
  65.   
  66.             // 递归调用避免违反最大堆的性质  
  67.             maxHeapify(a, largestIndex, heapSize);  
  68.         }  
  69.     }  
  70.   
  71.     // 使以i为根的子树成为最小堆，并保持最小堆的性质  
  72.     private void minHeapify(int[] a, int index, int heapSize) {  
  73.         int l = left(index);        // 左儿子的下标  
  74.         int r = right(index);       // 右儿子的下标  
  75.         int largestIndex;     // 最大值的下标  
  76.   
  77.         //如果左儿子节点小于等于堆大小，左节点小于当前值;  
  78.         if (l < heapSize && a[l] < a[index]) {  
  79.             largestIndex = l;  
  80.         } else {  
  81.             largestIndex = index;  
  82.         }  
  83.   
  84.         // 如果右儿子节点小于等于堆大小，右节点小于最大节点值;  
  85.         if (r < heapSize && a[r] < a[largestIndex]) {  
  86.             largestIndex = r;  
  87.         }  
  88.   
  89.         // 如果最大值的index不等于当前根i，则交换根节点位置  
  90.         if (largestIndex != index) {  
  91.             swap(a, index, largestIndex);  
  92.   
  93.             // 递归调用避免违反最小堆的性质  
  94.             minHeapify(a, largestIndex, heapSize);  
  95.         }  
  96.     }  
  97.   
  98.     // 创建最大堆  
  99.     private void buildMaxHeapify(int[] a, int heapSize) {  
  100.         int parentIndex = parent(a.length);  
  101.         for (int i = parentIndex; i >= 0; i--) {  
  102.             maxHeapify(a, i, heapSize);  
  103.         }  
  104.     }  
  105.   
  106.     // 创建最小堆  
  107.     private void buildMinHeapify(int[] a, int heapSize) {  
  108.         int parentIndex = parent(a.length);  
  109.         for (int i = parentIndex; i >= 0; i--) {  
  110.             minHeapify(a, i, heapSize);  
  111.         }  
  112.     }  
  113.   
  114.     // 对a数组降序排序：使用最小堆  
  115.     public void heapDescSort(int[] a, int headSize) {  
  116.         buildMinHeapify(a, headSize);  
  117.         for (int i = a.length - 1; i > 0; i--) {  
  118.             swap(a, 0, i);  
  119.             headSize = headSize - 1;     // 通过减小headSize，去掉节点i  
  120.             minHeapify(a, 0, headSize);  // 还原位置，避免违反最小堆性质  
  121.         }  
  122.     }  
  123.   
  124.     // 对a数组升序排序：使用最大堆  
  125.     public void heapAscSort(int[] a, int headSize) {  
  126.         buildMaxHeapify(a, headSize);  
  127.         for (int i = a.length - 1; i > 0; i--) {  
  128.             swap(a, 0, i);  
  129.             headSize = headSize - 1;     // 通过减小headSize，去掉节点i  
  130.             maxHeapify(a, 0, headSize);  // 还原位置，避免违反最大堆性质  
  131.         }  
  132.     }  
  133.   
  134. }  
  135. </p>  

(2)使得数组始终保持升序或者降序

[java] view plain copy
 print?
  1. package com.ngaa.bigdata.common.utils.sort;  
  2.   
  3. /** 
  4.  * Created by yangjf on 20171030. 
  5.  * Update date: 
  6.  * Time: 8:46 
  7.  * Project: ngaa-cdn-java-sdk 
  8.  * Package: com.ngaa.utils 
  9.  * Describe : 找到最大堆和最小堆的排序 
  10.  * <p> 
  11.  * Result of Test: test ok 
  12.  * Command: 
  13.  * </p><p> 
  14.  * Email:  [email protected] 
  15.  * Status：Using online 
  16.  * </p><p> 
  17.  * Please note: 
  18.  * Must be checked once every time you submit a configuration file is correct! 
  19.  * Data is priceless! Accidentally deleted the consequences! 
  20.  */  
  21. public class FindTopNUtils {  
  22.     private static HeapSortUtil heapSortUtil = new HeapSortUtil();  
  23.   
  24.     /** 
  25.      * 方法的目的：使得数组a始终保持降序排序 
  26.      * 
  27.      * @param a     堆数组:例如 a={10,9,8,7,6,5,4,3,2,1} 
  28.      * @param value 输入的值 
  29.      * @throws Exception 异常 
  30.      */  
  31.     public synchronized void findMaxTopN(int[] a, int value) throws Exception {  
  32.         try {  
  33.             int arraySize = a.length; // 数组长度  
  34.             /** 
  35.              * tmp的值可能性是 
  36.              *  (1)大于最大的元素：   tmp>heap[0] 
  37.              *  (2)处于最小和最大之间：heap[arraySize-1]<tmp<heap[0] *="" (3)舍弃值：value="heap[0]" 、="" value="heap[arraySize-1]" 和="" <="" heap[arraysize-1](小于最小值)="" if="" (value=""> a[0] || (a[arraySize - 1] < value && value < a[0])) { 
  38.                 // 阶梯交换值：即将最小的值用value替换 
  39.                 a[arraySize - 1] = value; 
  40.                 // 保证最小堆的性质 
  41.                 heapSortUtil.heapDescSort(a, arraySize); 
  42.             } 
  43.  
  44.  
  45.         } catch (Exception minE) { 
  46.             throw new RuntimeException(minE); 
  47.         } 
  48.     } 
  49.  
  50.     /** 
  51.      * 方法的目的：使得数组a始终保持升序排序 
  52.      * 
  53.      * @param a     堆数组:例如 a={1,2,3,4,5,6,7,8} 
  54.      * @param value 输入的值 
  55.      * @throws Exception 异常 
  56.      */  
  57.     public synchronized void findMinTopN(int[] a, int value) throws Exception {  
  58.         try {  
  59.             int arraySize = a.length; // 数组长度  
  60.             /** 
  61.              * tmp的值可能性是 
  62.              *  (1)小于最小值：       tmp<heap[0] *="" (2)处于最小和最大之间：heap[0]<tmp<heap[arraysize-1]="" (3)舍弃值：tmp="heap[0]" 、="" tmp="heap[arraySize-1]" (4)tmp="">heap[arraySize-1](大于数组最大值) 
  63.              * 
  64.              * 
  65.              */  
  66.             if (value < a[0] || (a[0] < value && value < a[arraySize - 1])) {  
  67.                 // 阶梯交换值：即将最大的值用value替换  
  68.                 a[arraySize - 1] = value;  
  69.                 // 保证最大堆的性质  
  70.                 heapSortUtil.heapAscSort(a, arraySize);  
  71.             }  
  72.             // 为了避免数组初始时没有元素加入，需要添加：value>a[0]  
  73.             if (value > a[0] && a[0] == 0) {  
  74.                 // 阶梯交换值：即将第一个元素用value替换  
  75.                 a[0] = value;  
  76.                 // 保证最大堆的性质  
  77.                 heapSortUtil.heapAscSort(a, arraySize);  
  78.             }  
  79.   
  80.         } catch (Exception maxE) {  
  81.             throw new RuntimeException(maxE);  
  82.         }  
  83.     }  
  84. }  
  85. </heap[0]></tmp<heap[0]></p>  

(3)测试排序是否正常

准备一个文件：number.txt

包含的内容是1千万条随机数：

Java--常见排序算法

测试的Java代码如下:

[java] view plain copy
 print?
  1. package com.ngaa.bigdata.scala.test;  
  2.   
  3. import com.ngaa.bigdata.common.utils.sort.FindTopNUtils;  
  4.   
  5. import java.io.BufferedReader;  
  6. import java.io.File;  
  7. import java.io.FileReader;  
  8. import java.io.IOException;  
  9.   
  10. /** 
  11.  * Created by yangjf on 20171030. 
  12.  * Update date: 
  13.  * Time: 13:53 
  14.  * Project: sparkmvn 
  15.  * Package: com.ngaa.bigdata.scala.core 
  16.  * Describe : 
  17.  * <p> 
  18.  * Result of Test: test ok,test error 
  19.  * Command: 
  20.  * </p><p> 
  21.  * Email:  [email protected] 
  22.  * Status：Using online 
  23.  * </p><p> 
  24.  * Please note: 
  25.  * Must be checked once every time you submit a configuration file is correct! 
  26.  * Data is priceless! Accidentally deleted the consequences! 
  27.  */  
  28.   
  29.   
  30. public class TestTopNForJava {  
  31.     public static void main(String[] args) throws IOException {  
  32.         int topN = 10;  
  33.         String file = "G:/tmp/number.txt";  
  34.         // 最小的前n个数  
  35.         int[] minTopN = findTopNMin(topN, file);  
  36.         for (int minArray : minTopN) {  
  37.             System.out.println("-------->" + minArray);  
  38.         }  
  39.         System.out.println("-----------------------------------------------------------------------------");  
  40.         // 最大的前n个数  
  41.         int[] maxTopN = findTopNMax(topN, file);  
  42.         for (int maxArray : maxTopN) {  
  43.             System.out.println("-------->" + maxArray);  
  44.         }  
  45.   
  46.     }  
  47.   
  48.     //求最大的前topN个数  
  49.     static int[] findTopNMax(int topN, String filePath) throws NumberFormatException, IOException {  
  50.         File file = new File(filePath);  
  51.         int[] heap = new int[topN];  //创建长度为topN的数组  
  52.   
  53.         FileReader fr = new FileReader(file);  
  54.         BufferedReader br = new BufferedReader(fr);  
  55.         String line = null;  
  56.         FindTopNUtils heapSort = new FindTopNUtils();  
  57.         int i = 0;  //初始下标为0  
  58.         while ((line = br.readLine()) != null) {  
  59.             //如果元素有值  
  60.             if (line.trim().length() > 0) {  
  61.                 int tmp = Integer.  
  62.                         parseInt(line);  
  63.                 try {  
  64.                     heapSort.findMaxTopN(heap, tmp);  // 获取最大的前N个数  
  65.                 } catch (Exception e) {  
  66.                     e.printStackTrace();  
  67.                 }  
  68.             }  
  69.         }  
  70.         br.close();  
  71.         fr.close();  
  72.         return heap;  
  73.     }  
  74.   
  75.     //求最小的前topN个数  
  76.     static int[] findTopNMin(int topN, String filePath) throws NumberFormatException, IOException {  
  77.         File file = new File(filePath);  
  78.         int[] heap = new int[topN];  //创建长度为topN的数组  
  79.   
  80.         FileReader fr = new FileReader(file);  
  81.         BufferedReader br = new BufferedReader(fr);  
  82.         String line = null;  
  83.         FindTopNUtils heapSort = new FindTopNUtils();  
  84.         int i = 0;  //初始下标为0  
  85.         while ((line = br.readLine()) != null) {  
  86.             //如果元素有值  
  87.             if (line.trim().length() > 0) {  
  88.                 int tmp = Integer.  
  89.                         parseInt(line);  
  90.                 try {  
  91.                     heapSort.findMinTopN(heap, tmp);    // 获取最小的前N个数  
  92.                 } catch (Exception e) {  
  93.                     e.printStackTrace();  
  94.                 }  
  95.             }  
  96.         }  
  97.         br.close();  
  98.         fr.close();  
  99.         return heap;  
  100.     }  
  101. }  
  102. </p>  

五、堆排序的Scala实现

(1)堆排序算法

[plain] view plain copy
 print?
  1. package com.ngaa.bigdata.common.utils.sort  
  2.   
  3. /**  
  4.   * Created by yangjf on 20171030.  
  5.   * Update date:  
  6.   * Time: 10:09  
  7.   * Project: sparkmvn  
  8.   * Package: com.ngaa.bigdata.common.utils.sort  
  9.   * Describe :  
  10.   *          This class is the largest stack and the smallest heap sort for the second element of the ancestor.  
  11.   *  
  12.   * Result of Test: test ok  
  13.   * Command:  
  14.   *  
  15.   * Email:  [email protected]  
  16.   * Status：Using online  
  17.   *  
  18.   * Please note:  
  19.   * Must be checked once every time you submit a configuration file is correct!  
  20.   * Data is priceless! Accidentally deleted the consequences!  
  21.   *  
  22.   */  
  23. class SortByHeapUtils extends Serializable{  
  24.   
  25.   def parent(i: Int): Int = {  
  26.      (Math.floor(i / 2) - 1).asInstanceOf[Int]  
  27.   }  
  28.   
  29.   def left(i: Int): Int = {  
  30.     2 * i + 1  
  31.   }  
  32.   
  33.   def right(i: Int): Int = {  
  34.     2 * (i + 1)  
  35.   }  
  36.   
  37.   def swap(array: Array[(String, Long)], i: Int, j: Int): Unit = {  
  38.     val tmp = array(i)  
  39.     array(i) = array(j)  
  40.     array(j) = tmp  
  41.   }  
  42.   
  43.   def minHeapify(a: Array[(String, Long)], index: Int, heapSize: Int): Any = {  
  44.     val l = left(index)  
  45.     val r = right(index)  
  46.     var largestIndex: Int = 0  
  47.   
  48.     if (l < heapSize && (a(l)._2 < a(index)._2)) {  
  49.       largestIndex = l  
  50.     } else {  
  51.       largestIndex = index  
  52.     }  
  53.   
  54.     if (r < heapSize && a(r)._2 < a(largestIndex)._2) {  
  55.       largestIndex = r  
  56.     }  
  57.   
  58.     if (largestIndex != index) {  
  59.       swap(a, index, largestIndex)  
  60.       minHeapify(a, largestIndex, heapSize)  
  61.     }  
  62.   }  
  63.   
  64.   def maxHeapify(a: Array[(String, Long)], index: Int, heapSize: Int): Any = {  
  65.     val l = left(index)  
  66.     val r = right(index)  
  67.     var largestIndex: Int = 0  
  68.   
  69.     if (l < heapSize && (a(l)._2 > a(index)._2)) {  
  70.       largestIndex = l  
  71.     } else {  
  72.       largestIndex = index  
  73.     }  
  74.   
  75.     if (r < heapSize && a(r)._2 > a(largestIndex)._2) {  
  76.       largestIndex = r  
  77.     }  
  78.   
  79.     if (largestIndex != index) {  
  80.       swap(a, index, largestIndex)  
  81.       maxHeapify(a, largestIndex, heapSize)  
  82.     }  
  83.   }  
  84.   
  85.   
  86.   def buildMinHeapify(a: Array[(String, Long)], heapSize: Int): Unit = {  
  87.     val parentIndex: Int = parent(a.length)  
  88.     for (i <- parentIndex to 0 by -1) {  
  89.       minHeapify(a, i, heapSize)  
  90.     }  
  91.   }  
  92.   
  93.   def buildMaxHeapify(a: Array[(String, Long)], heapSize: Int): Unit = {  
  94.     val parentIndex: Int = parent(a.length)  
  95.     for (i <- parentIndex to 0 by -1) {  
  96.       maxHeapify(a, i, heapSize)  
  97.     }  
  98.   }  
  99.   
  100.   def heapDescSort(a: Array[(String, Long)], headSize: Int) {  
  101.     buildMinHeapify(a, headSize)  
  102.   
  103.     var headSizeTmp = headSize  
  104.     for (i <- a.length - 1 to 0 by -1) {  
  105.       swap(a, 0, i)  
  106.       headSizeTmp -= 1  
  107.       minHeapify(a, 0, headSizeTmp)  
  108.     }  
  109.   }  
  110.   
  111.   def heapAscSort(a: Array[(String, Long)], headSize: Int) {  
  112.     buildMaxHeapify(a, headSize)  
  113.   
  114.     var headSizeTmp = headSize  
  115.     for (i <- a.length - 1 to 0 by -1) {  
  116.       swap(a, 0, i)  
  117.       headSizeTmp -= 1  
  118.       maxHeapify(a, 0, headSizeTmp)  
  119.     }  
  120.   }  
  121.   
  122. }  

(2)保持数组降序或者升序

[plain] view plain copy
 print?
  1. package com.ngaa.bigdata.common.utils.sort  
  2.   
  3. import com.ngaa.bigdata.common.model.global.NgaaException  
  4. import com.ngaa.bigdata.common.traits.HeapSort  
  5.   
  6. /**  
  7.   * Created by yangjf on 20171030.  
  8.   * Update date:  
  9.   * Time: 11:54  
  10.   * Project: sparkmvn  
  11.   * Package: com.ngaa.bigdata.common.utils.sort  
  12.   * Describe :  
  13.   *        The Scala version looks for the largest number of N and the smallest number of N numbers in the tuple.  
  14.   *  
  15.   * Result of Test: test ok  
  16.   * Command:  
  17.   *  
  18.   * Email:  [email protected]  
  19.   * Status：Using online  
  20.   *  
  21.   * Please note:  
  22.   * Must be checked once every time you submit a configuration file is correct!  
  23.   * Data is priceless! Accidentally deleted the consequences!  
  24.   *  
  25.   */  
  26. class FindSortTopN extends HeapSort with Serializable{  
  27.   private val sortByHeapUtils = new SortByHeapUtils  
  28.   
  29.   @throws(classOf[NgaaException])  
  30.   override def findMaxTopN(a: Array[(String, Long)], value: (String, Long)): Unit = {  
  31.     try {  
  32.       val arraySize: Int = a.length // 数组长度  
  33.       /**  
  34.         * tmp的值可能性是  
  35.         * (1)大于最大的元素：   tmp>heap[0]  
  36.         * (2)处于最小和最大之间：heap[arraySize-1]< tmp < heap[0]  
  37.         * (3)舍弃值：value=heap[0] 、 value=heap[arraySize-1] 和 value < heap[arraySize-1](小于最小值)  
  38.         */  
  39.       if (value._2 >= a(0)._2 || (a(arraySize - 1)._2 < value._2 && value._2 < a(0)._2)) {  
  40.         // 阶梯交换值：即将最小的值用value替换  
  41.         a(arraySize - 1) = value  
  42.         // 保证最小堆的性质  
  43.         sortByHeapUtils.heapDescSort(a, arraySize)  
  44.       }  
  45.     }  
  46.     catch {  
  47.       case minE: Exception => throw new RuntimeException(minE)  
  48.     }  
  49.   }  
  50.   
  51.   @throws(classOf[NgaaException])  
  52.   override def findMinTopN(a: Array[(String, Long)], value: (String, Long)): Unit = {  
  53.     try {  
  54.       val arraySize = a.length; // 数组长度  
  55.       /**  
  56.         * tmp的值可能性是  
  57.         * (1)小于最小值：       tmp<heap[0] *="" (2)处于最小和最大之间：heap[0]<tmp<heap[arraysize-1]="" (3)舍弃值：tmp="heap[0]" 、="" tmp="heap[arraySize-1]" (4)tmp="">heap[arraySize-1](大于数组最大值)  
  58.         *  
  59.         *  
  60.         */  
  61.   
  62.       if (value._2 < a(0)._2 || (a(0)._2 < value._2 && value._2 < a(arraySize - 1)._2)) {  
  63.         // 阶梯交换值：即将最大的值用value替换  
  64.         a(arraySize - 1) = value  
  65.         // 保证最大堆的性质  
  66.         sortByHeapUtils.heapAscSort(a, arraySize)  
  67.       }  
  68.       // 为了避免数组初始时没有元素加入，需要添加：value>a[0]  
  69.       if (value._2 > a(0)._2 && a(0)._2 == 0) {  
  70.         // 阶梯交换值：即将第一个元素用value替换  
  71.         a(0) = value  
  72.         // 保证最大堆的性质  
  73.         sortByHeapUtils.heapAscSort(a, arraySize)  
  74.       }  
  75.   
  76.     } catch {  
  77.       case maxE: Exception => throw new RuntimeException(maxE)  
  78.     }  
  79.   }  
  80.   
  81.   @throws(classOf[NgaaException])  
  82.   override def initArray(array: Array[(String, Long)],initValue:(String,Long)=("init",0l)): Unit = {  
  83.    for(i <- array.indices ){  
  84.       array(i)=initValue  
  85.    }  
  86.   }  
  87. }  
  88. </heap[0]>  

注：

代码中涉及的文件内容如下

[plain] view plain copy
 print?
  1. package com.ngaa.bigdata.common.traits  
  2.   
  3. import com.ngaa.bigdata.common.model.global.NgaaException  
  4.   
  5. /**  
  6.   * Created by yangjf on 20171030.  
  7.   * Update date:  
  8.   * Time: 11:19  
  9.   * Project: sparkmvn  
  10.   * Package: com.ngaa.bigdata.common.traits  
  11.   * Describe : Heap sort interface  
  12.   *  
  13.   * Result of Test: test ok  
  14.   * Command:  
  15.   *  
  16.   * Email:  [email protected]  
  17.   * Status：Using online  
  18.   *  
  19.   * Please note:  
  20.   * Must be checked once every time you submit a configuration file is correct!  
  21.   * Data is priceless! Accidentally deleted the consequences!  
  22.   *  
  23.   */  
  24.  trait HeapSort  extends Serializable{  
  25.   
  26.   /**  
  27.     *  Initialize the array  
  28.     * @param array       Input array  
  29.     * @param initValue   Init value  
  30.     * @throws com.ngaa.bigdata.common.model.global.NgaaException exception  
  31.     */  
  32.     @throws(classOf[NgaaException])  
  33.     def initArray(array:Array[(String, Long)],initValue:(String,Long)=("init",0l))  
  34.   
  35.   /**  
  36.     * Discover the largest number of N numbers in the Tuple.  
  37.     * @param array Input array.  
  38.     * @param tuple Tuple  
  39.     * @throws com.ngaa.bigdata.common.model.global.NgaaException exception  
  40.     */  
  41.     @throws(classOf[NgaaException])  
  42.     def findMaxTopN(array:Array[(String, Long)],tuple:(String,Long))  
  43.   
  44.   /**  
  45.     * Discover the smallest number of N numbers in the Tuple.  
  46.     * @param array Input array.  
  47.     * @param tuple Tuple  
  48.     * @throws com.ngaa.bigdata.common.model.global.NgaaException exception  
  49.     */  
  50.     @throws(classOf[NgaaException])  
  51.     def findMinTopN(array:Array[(String, Long)],tuple:(String,Long))  
  52.   
  53. }  



参考文章：

1、堆排序：http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.2.1.htm

2、算法-堆排序：http://ind.ntou.edu.tw/~litsnow/al98/pdf/Algorithm-Ch6-Heapsort.pdf

3、堆排序：http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

4、排序算法：http://www.sorting-algorithms.com/

5、计算机算法：http://www.nowamagic.net/algorithm/algorithm_HeapSortStudy.php

6、堆排序wiki：https://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

相关推荐