Fork me on GitHub

排序算法(三)

前言

上篇文章排序算法(二)我们介绍了10种排序算法,今天我们再来介绍一些其他的排序算法。

正文

今天我们介绍7种排序算法,它们如下:

Sort NameTime(Best)Time(Average)Time(Worst)MemoryStable
BinaryTreeSortO(n)O(n * log n)O(n * log n)O(n)Yes
FlashSortO(n)O(n+k)O(n^2)O(n+k)Yes
PatienceSortO(n)O(n * log n)O(n * log n)O(n)No
StoogeSort————O(n^(log 3 / log 1.5))O(n)Yes
PancakeSortO(n)O(n^2)O(n^2)O(n)No
InPlaceMergeSort————O(n * (log n)^2)O(1)Yes
StrandSortO(n)O(n^2)O(n^2)O(n)Yes

我们分别来看下。

二叉排序树排序(BinaryTreeSort)

简介及原理

二叉排序树排序(BinaryTreeSort),其原理是利用二叉树的特性,较小值依次比较放在树的左边,较大值依次比较放在树的右边,形成一个数据二叉树,然后将数据从左到右遍历出来即可。

算法描述

  1. 对于待排序数组array,构建一个二叉树tree,根节点可以取array[0],此时根节点的左右叶子节点为null;
  2. 对数组里每个元素,放入二叉树tree,如果小于根节点数值,应该放到左边,左边如果没有节点就创建一个并放入,如果有则需要比较其节点值和放入值大小,进而确定要放置的位置;右边同理;
  3. 进而我们会得到一个二叉树,我们从左向右遍历二叉树,就可以得到有序的数组。

动图演示

upload successful

代码实现

相关代码如下:

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
public class BinaryTreeSort {
public static int[] binaryTreeSort(int[] array){
BinaryNode root = new BinaryNode(array[0], null, null);
for(int i=1; i<array.length; i++){
root.addChild(array[i]);
}
List<Integer> list = BinaryNode.getSortedList(root);
int[] result = new int[list.size()];
for (int i=0;i<list.size();i++) {
result[i] = list.get(i);
}
return result;
}

public static void main(String[] args) {
int[] a = new int[100];
Random r = new Random();
for (int i=0;i<a.length;i++){
a[i] = r.nextInt(10000);
}
System.out.println("BinaryTreeSort排序前:");
System.out.println(Arrays.toString(a));
int [] s = binaryTreeSort(a);
System.out.println("BinaryTreeSort排序后:");
System.out.println(Arrays.toString(s));
}
}
/**
* 二叉树节点类
*/
class BinaryNode{
/**
* 节点当前值
*/
private int value;
/**
* 左节点
*/
private BinaryNode lChild;
/**
* 右节点
*/
private BinaryNode rChild;
/**
* 排序结果集
*/
private static List<Integer> resultList = new ArrayList<>();

public BinaryNode(int value, BinaryNode l, BinaryNode r){
this.value = value;
this.lChild = l;
this.rChild = r;
}
public BinaryNode getLChild() {
return lChild;
}
public BinaryNode getRChild() {
return rChild;
}
public int getValue() {
return value;
}

public static List<Integer> getSortedList(BinaryNode root) {
iterate(root);
return resultList;
}
/**
* 添加一个节点
* **/
public void addChild(int n){
if(n < value){
if(lChild!=null){
lChild.addChild(n);
}else{
lChild = new BinaryNode(n, null, null);
}
}else{
if(rChild!=null){
rChild.addChild(n);
}else{
rChild = new BinaryNode(n, null, null);
}
}
}
/**
* 迭代赋值
* @param root
*/
public static void iterate(BinaryNode root){
if(root.lChild!=null){
iterate(root.getLChild());
}
resultList.add(root.getValue());
if(root.rChild!=null){
iterate(root.getRChild());
}
}
}

其他注意事项

  • 这儿是否可以使用平衡二叉树?

    可以,但平衡二叉树可以提高单个数据查找性能,我们这儿需要处理全部数据,同时平衡二叉树插入时涉及到树的旋转变化等,因此使用平衡二叉树的效率不一定比普通二叉树效率高。

    某些情况下,使用平衡二叉树递归取值的栈深度会比普通二叉树要低。

  • 该排序算法的时间复杂度:

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

    时间复杂度(平均):O(n * log n)

    时间复杂度(最差):O(n * log n)

  • 该排序算法空间复杂度:O(n)

  • 该排序算法是稳定排序算法。

闪电排序(FlashSort)

简介及原理

闪电排序(FlashSort)是由Karl-Dietrich Neubert在1997年发展而来的一种排序算法,并且在欧洲理论计算机协会的新闻简报上发表了该算法。

该算法类似于桶排序,主要改进了对使用桶的预测。

我们知道,对于桶排序,我们首先要确定桶的数量,不能太多或者太少。

太多的话,桶中元素少,或者无用桶多,会浪费内存;太少的话,桶中元素多,每个桶中这些元素进行由大到小(或者由小到大)排序时就会比较耗时。(可参考HashMap理解桶排序)

因此桶的数量对排序性能的影响也不能忽视,FlashSort就是可以提前预知桶的大致数量及元素在桶中的位置,使其元素尽量利用每个桶,然后进行排序的。

FlashSort是如何预测的呢?

我们知道,桶排序桶的数量bucketCount一般为 INT[(Amax - Amin)/Asize] +1,对于如下数组[1,152,1000,8763,3,88,1000001,666,9999,100],根据公式可以算出需要的桶的数量为(1000001-1)/10 +1 = 1000001。

显然浪费了大量桶(内存),当然bucketCount也可以设置为数组长度,但是如果有一个长度为100000的数组,数组元素只有[0-9]之间的元素,我们显然设置的bucketCount也会不合适。

你一定会说可以取 INT[(Amax - Amin)/Asize] +1 或者数组长度中的最小值啊,哈哈,当然这么想也正确,但是即使这样,桶排序也不一定会完全把所有的桶充分利用,也会出现空桶的情况,因而造成内存浪费。

FlashSort就可以充分利用桶吗? 是的,其数据的位置主要依赖一个公式,如下:

K(Ai) = 1 + INT[ (m-1)(Ai-Amin)/(Amax-Amin) ]

这个公式可以算出数组的Ai项在桶中的位置。

比如如下数组[6,2,4,1,5,9],m如果取数组长度的话 m=6(也表明桶的数量为m个),我们可以算出:

  • K(6) = 1 + 5 * 5/8 = 4
  • K(2) = 1 + 5 * 1/8 = 1
  • K(4) = 1 + 5 * 3/8 = 2
  • K(1) = 1 + 5 * 0/8 = 1
  • K(5) = 1 + 5 * 4/8 = 3
  • K(9) = 1 + 5 * 8/8 = 6

可以看到极大的利用了桶,在数据量较多的情况下,与桶排序相比效果更明显。

可以看到上面我们m (桶的数量)取的数组长度,这显然不太合理,我们m一般取 0.1n (n代表数组长度),当m<1 时,m=1。这样保证桶尽量少的浪费的前提下,尽可能减少桶的使用数量。

如果数组过大,m过小,会导致每个桶内数据多,排序浪费较多时间;如果数据少,但桶较多,会导致内存浪费。所以对于具体数组,m也可以自己指定,以达到排序效率和空间的优化平衡。

算法描述

  • 构建M个桶,M可以取0.1N (N数组长度)或者自定义;
  • 根据FlashSort的K(Ai)计算公式,找到每个元素所在的桶,放入元素;
  • 对于每个桶中的元素,如果元素个数大于等于2,需要进行内部排序;
  • 从小到大(或者大到小)依次取出桶中元素,得到有序数组。

动图演示

upload successful

代码实现

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
public class FlashSort {
public static void flashSort(int[] array) {
//桶排序
partialFlashSort(array, array.length);
//桶内元素使用插入排序
insertionSort(array);
}
private static void partialFlashSort(int[] a, int n) {
//m值,取0.1n,也可以自由指定
int bucketSize = n / 10;
if (bucketSize < 1) {
bucketSize = 1;
}
//构建bucket
int[] buckets = new int[bucketSize];
int i, j, k;
int min = a[0];
int maxIndex = 0;

//找到最大最小值
for (i = 1; i < n; i++) {
if (a[i] < min) {
min = a[i];
}
if (a[i] > a[maxIndex]) {
maxIndex = i;
}
}
if (min == a[maxIndex]) {
return;
}
//计算系数
double c1 = ((double) bucketSize - 1) / (a[maxIndex] - min);
//计算元素位置
for (i = 0; i < n; i++) {
k = (int) (c1 * (a[i] - min));
buckets[k]++;
}
for (k = 1; k < bucketSize; k++) {
buckets[k] += buckets[k - 1];
}
//元素入桶
int hold = a[maxIndex];
a[maxIndex] = a[0];
a[0] = hold;

int nmove = 0;
int flash;
j = 0;
k = bucketSize - 1;

while (nmove < n - 1) {
while (j > (buckets[k] - 1)) {
j++;
k = (int) (c1 * (a[j] - min));
}
flash = a[j];
while (j != buckets[k]) {
k = (int) (c1 * (flash - min));
hold = a[buckets[k] - 1];
a[buckets[k] - 1] = flash;
flash = hold;
buckets[k]--;
nmove++;
}
}
}
private static void insertionSort(int[] a) {
int i, j, hold;
for (i = a.length - 3; i >= 0; i--) {
if (a[i + 1] < a[i]) {
hold = a[i];
j = i;
while (a[j + 1] < hold) {
a[j] = a[j + 1];
j++;
}
a[j] = hold;
}
}
}

public static void main(String[] args) {
int[] a = new int[100];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(10000);
}
System.out.println("FlashSort排序前:");
System.out.println(Arrays.toString(a));
flashSort(a);
System.out.println("FlashSort排序后:");
System.out.println(Arrays.toString(a));
}
}

其他注意事项

  • 可以看到FlashSort只是优化了桶排序的元素存放桶的位置,使其尽量均匀分布于每个桶,而且选择合适的m值(桶数量)也是至关重要的(无论FlashSort或者桶排序);
  • 该算法时间复杂度:

    • 时间复杂度(最好):O(n)
    • 时间复杂度(平均):O(n+k)
    • 时间复杂度(最差):O(n^2)
  • 该算法空间复杂度:O(n+k)

  • 该算法为稳定排序算法。

耐心排序(PatienceSort)

简介及原理

耐心排序(PatienceSort)是将数组的元素分类成很多堆再串接回数组的一种排序算法。受到纸牌游戏的启发和命名。

我们在Windows系统上一定玩过纸牌游戏吧,我们知道,无序的纸牌要变为有序,我们需要将无序的纸牌通过操作进行有序分堆,最后在将这些堆纸牌合并生成有序的结果。

我们后面的动图也会模拟纸牌来看下耐心排序的执行过程。

算法描述

  1. 创建一个堆数组;
  2. 比较当前指向的元素和每个堆的第一个元素;
  3. 若当前元素比所有堆的第一个元素大,创建新的堆并加入到堆数组中;
  4. 如果当前元素比堆内的第一个元素小,就放入该堆头部作为新的第一个元素;
  5. 分类完后将每个堆有两种处理方式,可以通过合并后使用插入排序形成有序数列,也可以使用优先级队列依次取出元素完成排序。

PS:其实第4步,如果元素找到了多个符合条件的堆,可以放到任意一个堆里作为首元素。

动图演示

upload successful

代码实现

这里的代码有两个,都比较好理解,第一个是将生成的堆合并,然后使用插入排序处理;第二个是生成堆后,使用优先级队列处理堆中数据。

大家都可以看下。

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
public class PatienceSort {
public static void patienceSort(int[] theArray) {
List<List<Integer>> newList = new ArrayList<>();
for (int i = 0; i < theArray.length; i++) {
List<Integer> bucketList = new ArrayList<>();
//先开始创建一个堆
if (i == 0) {
bucketList.add(theArray[i]);
newList.add(bucketList);
} else {
boolean isOk = false;
for (int j = 0; j < newList.size(); j++) {
//如果当前元素比堆内的第一个元素小,就放入该堆头部作为新的第一个元素,然后执行下个元素判断
//这儿我们直接放到第一个符合的堆里了,其实放到其它符合的也是可以的,放到最后一个符合的堆里还可以解决子序列问题
if (theArray[i] < (int) ((List) newList.get(j)).get(0)) {
(newList.get(j)).add(0, theArray[i]);
isOk = true;
break;
}
}
//如果当前元素比所有堆内的第一个元素大,就创建个新堆,把元素作为第一个元素放进去
if (!isOk) {
bucketList.add(theArray[i]);
newList.add(bucketList);
}
}
}
////生成的堆合并,而后使用插入排序
int q = 0;
for (int m = 0; m < newList.size(); m++) {
for (int n = 0; n < (newList.get(m)).size(); n++) {
theArray[q] = (int) ((List) newList.get(m)).get(n);
q++;
}
}
//插入排序
int tmp;
int j;
for (int i = 1; i < theArray.length; i++) {
tmp = theArray[i];
for (j = i - 1; j >= 0 && theArray[j] > tmp; j--) {
theArray[j + 1] = theArray[j];
}
theArray[j + 1] = tmp;
}
}

public static void main(String[] args) {
int[] a = new int[200];
Random r = new Random();
for (int i=0;i<a.length;i++){
a[i] = r.nextInt(10000);
}
System.out.println("PatienceSort排序前:");
System.out.println(Arrays.toString(a));
patienceSort(a);
System.out.println("PatienceSort排序后:");
System.out.println(Arrays.toString(a));
}

public static <E extends Comparable<? super E>> void patienceSort(E[] n) {
List<Pile<E>> piles = new ArrayList<Pile<E>>();
//生成堆
for (E x : n) {
Pile<E> newPile = new Pile<E>();
newPile.push(x);
int i = Collections.binarySearch(piles, newPile);
if (i < 0){
i = ~i;
}
if (i != piles.size()) {
piles.get(i).push(x);
}else {
piles.add(newPile);
}
}
//使用优先级队列处理数据
PriorityQueue<Pile<E>> heap = new PriorityQueue<Pile<E>>(piles);
for (int c = 0; c < n.length; c++) {
Pile<E> smallPile = heap.poll();
n[c] = smallPile.pop();
if (!smallPile.isEmpty()) {
heap.offer(smallPile);
}
}
assert(heap.isEmpty());
}
private static class Pile<E extends Comparable<? super E>> extends Stack<E> implements Comparable<Pile<E>> {
@Override
public int compareTo(Pile<E> y) { return peek().compareTo(y.peek()); }
}
}

其他注意事项

  • 该算法有一个变体,可以有效地计算给定数据中的最长增长子列和最长递减子列。比如有个数组[7,8,2,3,5,8,6,4,3,1,5,9],我们可以看到最长增长子列为[2,3,5,8],最长递减子列为[8,6,4,3,1]

    我们使用耐心排序算法来看下:

    算法描述的PS部分:如果元素找到了多个符合条件的堆,可以放到任意一个堆里作为首元素,我们在这儿放到最后一个符合的堆中。

    • 根据耐心排序,我们可以把[7,8,2,3,5,8,6,4,3,1,5,9]数组按照上述算法分为如下堆数组: [3,7],[2,8],[5],[1,3,4,6,8],[5],[9]。显而易见最长递减子列为[1,3,4,6,8]的反向序列。
    • 我们对于上述所讲的算法,也可以反过来,即比较当前指向的元素和每个堆的第一个元素,如果当前元素大于该堆第一个元素,在进行放入操作,这样可以得到如下堆数组:[8,7],[8,5,3,2],[6],[4],[3],[9,5,1]。显而易见[8,5,3,2]是最长递增子列的反向序列。
  • 该排序算法时间复杂度:

    • 时间复杂度(最好):O(n)
    • 时间复杂度(平均):O(n * log n)
    • 时间复杂度(最差):O(n * log n)
  • 该排序算法空间复杂度:O(n)

  • 该排序算法为不稳定排序算法

臭皮匠排序(StoogeSort)

简介及原理

臭皮匠排序(StoogeSort)是一种低效的递归排序算法,是由Howard、Fine等教授提出的所谓“漂亮的”排序算法,代码很漂亮但是很耗时。

臭皮匠排序翻译的由来:因为这个排序和3有很大关系(3个臭皮匠)。

我们来看下算法描述:

算法描述

  1. 如果最后一个值小于第一个值,则交换这两个数;
  2. 如果当前集合元素数量大于等于3:
    1. 使用臭皮匠排序前2/3的元素;
    2. 使用臭皮匠排序后2/3的元素;
    3. 再次使用臭皮匠排序前2/3的元素。

动图演示

upload successful

代码实现

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
public class StoogeSort {
public static void stoogeSort(int[] array) {
stoogeSort(array, 0, array.length - 1);
}
private static void stoogeSort(int[] array, int low, int high) {
//如果第一个数大于最后一个数,交换位置
if (array[low] > array[high]) {
swap(array, low, high);
}
if (low + 1 >= high){
return;
}
int third = (high - low + 1) / 3;
//排序前2/3数组元素
stoogeSort(array, low, high - third);
//排序后2/3数组元素
stoogeSort(array, low + third, high);
//排序前2/3数组元素
stoogeSort(array, low, high - third);
}
private static void swap(int[] a, int b, int c) {
if (b == c){
return;
}
int temp = a[b];
a[b] = a[c];
a[c] = temp;
}

public static void main(String[] args) {
int[] a = new int[100];
Random r = new Random();
for (int i=0;i<a.length;i++){
a[i] = r.nextInt(10000);
}
System.out.println("StoogeSort排序前:");
System.out.println(Arrays.toString(a));
stoogeSort(a);
System.out.println("StoogeSort排序后:");
System.out.println(Arrays.toString(a));
}
}

其他注意事项

  • 该算法是一种低效的递归排序算法,甚至慢于冒泡排序,相比经典排序,臭皮匠排序性能十分差;
  • 该算法的时间复杂度:

    时间复杂度(最差):O(n^(log 3 / log 1.5))

  • 该算法的空间复杂度:O(n)

  • 该排序算法为稳定排序算法。

煎饼排序(PancakeSort)

简介及原理

煎饼排序(PancakeSort),我们对于排序数组,可以看成一叠大大小小的煎饼,假设我们有一把锅铲,可以每次从任意位置铲起上方全部煎饼并翻面,最终我们可以实现按煎饼大小进行排序的煎饼堆。

比如对于一个数组 [3,1,3,6,8,2,7,1],我们把它看成煎饼堆,则我们使用“锅铲”翻转的过程如下:

  1. [3,1,3,6,8,2,7,1] 初始化
  2. [8,6,3,1,3,2,7,1] 先把“大煎饼”8翻转到上面
  3. [1,7,2,3,1,3,6,8] 再把“大煎饼”8翻转到下面
  4. [7,1,2,3,1,3,6,8] 再把“第二大煎饼”7翻转到上面
  5. [6,3,1,3,2,1,7,8] 再把7翻转到下面
  6. [1,2,3,1,3,6,7,8] 再把6翻转到下面
  7. [3,2,1,1,3,6,7,8] 再把3翻转到上面
  8. [1,1,2,3,3,6,7,8] 再把3翻转到下面,完成排序

算法描述

  1. 对于待排序数组,找到最大值最小值及索引;
  2. 将最大值翻转到顶部,在翻转到数组底部;
  3. 此时再从未排序数组里找到最大值及索引,重复1、2过程。

动图演示

upload successful

代码实现

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
public class PancakeSort {
/**
* 翻转
* @param n
* @param heap
*/
private static void flip(int n, int[] heap) {
for (int i = 0; i < (n + 1) / 2; ++i) {
int tmp = heap[i];
heap[i] = heap[n - i];
heap[n - i] = tmp;
}
}
/**
* 获取最小最大值数组
* @param n
* @param heap
* @return
*/
private static int[] minmax(int n, int[] heap) {
int xm, xM;
xm = xM = heap[0];
int posm = 0, posM = 0;
for (int i = 1; i < n; ++i) {
if (heap[i] < xm) {
xm = heap[i];
posm = i;
} else if (heap[i] > xM) {
xM = heap[i];
posM = i;
}
}
return new int[]{posm, posM};
}
private static void sort(int n, int dir, int[] heap) {
if (n == 0) {
return;
}
int[] mM = minmax(n, heap);
int bestXPos = mM[dir];
int altXPos = mM[1 - dir];
boolean flipped = false;

if (bestXPos == n - 1) {
--n;
} else if (bestXPos == 0) {
flip(n - 1, heap);
--n;
} else if (altXPos == n - 1) {
dir = 1 - dir;
--n;
flipped = true;
} else {
flip(bestXPos, heap);
}
sort(n, dir, heap);
if (flipped) {
flip(n, heap);
}
}
public static void pancakeSort(int[] array) {
sort(array.length, 1, array);
}

public static void main(String[] args) {
int[] a = new int[100];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(10000);
}
System.out.println("PancakeSort排序前:");
System.out.println(Arrays.toString(a));
pancakeSort(a);
System.out.println("PancakeSort排序后:");
System.out.println(Arrays.toString(a));
}
}

其他注意事项

  • 煎饼排序的一个问题变种为焦煎饼排序,即对于我们的煎饼,每张煎饼都有一面是烤焦的,最终除了按照大小排序以外还要让所有焦面向下;

    焦煎饼问题: 比如对于上面的[3,1,3,6,8,2,7,1]数组,它们的右面都是“焦”的,我们按照上面的步骤走,会发现当执行到第4步得到[7,1,2,3,1,3,6,8],其中[7,1][3,1,3,6,8]是焦面向下,[2]是焦面向上的,我们执行第5步把7翻转到底下时,7的焦面就向上了,就不符合要求了,因此这时候我们需要在单独翻转一次“煎饼”7,然后把[7,1,2,3,1,3,6]整个翻转一下。

    关于这部分的代码我就略过了,有兴趣的同学可以自己写一下。关于如何表示焦煎饼的正反两面也可以思考下。

  • 煎饼排序的时间复杂度:

    • 时间复杂度(最好):O(n)
    • 时间复杂度(平均):O(n^2)
    • 时间复杂度(最差):O(n^2)
  • 该排序算法的空间复杂度:O(n)

  • 该排序算法是一种不稳定排序算法。

原地归并排序(InPlaceMergeSort)

简介及原理

原地归并排序(InPlaceMergeSort)是归并排序(MergeSort)的一个变种。

我们知道,当使用归并排序时,我们需要借助辅助数组。原地归并排序可以使我们不使用辅助数组即可完成目标数组的排序。

算法描述

  1. 将长度为n的数组分为两个n/2的子序列;
  2. 对两个子序列分别进行归并排序;
  3. 将两个排序好的子序列合并成一个最终的排序序列。

动图演示

upload successful

代码实现

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
public class InPlaceMergeSort {
public static void inPlaceMergeSort(int[] array) {
inPlaceMergeSort(array, 0, array.length - 1);
}
private static void inPlaceMergeSort(int[] array, int first, int last) {
int mid, lt, rt;
int tmp;
if (first >= last) {
return;
}
mid = (first + last) / 2;
inPlaceMergeSort(array, first, mid);
inPlaceMergeSort(array, mid + 1, last);
lt = first;
rt = mid + 1;
// One extra check: can we SKIP the merge?
if (array[mid] <= array[rt]) {
return;
}
while (lt <= mid && rt <= last) {
// Select from left: no change, just advance lt
if (array[lt] <= array[rt]) {
lt++;
// Select from right: rotate [lt..rt] and correct
} else {
// Will move to [lt]
tmp = array[rt];
System.arraycopy(array, lt, array, lt + 1, rt - lt);
array[lt] = tmp;
// EVERYTHING has moved up by one
lt++;
mid++;
rt++;
}
}
// Whatever remains in [rt..last] is in place
}

public static void main(String[] args) {
int[] a = new int[100];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(10000);
}
System.out.println("InPlaceMergeSort排序前:");
System.out.println(Arrays.toString(a));
inPlaceMergeSort(a);
System.out.println("InPlaceMergeSort排序后:");
System.out.println(Arrays.toString(a));
}
}

其他注意事项

  • 该排序的时间复杂度与归并排序相当:

    时间复杂度(最差):O(n * (log n)^2)

  • 由于未使用辅助数组,因此该排序的空间复杂度为:O(1)

  • 该排序为稳定排序算法。

Strand排序(StrandSort)

简介及原理

Strand排序(StrandSort)又称串排序、线排序,其原理主要和子有序数组有关。

这儿的子有序数组是这样定义的:比如一个数组[5,3,7,8,2,1,9],则它的子有序数组为[5,7,8,9],此时原数组变为[3,2,1],其中子有序数组为[3],依次类推……得到最终子有序数组为[5,7,8,9],[3],[2],[1]。

得到子有序数组后将它们合并为新的有序数组。

比如数组[7,9,6,3,2,5,8,1],我们使用Strand排序:

  • [7,9,6,3,2,5,8,1] 得到子有序数组和另一个子数组 [7,9][6,3,2,5,8,1];
  • [6,3,2,5,8,1] 得到子有序数组和另一个子数组 [6,8][3,2,5,1] ,将[7,9]和[6,8]有序合并得到[6,7,8,9];
  • [3,2,5,1] 继续得到 [3,5][2,1], [3,5]与[6,7,8,9]合并得到[3,5,6,7,8,9];
  • [2,1]得到[2][1],继续合并得到[1,2,3,5,6,7,8,9];
  • [1,2,3,5,6,7,8,9]即为要求的有序数组。

算法描述

  1. 对于待排序数组,取首元素为基础数;
  2. 向后寻找子有序数组,原数组变为一个子有序数组和一个新的子数组;
  3. 对于新的子数组,继续1、2步逻辑,得到新的子子有序数组和另一个新的子子数组;
  4. 将子有序数组和子子有序数组合并成有序数组,新的子子数组重复上述逻辑。

动图演示

upload successful

代码实现

这儿我们借助LinkedList实现StrandSort

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
public class StrandSort {
private static <E extends Comparable<? super E>> LinkedList<E> strandSort(LinkedList<E> list) {
if (list.size() <= 1) {
return list;
}
LinkedList<E> result = new LinkedList<>();
while (list.size() > 0) {
LinkedList<E> sorted = new LinkedList<>();
//same as remove() or remove(0)
sorted.add(list.removeFirst());
for (Iterator<E> it = list.iterator(); it.hasNext(); ) {
E elem = it.next();
if (sorted.peekLast().compareTo(elem) <= 0) {
//same as add(elem) or add(0, elem)
sorted.addLast(elem);
it.remove();
}
}
result = merge(sorted, result);
}
return result;
}

private static <E extends Comparable<? super E>> LinkedList<E> merge(LinkedList<E> left, LinkedList<E> right) {
LinkedList<E> result = new LinkedList<>();
while (!left.isEmpty() && !right.isEmpty()) {
//change the direction of this comparison to change the direction of the sort
if (left.peek().compareTo(right.peek()) <= 0) {
result.add(left.remove());
} else {
result.add(right.remove());
}
}
result.addAll(left);
result.addAll(right);
return result;
}

public static void strandSort(int[] array){
LinkedList<Integer> linkedList = new LinkedList<>();
Arrays.stream(array).forEach(e -> linkedList.add(e));
List<Integer> list = strandSort(linkedList);
assert list.size() == array.length;
for(int i=0;i<array.length;i++){
array[i] = list.get(i);
}
}

public static void main(String[] args) {
int[] a = new int[100];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(10000);
}
System.out.println("StrandSort排序前:");
System.out.println(Arrays.toString(a));
strandSort(a);
System.out.println("StrandSort排序后:");
System.out.println(Arrays.toString(a));
}
}

其他注意事项

  • 该排序算法的时间复杂度如下:

    • 时间复杂度(最好): O(n)
    • 时间复杂度(平均): O(n^2)
    • 时间复杂度(最差): O(n^2)
  • 该排序算法的空间复杂度为: O(n)

  • 该排序算法是稳定排序算法。

总结

今天我们了解了7种排序算法,这7种排序算法还是比较好理解的,我们可以看到,各个排序都有各自的一些优点(某些个例除外),比如有的时间复杂度要低些,但空间复杂度要高些;有的空间复杂度低,但是时间复杂度要高些;还有一些数据量小的情况下,可能经典排序(冒泡、插入、选择)效率要高,因此可以选择一个合适的阈值,当要排序的数组部分数据量小时,我们可以使用它们代替。

比如归并排序,如果数组较小,就没必要继续归并,而采用插入排序可能会提高效率等。

所以后面我们会介绍一些经典的混合排序,还有一些基于某些原理的排序等。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力!
0%