堆排序与快速排序

前言 

 前面差不多学习了插入排序、选择排序、冒泡排序、归并排序。这些排序除了归并排序在时间上消耗为:θ(nlgn)外,其余排序时间消耗都为:θ(n2). 

接下来要讲的就是两种比较优雅的比较排序算法:堆排序和快速排序。 堆排序最坏情况下可以达到上界:ο(nlgn).快速排序平均情况下可以达到:θ(nlgn)。

堆排序

堆排序的关键在于完全二叉树。堆排序开始要构建一个完全二叉树,且该完全二叉树必须满足某一个结点大于左子节点的值和右子结点的值。我们假设根结点中的值为数组中下标为0的元素,根结点的左子结点下标为1,根结点的右子结点下标为2...依此类推。假设某一个结点的值对应数组中下标为i的元素,那么该结点的左子结点的值对应数组的数组元素下标为(2*i+1),右子结点的值对应数组元素下标为(2*i+2)。堆排序的步骤是:

1. 首先要构造一个以数组中下标为0的元素作为根结点的完全堆二叉树。此二叉树构造完成之后可以保证根结点的值为数组中最大的元素且对于堆中的所有结点的值都大于它的左子结点和右子结点的值。

2. 将堆中的根结点和堆中最后一个结点替换,然后重新构造以数组下标为0,长度为数组长度减1的完全堆二叉树。

3. 重复第二部直到需要构建的堆中元素只剩下唯一一个。

具体代码实现如下:

 1 public static void main(String[] args)
 2     {
 3         int[] arr = {1, 12, 11, 4, 5, 7, 3, 1, 23, 56, 34, 76, 25};
 4         heapSort(arr);
 5     }
 6 
 7     /**
 8      * 堆排序
 9      * @param arr 待排序的数组
10      */
11     private static void heapSort(int[] arr) {
12         for (int i=arr.length/2; i>=0; i--)
13         {
14             buildHeapTree(arr, i, arr.length);
15         }
16         
17         for (int i=arr.length-1; i>=0; i--)
18         {
19             swap(arr, 0, i);        // 交换根结点和堆树中最后一个结点
20             buildHeapTree(arr, 0, i);    // 再次以下标为0的元素开始构建层次递减的堆树
21         }
22         
23         System.out.println(Arrays.toString(arr));
24     }
25     
26     /**
27      * 构建堆树(满足时一颗完全二叉树,且任何结点大于他的子结点)
28      * @param arr  传入的数组
29      * @param rootIndex 根结点对应的数组下标(即以当前下标作为根结点来将数组中改下标之后的元素作为其子节点的堆树)
30      * @param deep     堆的深度(对于超过堆深度的数组中的元素不进行堆树的构建)
31      */
32     private static void buildHeapTree(int[] arr, int rootIndex, int deep) {
33         int leftChildIndex = rootIndex * 2 + 1;
34         int rightChildIndex = rootIndex * 2 + 2;
35         int maxIndex = rootIndex;
36         if (leftChildIndex < deep && arr[leftChildIndex] > arr[rootIndex])
37         {
38             // 如果左子结点大于右子结点,说明当前最大结点的下标应该为左子结点的下标
39             maxIndex = leftChildIndex;
40         }
41         
42         if (rightChildIndex < deep && arr[rightChildIndex] > arr[maxIndex])
43         {
44             // 如果右子结点的值大于与左子结点比较之后得到的最大的结点的值,则说明最大结点的下标应该为右子结点的下标
45             maxIndex = rightChildIndex;
46         }
47         
48         if (maxIndex != rootIndex)
49         {
50             // 以当前下标从数组中的元素开始没法够造成堆树,此时需要在树中将最大值所在的结点和根结点的位置互换,又因为堆树的构建是自下往上的,互换了之后需要考虑对前面最大值所在堆树的影响,所以需要再次递归调用以前面最大值元素所在位置为根结点构建堆树、
51             swap(arr, maxIndex, rootIndex);
52             buildHeapTree(arr, maxIndex, deep);
53         }
54     }
55 
56     private static void swap(int[] arr, int index1, int index2) {
57         int temp = arr[index1];
58         arr[index1] = arr[index2];
59         arr[index2] = temp;
60     }

快速排序:

  快速排序的思想其实和归并排序有些类似。都是通过分治的思想来实现的。只不过归并排序先是将数组均分排序,然后再进行归并整理。快速排序是先得到分开点,然后再对分出来的两个数组进行分别快速排序。

  废话不多说直接上代码:

 1 public static void main(String[] args)
 2     {
 3         int[] arr = {1, 12, 11, 4, 5, 7, 3, 1, 23, 56, 34, 76, 25};
 4         quickSort(arr);
 5     }
 6 
 7     private static void quickSort(int[] arr) {
 8         divideQuickSort(arr, 0, arr.length - 1);
 9         System.out.println(Arrays.toString(arr));
10     }
11 
12     private static void divideQuickSort(int[] arr, int start, int end) {
13         if (start >= end)
14         {
15             return;
16         }
17         
18         int r = partition(arr, start, end);
19         divideQuickSort(arr, start, r - 1);
20         divideQuickSort(arr, r + 1, end);
21     }
22 
23     /**
24      * 得到快速排序的分割点
25      * @param arr     传入的待排序的数组
26      * @param start  排序的起始元素下标
27      * @param end  排序的终止元素下标
28      * @return          分割点的下标
29      */
30     private static int partition(int[] arr, int start, int end) {
31         // 先要找一个对比的元素,这里取终止元素作为对比的元素
32         int compareValue = arr[end];
33         
34         // 从起始元素到比较元素前一个元素循环与终止元素进行比对
35         int placeStartIndex = start;
36         for (int i = start; i <= end-1; i++)
37         {
38             if (arr[i] < compareValue)
39             {
40                 // 发现比比较元素小的元素,通过交换位置依次从起始元素位置开始摆放
41                 swap(arr, i, placeStartIndex++);
42             }
43         }
44         
45         // 将比较元素放到比它都小的元素的右侧
46         swap(arr, placeStartIndex, end);
47         
48         // 此时返回当前比较元素交换之后的位置
49         return placeStartIndex;
50     }
51     
52     private static void swap(int[] arr, int index1, int index2) {
53         int temp = arr[index1];
54         arr[index1] = arr[index2];
55         arr[index2] = temp;
56     }

以上两种算法都是比较优雅的比较算法。实际上他们在实现的时候不需要额外的分配内存,直接在数组之内进行比较和位置调换。特别是堆排序,完美的实现了将数组又作为线性的元素列表,又做为树结点。可以看到比较算的时间极限应该就在Ω(nlgn),对于其他的一些关于数组长度线性的排序算法必须依赖于数组的某些特性,而那些也不能称作完全的比较算法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(四)No.52

这是本坑的第四篇,之前已经说了关于 HashSet 、BitMap 、Bloom Filter 布隆过滤器了,本篇主要讲B-树。要是还不知道前面讲了啥的,可以点...

1787
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

992
来自专栏决胜机器学习

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十三) ——动态查找表(二叉排序树) (原创内容,转载请注明来源,谢谢) 一、概念 1、动态查找表特点 当对动态查找表进行查...

43010
来自专栏专注 Java 基础分享

从源码解析TreeMap

     上篇文章我们介绍了HashMap集合,这是一个键值对集合,可以高效的按照键查找数值。但是它有一个缺陷:数据如果是无序的可以是很高效的,但是如果数据...

1928
来自专栏ACM算法日常

算法合集 | 神奇的笛卡尔树 - HDU 1506

笛卡尔树是一个很有意思的树形结构,因为它同时满足两个性质,从key(key就是索引位置,如下图中9的key为1,3的key为2......)来看...

1172
来自专栏书山有路勤为径

二叉查找树转换为较大树

Leetcode 538 已知一个二叉查找树,将它转换为一个较大树,即所有的二叉查找树的节点,赋值为该节点本身的值与该节点大的节点的值的和

712
来自专栏陈树义

3.Redis常用命令:String

字符串类型是Redis中最为基础的数据存储类型,它在Redis中是二进制安全的,这便意味着该类型可以接受任何格式的数据,如JPEG图像数据或Json对象描述信息...

3528
来自专栏java初学

二叉查找树

35310
来自专栏恰同学骚年

数据结构基础温故-4.树与二叉树(中)

在上一篇中,我们了解了树的基本概念以及二叉树的基本特点和代码实现,还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是,由于递归需要系统堆栈,所以空间消耗要...

711
来自专栏JAVA烂猪皮

轻松理解 Java HashMap 和 ConcurrentHashMap

Map 这样的 Key Value 在软件开发中是非常经典的结构,常用于在内存中存放数据。

591

扫码关注云+社区