堆排序与快速排序

前言 

 前面差不多学习了插入排序、选择排序、冒泡排序、归并排序。这些排序除了归并排序在时间上消耗为:θ(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 条评论
登录 后参与评论

相关文章

来自专栏算法channel

图解用栈数据结构对树的遍历

本公众号主要推送关于如何构思算法使之应用到我们的工作中。计算机常用算法思想大致来说有,分而治之,动态规划,贪心算法,搜索算法,回溯 ,训练这些思维的一个很好的平...

34011
来自专栏null的专栏

挑战数据结构和算法面试题——二叉搜索树的后序遍历

题目来源“数据结构与算法面试题80道”。在此给出我的解法,如你有更好的解法,欢迎留言。 ? 分析: 根据二叉查找树的定义,二叉查找树或者是一棵空二叉树,或者是...

3234
来自专栏Java3y

堆排序就这么简单

一、堆排序介绍 来源百度百科: 堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指...

43411
来自专栏desperate633

LintCode 二叉树中的最大路径和题目分析代码

给出一棵二叉树,寻找一条路径使其路径和最大,路径可以在任一节点中开始和结束(路径和为两个节点之间所在路径上的节点权值之和)

552
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1345
来自专栏我的技术专栏

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

814
来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

1756
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1624
来自专栏大数据学习笔记

面试算法题

题目来源于牛客网:https://www.nowcoder.com/ta/coding-interviews 1、二维数组中的查找 在一个二维数组中,每一行都按...

7186
来自专栏尾尾部落

[剑指offer] 把二叉树打印成多行

就是二叉树的层序遍历,用队列来实现。我们需要两个变量,一个start记录当前层已经打印的节点个数,一个end记录前当层所有的节点个数,当 start == en...

603

扫描关注云+社区