排序算法

发表于 更新于 分类于 阅读次数： 本文字数： 12k 阅读时长 ≈ 11 分钟

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这里说说八大排序的内部排序。

概述

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
我们这里说说八大排序的内部排序。

当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；*

如何分析一个算法

算法的执行效率

  1. 最好情况、最坏情况、平均情况时间复杂度

我们在分析排序算法的时间复杂度时，要分别给出最好情况、最坏情况、平均情况下的时间复杂度。除此之外，你还要说出最好、最坏时间复杂度对应的要排序的原始数据是什么样的。

为什么要区分这三种时间复杂度呢？第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。

  1. 时间复杂度的系数、常数 、低阶

我们知道，时间复杂度反应的是数据规模n很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能
是10个、 100个、 1000个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

  1. 比较次数和交换（或移动）次数

基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如
果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

排序算法的内存消耗

我们前面讲过，算法的内存消耗可以通过空间复杂度来衡量，排序算法也不例外。不过，针对排序算法的空间复杂度，我们还引入了一个新的概念， 原地排
序（Sorted in place）。原地排序算法，就是特指空间复杂度是O(1)的排序算法。

冒泡排序、插入排序、选择排序，都是原地排序算法。

排序算法的稳定性

这个概念是说，如果待排序的序列中存在
值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

我通过一个例子来解释一下。比如我们有一组数据2， 9， 3， 4， 8， 3，按照大小排序之后就是2， 3， 3， 4， 8， 9。

这组数据里有两个3。经过某种排序算法排序之后，如果两个3的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；如果前后顺序发生变化，那
对应的排序算法就叫作不稳定的排序算法。

有序度/逆序度

有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示就是这样：

1
2
有序元素对： 
a[i] <= a[j], 如果i < j

2, 4, 3, 1, 5, 6 这组数据的有序度 11，其有序元素对为11个，分别为：

1
2
3
4
5
(2,4), (2,3), (2,5), (2,6), 
(4,5), (4,6),
(3,5), (3,6),
(1,5),
(5,6)

同理，对于一个倒序排列的数组，比如6， 5， 4， 3， 2， 1，有序度是0；对于一个完全有序的数组，比如1， 2， 3， 4， 5， 6，有序度就是 n * (n-1) / 2 ，也就是15。我
们把这种完全有序的数组的有序度叫作满有序度。

逆序度的定义正好跟有序度相反（默认从小到大为有序）。

1
2
逆序元素对： 
a[i] > a[j], 如果i < j。

公式

(n为元素个数)

满有序度 = n * (n-1) / 2

逆序度=满有序度-有序度。

举个栗子

要排序的数组的初始状态是4， 5， 6， 3， 2， 1

其中，有序元素对有(4， 5) (4， 6)(5， 6)，所以有序度是3。 n=6，
所以排序完成之后终态的满有序度为 n * (n-1) / 2 = 15。

冒泡排序包含两个操作原子， 比较和交换。每交换一次，有序度就加1。不管算法怎么改进，交换次数总是确定的，即为逆序度， 也就是 n * (n-1) / 2 – 初始有序度。
此例中就是15–3=12，要进行12次交换操作。

经典算法示例

基于比较的排序

冒泡排序

  • 原地排序算法

  • 稳定的排序算法

  • 最好时间复杂度O(n)

  • 最坏时间复杂度O(n^2)

  • 平均时间复杂度O(n^2)

  • 冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)

  • 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的
    数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。

  • 最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，

冒泡排序的核心是从头遍历序列。以升序排列为例：将第一个元素和第二个元素比较，若前者大于后者，则交换两者的位置，再将第二个元素与第三个元素比较，若前者大于后者则交换两者位置，以此类推直到倒数第二个元素与最后一个元素比较，若前者大于后者，则交换两者位置。这样一轮比较下来将会把序列中最大的元素移至序列末尾，这样就***安排好了最大数的位置(每次找到一个最大的)***，接下来只需对剩下的（n-1）个元素，重复上述操作即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//时间复杂度O(N^2)， 额外空间复杂度O(1)
public class Sort_01_bubbleSort {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1])
                    swap(arr, j, j + 1);
            }
        }
    }
    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

插入排序

  • 原地排序算法

  • 稳定的排序算法

  • 最好时间复杂度O(n)

  • 最坏时间复杂度O(n^2)

  • 平均时间复杂度O(n^2)

  • 从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个原地排序算法。

  • 在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定
    的排序算法。

  • 如果要排序的数据已经是有序的，我们并不需要搬移任何数据。如果我们从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位
    置。所以这种情况下，最好是时间复杂度为O(n)。注意，这里是从尾到头遍历已经有序的数据。
    如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为O(n2)。

    还记得我们在数组中插入一个数据的平均时间复杂度是多少吗？没错，是O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环

执行n次插入操作，所以平均时间复杂度为O(n2)。

插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中……第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。
类似手里有一把排好序的牌，心哪一张和最后一个比较，看能插到前边哪个位置上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//时间复杂度O(N^2)， 额外空间复杂度O(1)
//实际时间和数据有关系O(N)~O(N^2)
//           排好序的数据~逆序数据
public class Sort_02_insertSort {
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }
    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

选择排序

  • 原地排序算法

  • 稳定的排序算法

  • 最好时间复杂度O(n^2)

  • 最坏时间复杂度O(n^2)

  • 平均时间复杂度O(n^2)

  • 选择排序空间复杂度为O(1)，是一种原地排序算法。选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n2)。

  • 选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素
    交换位置，这样破坏了稳定性。

    比如5， 8， 5， 2， 9这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
注意:

选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//时间复杂度O(N^2)， 额外空间复杂度O(1)
public class Sort_03_selectSort {
    public static void selectSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for(int j = i + 1; j < arr.length; j++){
                minIndex = arr[j] < arr[minIndex] ? j: minIndex; 
            }
            swap(arr, i, minIndex);
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

归并排序

  • 原地排序算法
  • 稳定的排序算法
  • 最好时间复杂度O(nlogn)
  • 最坏时间复杂度O(nlogn)
  • 平均时间复杂度O(nlogn)

递归方法的复杂度分析，见另一篇 master公式。

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
13DLZT.jpg

归并排序是稳定排序，他也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。

从上图中可看出，**每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|**。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 归并排序。
 * 
 * 时间复杂度O(N*logN)，额外空间复杂度O(N)
 * 
 * @author Jelly
 *
 */
public class Sort_04_mergeSort {
	public static void mergeSort(int[] arr, int l, int r) {
		if(l == r)
			return;
		int mid = l + ((r - l) >> 1);
		mergeSort(arr, l, mid);
		mergeSort(arr, mid + 1, r);
		merge(arr, l, mid, r);
	}
	private static void merge(int[] arr, int l, int mid, int r) {
		int[] help = new int[r - l + 1];
		int left = l;
		int right = mid + 1;
		int i = 0;
		while(left <= mid && right <= r)
			help[i++] = arr[left] < arr[right] ? arr[left++] : arr[right++];
		while(left <= mid)
			help[i++] = arr[left++];
		while(right <= r)
			help[i++] = arr[right++];
		//将help数组拷贝到arr数组中
		System.arraycopy(help, 0, arr, l, help.length);
	}
}

快速排序

  • 原地排序算法
  • 稳定的排序算法
  • 最好时间复杂度O(nlogn)
  • 最坏时间复杂度O(n^2)
  • 平均时间复杂度O(nlogn)

归并-快排对比

归并排序的处理过程是由下到上的，先处理子问题，然后再合并。而快排正好相反，它的处理过程是由上到下的，先分区，然后再处理子问题。

归并排序虽然是稳定的、时间复杂度为O(nlogn)的排序算法，但是它是非原地排序算法。

我们前面讲过，归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 快速排序。（随机快排）
 * 
 * 时间复杂度O(N*logN), 额外空间复杂度O(logN)
 * 
 * @author Jelly
 *
 */
public class Sort_05_quickSort {
	public static void quickSort(int[] arr, int l, int r) {
		if (l < r) {
			swap(arr, (int) (l + Math.random() * (r - l + 1)), r);// 随机快排，减少出现最坏的情况
			int[] p = partition(arr, l, r);
			quickSort(arr, l, p[0]);
			quickSort(arr, p[1], r);
		}
	}
	private static int[] partition(int[] arr, int l, int r) {
		int less = l - 1;
		int more = r;
		while(l < more) {
			if(arr[l] < arr[r])
				swap(arr, ++less, l++);
			else if(arr[l] > arr[r])
				swap(arr, --more, l);
			else
				l++;
		}
		swap(arr, more, r);
		return new int[] {less, more};
	}
	private static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

非基于比较的排序

桶排序

  • 原地排序算法

  • 稳定的排序算法

  • 最好时间复杂度O(n)

  • 最坏时间复杂度O(n)

  • 平均时间复杂度O(n)

  • 如果要排序的数据有n个，我们把它们均匀地划分到m个桶内，每个桶里就有k=n/m个元素。每个桶内部使用快速排序，时间复杂度为O(k * logk)。 m个桶排序的时
    间复杂度就是O(m * k * logk)，因为k=n/m，所以整个桶排序的时间复杂度就是O(n*log(n/m))。当桶的个数m接近数据个数n时， log(n/m)就是一个非常小的常量，这
    个时候桶排序的时间复杂度接近O(n)。

核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之
后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

  • 设置一个定量的数组当作空桶。
  • Divide - 从待排序数组中取出元素，将元素按照一定的规则塞进对应的桶子去。
  • 对每个非空桶进行排序，通常可在塞元素入桶时进行插入排序。
  • Conquer - 从非空桶把元素再放回原来的数组中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 桶排序。
 * 
 * N为待排数据，M个桶
 * 
 * 平均时间复杂度O(N + C), 其中C = N*(logN-logM)。空间复杂度 O(N+M)
 * 
 * 对于同样的N，桶的数量M越大，其效率越高。
 * 
 * @author Jelly
 *
 */
public class Sort_07_bucketSort {
	public static void bucketSort(int[] arr) {
		if (arr == null || arr.length < 2)
			return;
		// 找到数组中最大的一个元素
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < arr.length; i++) {
			max = arr[i] > max ? arr[i] : max;
		}
		// 创建一个比最大元素大 1 的桶
		int[] bucket = new int[max + 1];
		// 遍历数组,将元素做为桶的下标，找到桶的位置.相同的元素，则在当前位置加1
		for (int i = 0; i < arr.length; i++) {
			bucket[arr[i]]++;
		}
		// 遍历桶
		int i = 0;
		for (int j = 0; j < bucket.length; j++) {
			while (bucket[j]-- > 0) { // 该位置桶的value时多少，原数组就有几个该数据
				arr[i++] = j;
			}
		}
	}
}

计数排序

顾名思义，就是对待排序数组按元素进行计数。使用前提是需要先知道待排序数组的元素范围，将这些一定范围的元素置于新数组中，新数组的大小为待排序数组中最大元素与最小元素的差值。
维基上总结的四个步骤如下：

  • 定新数组大小——找出待排序的数组中最大和最小的元素
  • 统计次数——统计数组中每个值为i的元素出现的次数，存入新数组C的第i项
  • 对统计次数逐个累加——对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
  • 反向填充目标数组——将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

其中反向填充主要是为了避免重复元素落入新数组的同一索引处。

基数排序

原理类似桶排序,这里总是需要10个桶,多次使用

首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数

例如

待排序数组[62,14,59,88,16]简单点五个数字

分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样

| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶编号

将桶里的数字顺序取出来,

输出结果:[62,14,16,88,59]

再次入桶,不过这次以十位数的数字为准,进入相应的桶,变成下边这样:

由于前边做了个位数的排序,所以当十位数相等时,个位数字是由小到大的顺序入桶的,就是说,入完桶还是有序

| 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶编号

因为没有大过100的数字,没有百位数,所以到这排序完毕,顺序取出即可

最后输出结果:[14,16,59,62,88]

小结

1MKgjf.png

如果对小规模数据进行排序，可以选择时间复杂度是O(n2)的算法；如果对大规模数据进行排序，时间复杂度是O(nlogn)的算法更加高效。

所以，为了兼顾任意规
模数据的排序，一般都会首选时间复杂度是O(nlogn)的排序算法来实现排序函数。

工程中使用

数据量小于60会使用插入排序

原因： 虽然插入排序时间复杂度O(n^2) 但是常数项较小，在数据量小的时候，复杂度不会表现出劣势

数据是基础类型用快排

原因： 因为基础类型数据不用区分数据的先后顺序，是无差别的。即基础数据不用关心排序的稳定性。

数据是自定义类型用归并排序

归并排序可以保持排序后的稳定性。

堆排序

  • 原地排序算法
  • 稳定的排序算法
  • 最好时间复杂度O(nlogn)
  • 最坏时间复杂度O(nlogn)
  • 平均时间复杂度O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
/**
 * 大根堆。从0开始的数组。
 * 父节点:i；左子节点:2*i+1；右子节点:2*i+2
 * 子节点:i；父节点：floor((i-1)/2)
 */
class MaxHeap {
    /**
     * 堆数据区
     */
    private int[] data;
    /**
     * 堆中数据数量
     */
    private int size;
    /**
     * 堆最大容量
     */
    private int capacity;
    public MaxHeap(int capacity) {
        this.data = new int[capacity];
        this.size = 0;
        this.capacity = capacity;
    }
    /**
     * 修改了调整堆的方法。从最后的元素开始shiftDown, 每次构建只调整 n/2 次，构建完成即获取到了调整好的大根堆。
     *
     * @param arr      构建堆元数据。
     * @param capacity 堆大小
     */
    public MaxHeap(int[] arr, int capacity) {
        int arrSize = arr.length;
        //当arr容量大于给定的capacity时，只存储capacity大小的数据。
        if (capacity < arrSize) {
            arrSize = capacity;
        }
        this.data = new int[capacity];
        System.arraycopy(arr, 0, this.data, 0, arrSize);
        this.capacity = capacity;
        this.size = arrSize;
        for (int i = size - 1; i >= 0; i--) {
            shiftDown(i);
        }
    }
    public void insert(int d) {
        if (size >= capacity) {
            System.out.println("heap is full!");
            return;
        }
        //插入堆尾
        data[size++] = d;
        //调整堆
        shiftUp(size - 1);
    }
    private void shiftUp(int cur) {
        while (cur > 0) {
            int p = (cur - 1) / 2;
            if (data[cur] > data[p]) {
                swap(data, cur, p);
            }
            cur = p;
        }
    }
    public int pop() {
        if (size == 0) {
            System.out.println("heap is empty!!");
            return -1;
        }
        //弹出顶部元素
        int t = data[0];
        //将最后一个元素换到顶部
        data[0] = data[--size];
        //将第一个元素下移到适当位置
        shiftDown(0);
        return t;
    }
    private void shiftDown(int cur) {
        int left = cur * 2 + 1;
        while (left < size) {
            //找到两个子节点中较大的一个
            if (left + 1 < size && data[left] < data[left + 1]) {
                left++;
            }
            if (data[cur] >= data[left]) {
                break;
            }
            //元素下移
            swap(data, cur, left);
            cur = left;
        }
    }
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    @Override
    public String toString() {
        return "MaxHeap{" +
                "data=" + Arrays.toString(data) +
                ", size=" + size +
                ", capacity=" + capacity +
                '}';
    }
}
//堆排序
public void heapSort(int arr[],MaxHeap heap){
    for(int i = 0; i < arr.length; i++){
        heap.insert(arr[i]);
    }
    for(int i = arr.length-1; i >=0 ; i--){
        arr[i] = heap.deleteMax();
    }
}
// 上面的那个堆排序需要先将数组中的数存到堆中，这里的时间复杂度是n(log2n)，
// 可以通过改变建堆的过程从而将建堆的时间复杂度变为O(n)级别。
//堆排序O(n)+O(nlog2n)
public void heapSort2(int arr[]){
    MaxHeap maxHeap = new MaxHeap(arr,100);
    for(int i=arr.length-1; i >= 0 ; i--){
        arr[i] = maxHeap.deleteMax();
    }
}

快速排序要比堆排序性能好

  1. 堆排序数据访问的方式没有快排友好。对于快速排序来说，数据是顺序访问的。而对于堆排序来说，数据是跳着访问的。 比如，堆排序中，最重要的一个操作就是数据的堆化。比如下面这个例子，对 堆顶节点进行堆化，会依次访问数组下标是$1，2，4，8$的元素，而不是像快速排序那样，局部顺序访问，所以，这样对CPU缓存是不友好的。

  2. 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。

我们在讲排序的时候，提过两个概念，有序度和逆序度。对于基于比较的排序算法来说，整个排序过程就是由两个基本的操作组成的，比较和交换（或移动）。快速排序数据交换的次数不会比逆序度多。

但是堆排序的第一步是建堆，建堆的过程会打乱数据原有的相对先后顺序，导致原数据的有序度降低。比如，对于一组已经有序的数据来说，经过建堆之后，数 据反而变得更无序了。