数据结构与算法 - 排序算法

  1. Prerequisite
  2. 特性
    1. 算法和空间复杂度
    2. 排序稳定性
  3. 思考
    1. Java使用什么排序?
    2. 为什么 Java 使用归并排序?

Prerequisite

排序算法的解释可参考:1.0 十大经典排序算法

特性

算法和空间复杂度

算法的时间与空间复杂度(一看就懂)

排序稳定性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 对第一个排序
# 排序前
数组1	2	1
数组2	3	2
数组3	3	4
数组4 1	3

# 排序后
# 不稳定性
数组4 1	3
数组1	2	1
数组3	3	4	<< 关注
数组2	3	2   << 关注

# 稳定性,第二个元素没有被乱序
数组4 1	3
数组1	2	1
数组2	3	2   
数组3	3	4	

参考:排序算法稳定性_百度百科

思考

Java使用什么排序?

JAVA中Arrays.sort()实现排序的具体原理是什么?

版本不同,排序也是不同。

  1. 基本类型是快速排序
  2. 对象是归并排序

为什么 Java 使用归并排序?

java中归并排序比快速排序快吗?

好像赛德维克在红色的《算法》里讲过这样一段话: Java的标准库应该是对抽象类型的数据结构使用归并排序的一种变种,而对于基本类型采取三向切分的快排变种。 大意如此。 归并有一个快排没有的优点,就是归并排序是稳定的。你对于整型数浮点数,稳定不稳定大概看不出来,对于对象么,呵呵。 另外,快排是不是最快的排序算法,这个可以去问问霍尔。

——梁川

稳定性对 对象(object) 很重要。