概要

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，

而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

用一张图概括：

排序算法稳定性图片

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。

希尔排序 线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

  • n：数据规模
  • k："桶"的个数
  • In-place：占用常数内存，不占用额外内存
  • Out-place：占用额外内存
  • 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

直接插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，

因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，

它的工作原理是通过构建有序序列，对于未排序数据，

在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入(折半插入)。

算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

由于没有改变两个元素的相对顺序，所以插入排序是稳定的）

跟斗地主一样,左起第一张牌当成有序序列，第二张牌到最后一张当成是无序序列。

从头到尾依次扫描未排序的牌，将扫描到的每一张牌插入到有序序列的适当位置。

动图演示

插入排序

Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int[] insertSort(int[] arr) {
    //第一张牌有序，所以从第二张牌开始往前比较
    for (int i = 1; i < arr.length; i++) {
        //把这张牌拿在手里
        int temp = arr[i];
    //    j=i-1是手牌的前一张，只要还没到最左边的牌，就一直比较下去
        int j;
        for (j = i - 1; j >= 0; j--) {
            //如果前面的牌比手牌大，那就把前面的牌往后移
            if (arr[j] > temp) {
                arr[j + 1] = arr[j];
            } else
                break;
        }
        //j = j + 1;
        //arr[j] = temp;
        arr[++j] = temp;
    }
    return arr;
}

排序过程及效率

直接插入排序

直接插入排序的优化——折半插入排序

查找采用折半查找方法，称为二分插入排序或折半插入排序。

二分插入排序算法的原理和插入排序算法原理一样，都是把要插入的数作为手牌，

只不过优化了查找要插入位置的算法进行二分，与中间(m=(low+hgih)/2)的数值作比较，

小则high=m-1，反之low=m+1,一直到low>high,high+1为要插入的位置。

学会这种方法，斗地主插牌就比别人快啦

Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int[] binInsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int low = 0;
            int high = i - 1;
            int mid;
            while (low <= high) {
                mid = (low + high) / 2;
                if (arr[mid] <= temp)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            high++;
            for (int j = i; j >= high + 1; j--) {
                arr[j] = arr[j - 1];
            }
            arr[high] = temp;
        }
        return arr;
    }

排序过程及效率

折半插入排序

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，

待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

算法步骤

将n个元素分成d个组：

{R[0] ,R[d], R[2d], ··· ,R[kd] }

{R[1] ,R[1+d], R[1+2d], ··· ,R[1+kd] }

···

{R[d-1] ,R[2d-1], R[3d-1], ··· ,R[(k+1)d-1]}

相距d个位置的元素分为一组，然后在组内完成排序

① d=arr.length/2

② 将排序序列分为d个组，在组内进行直接插入排序

③ 递减d=d/2，重复②，直到d=0

由于算法最后一趟对所有元素进行了直接插入排序，所以结果是一定正确的

由于不同组别可能存在两个或若干个相同的元素，在各自组内直接插入排序之后，

可能会导致相等元素在排序之后的相对位置发生改变，所以希尔排序是不稳定的。

动图演示

希尔排序

Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void shellSort(int[] arr) {
    int length = arr.length;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

排序过程及效率

希尔排序

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，

一次比较两个元素，如果他们的顺序错误就把他们交换过来。

走访数列的工作是重复地进行直到没有再需要交换，

也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。

这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图演示

冒泡动图

Java代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int[] bubbleSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            /*
                设定一个标记，若为true，则表示此次循环没有进行交换，
                也就是待排序列已经有序，排序已经完成。
                例如已经顺序排好的数列。
            */
            boolean flag = true;
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    CreatStuScore.swap(arr, j, j + 1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
        return arr;
    }

排序过程及效率

冒泡排序

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。

所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

动图演示

选择排序

Java代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int[] selectSort(int[] arr) {
        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }
            int temp=arr[min];
            arr[min]=arr[i];
            arr[i]=arr[min];
        }
        return arr;
    }

排序过程及效率

选择排序

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。

该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法步骤

  • 将序列中待排数字分为若干组，每个数字分为一组

  • 将若干组两两合并，保证合并后的组是有序的

  • 重复第二步操作直至剩下一组，排序完成

算法步骤图1

算法步骤图2

动图演示

归并排序

Java实现代码

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
//归并排序
    public static int[] mergeSortZ(int[] arr) {
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int[] temp = Arrays.copyOf(arr, arr.length);
        if (temp.length < 2) {
            return temp;
        }
        int mid = (int) Math.floor(temp.length / 2);
        //分而治之的分
        int[] left = Arrays.copyOfRange(temp, 0, mid);
        int[] right = Arrays.copyOfRange(temp, mid, temp.length);
        //递归调用，将左右子序列继续分为两组，直至每组只有一个元素
//        System.out.println(Arrays.toString(arr));
        return mergeZ(mergeSortZ(left), mergeSortZ(right));
    }

    private static int[] mergeZ(int[] left, int[] right) {

        int[] result = new int[left.length + right.length];
        int i = 0;

        while (left.length > 0 && right.length > 0) {
            //比较两个子序列中的第一个元素，将较小元素加入到结果序列中
            if (left[0] < right[0]) {
                result[i++] = left[0];
                //此步操作相当于剔除left序列中的第一个元素，从而诞生新的第一个元素
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }
        //当一方序列的元素全部加入到结果序列中后，将剩余子序列的元素全部加入到结果序列中
        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }
        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }

排序过程及效率

归并排序

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。

在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，

快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）

可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，

就是快，而且效率高！它是处理大数据最快的排序算法之一了。

算法步骤

  • 选定Pivot中心轴
  • 将大于Pivot的数字放在Pivot的右边
  • 将小于Pivot的数字放在Pivot的左边
  • 分别对左右子序列重复前三步操作

动图演示

快速排序

Java代码实现

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
public static int[] quickSortZ(int[] arr, int L, int R) {
        if (L >= R)
            return arr;
        int left = L, right = R;
        /*
            基本思想
            1.选定Pivot中心轴
            2.将大于Pivot的数字放在Pivot的右边
            3.将小于Pivot的数字放在Pivot的左边
            4.分别对左右子序列重复前三部操作。
         */
        int pivot = arr[left];
        while (left < right) {
            //右下标对应的元素若大于pivot，则不进行操作，右下标自减
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            //退出上面的while循环，代表右下标遇到了比pivot小的元素，将该元素放到左边
            if (left < right) {
                arr[left] = arr[right];
            }
            //左右下标 双向奔赴
            //左下标对应的元素若小于pivot，则不进行操作，左下标自增
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //退出上面的while循环，代表左下标遇到了比pivot大的元素，将该元素放到右边
            if (left < right) {
                arr[right] = arr[left];
            }
            //左右下标 双向奔赴 将pivot放在左右下标交汇点
            if (left >= right) {
                arr[left] = pivot;
            }
        }
//        System.out.println(Arrays.toString(arr));
        //递归调用，分别对左右子序列重复进行上述操作
        quickSortZ(arr, L, right - 1);
        quickSortZ(arr, right + 1, R);
        return arr;
    }


排序过程及效率

快速排序

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

本文采用的大顶堆。

算法步骤

  1. 创建一个堆 H[0 ~ arr.length-1]；

  2. 把堆首（最大值）和堆尾互换；

  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

  4. 重复步骤 2，直到堆的尺寸为 1。

动图演示

堆排序动画

Java代码实现

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
// 堆排序
    public static int[] heapSortZ(int[] sourceArray) {

        //对传进来的数组拷贝
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        //获取传进来的数组的长度
        int len = arr.length;
        //以该数组来建一个堆
        buildMaxHeapZ(arr, len);
        //将堆尾元素和堆首元素交换，交换到堆尾的元素已经排好序了，所以数组长度/堆长度减一
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapifyZ(arr, 0, len);
        }
        return arr;
    }

    //建立大顶堆  因为下标是从0开始 所以其实这里的len/2是最后一个非叶节点或非叶节点的下一个 但是不影响结果
    private static void buildMaxHeapZ(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapifyZ(arr, i, len);
        }
    }

    /**
     * 功能： 完成将以i对应的非叶节点的数，调整成大顶堆
     *
     * @param arr 待调整数组
     * @param i   第一个非叶节点
     * @param len 调整长度
     */
    private static void heapifyZ(int[] arr, int i, int len) {
        int left = 2 * i + 1;    //根节点下标从0开始 双亲节点下标是i 子节点下标是2i+1和2i+2
        int right = 2 * i + 2;
        int largest = i;

        //左孩子的值比爹大  那就左孩子当爹
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }
        //有孩子的值比爹大  那就有孩子当爹
        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        //如果最大值发生了变化，则可能会产生新的最大值，进行递归调用
        if (largest != i) {
            //将最大值对应的下标作为双亲结点
            swap(arr, i, largest);
            //递归调用
            heapifyZ(arr, largest, len);
        }
    }

排序过程及效率

堆排序过程及效率

Java完整代码–CreatStuScore类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import java.util.Random;

public class CreatStuScore {

    private static int[] args;

    public static int[] scores(int count) {
        args=new int[count];
        int i = 0;
        while (i < args.length) {
            args[i++] = new Random().nextInt(100);
        }
        return args;
    }

}



Java完整代码–FinalTest类

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173


import org.junit.Test;

import java.util.Arrays;

public class FinalTest {
    @Test
    public void InsertTest() {
        //排序过程
        int[] arrays = CreatStuScore.scores(10);
        System.out.println("直接插入排序前:");
        System.out.println(Arrays.toString(arrays));
        Sort.insertSort(arrays);
        System.out.println("\n直接插入排序后:");
        System.out.println(Arrays.toString(arrays));
        //性能测试
        arrays = CreatStuScore.scores(100000);
        long start = System.currentTimeMillis();
        Sort.insertSortZ(arrays);
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println();
        System.out.println("对" + arrays.length + "个随机数，直接插入排序耗时" + time + "ms");
        System.out.println();
    }

    @Test
    public void BubbleTest() {
        //排序过程
        int[] arrays = CreatStuScore.scores(10);
        System.out.println("冒泡排序前:");
        System.out.println(Arrays.toString(arrays));
        Sort.bubbleSort(arrays);
        System.out.println("\n冒泡排序后:");
        System.out.println(Arrays.toString(arrays));
        //性能测试
        arrays = CreatStuScore.scores(100000);
        long start = System.currentTimeMillis();
        Sort.bubbleSortZ(arrays);
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println();
        System.out.println("对" + arrays.length + "个随机数，冒泡插入排序耗时" + time + "ms");
        System.out.println();
    }

    @Test
    public void BinInsertSort() {
        //排序过程
        int[] arrays = CreatStuScore.scores(10);
        System.out.println("折半插入排序前:");
        System.out.println(Arrays.toString(arrays));
        Sort.binInsertSort(arrays);
        System.out.println("\n折半插入排序后:");
        System.out.println(Arrays.toString(arrays));
        //性能测试
        arrays = CreatStuScore.scores(100000);
        long start = System.currentTimeMillis();
        Sort.binInsertSortZ(arrays);
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println();
        System.out.println("对" + arrays.length + "个随机数，折半插入排序耗时" + time + "ms");
        System.out.println();
    }

    @Test
    public void ShellSort() {
        //排序过程
        int[] arrays = CreatStuScore.scores(10);
        System.out.println("希尔排序前:");
        System.out.println(Arrays.toString(arrays));
        Sort.shellSort(arrays);
        System.out.println("\n希尔排序后:");
        System.out.println(Arrays.toString(arrays));
        //性能测试
        arrays = CreatStuScore.scores(100000);
        long start = System.currentTimeMillis();
        Sort.shellSortZ(arrays);
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println();
        System.out.println("对" + arrays.length + "个随机数，希尔排序耗时" + time + "ms");
        System.out.println();

    }

    @Test
    public void SelectSort() {
        //排序过程
        int[] arrays = CreatStuScore.scores(10);
        System.out.println("选择排序前:");
        System.out.println(Arrays.toString(arrays));
        Sort.selectSort(arrays);
        System.out.println("\n选择排序后:");
        System.out.println(Arrays.toString(arrays));
        //性能测试
        arrays = CreatStuScore.scores(100000);
        long start = System.currentTimeMillis();
        Sort.selectSortZ(arrays);
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println();
        System.out.println("对" + arrays.length + "个随机数，选择排序耗时" + time + "ms");
        System.out.println();
    }

    @Test
    public void QuickSort() {
        //排序过程
        int[] arrays = CreatStuScore.scores(10);
        System.out.println("快速排序前:");
        System.out.println(Arrays.toString(arrays));
        Sort.quickSort(arrays, 0, arrays.length - 1);
        System.out.println("\n快速排序后:");
        System.out.println(Arrays.toString(arrays));
        //性能测试
        arrays = CreatStuScore.scores(100000);
        long start = System.currentTimeMillis();
        Sort.quickSortZ(arrays, 0, arrays.length - 1);
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println();
        System.out.println("对" + arrays.length + "个随机数，快速排序耗时" + time + "ms");
        System.out.println();
    }

    @Test
    public void MergeSort() {
        //排序过程
        int[] arrays = CreatStuScore.scores(16);
        System.out.println("归并排序前:");
        System.out.println(Arrays.toString(arrays));
        arrays = Sort.mergeSort(arrays);
        System.out.println("\n归并排序后:");
        System.out.println(Arrays.toString(arrays));
        //性能测试
        arrays = CreatStuScore.scores(100000);
        long start = System.currentTimeMillis();
        Sort.mergeSortZ(arrays);
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println();
        System.out.println("对" + arrays.length + "个随机数，归并排序耗时" + time + "ms");
        System.out.println();
    }

    @Test
    public void HeapSort() {
        //排序过程
        int[] arrays = CreatStuScore.scores(5);
        System.out.println("堆排序前:");
        System.out.println(Arrays.toString(arrays));
        arrays = Sort.heapSort(arrays);
        System.out.println("\n堆排序后:");
        System.out.println(Arrays.toString(arrays));
        //性能测试
        arrays = CreatStuScore.scores(100000);
        long start = System.currentTimeMillis();
        Sort.heapSortZ(arrays);
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println();
        System.out.println("对" + arrays.length + "个随机数，堆排序耗时" + time + "ms");
        System.out.println();
    }
}





Java完整代码–Sort类

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530


import java.util.Arrays;

public class Sort {

    //直接插入排序
    public static int[] insertSort(int[] arr) {
        //第一张牌有序，所以从第二张牌开始往前比较
        for (int i = 1; i < arr.length; i++) {
            //把这张牌拿在手里
            int temp = arr[i];
            int j = i;
            //从该牌的左起第一张开始比较，手牌小于左边的牌，则将左边的牌后移
            while (j > 0 && arr[j - 1] > temp) {
                arr[j] = arr[j - 1];
                j--;
            }
            if (j != i) {
                arr[j] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    //折半插入排序
    public static int[] binInsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int low = 0;
            int high = i - 1;
            int mid;
            while (low <= high) {
                mid = (low + high) / 2;
                if (arr[mid] <= temp)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            high++;
            for (int j = i; j >= high + 1; j--) {
                arr[j] = arr[j - 1];
            }
            arr[high] = temp;
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    //希尔排序
    public static int[] shellSort(int[] arr) {
        int length = arr.length;
        int temp;
        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) {
                temp = arr[i];
                int j = i - step;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    //冒泡排序
    public static int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            /*
                设定一个标记，若为true，则表示此次循环没有进行交换，
                也就是待排序列已经有序，排序已经完成。
                例如已经顺序排好的数列。
            */
            boolean flag = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    //选择排序

    public static int[] selectSort(int[] arr) {
        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int minPos = i;
            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minPos]) {
                    // 记录目前能找到的最小值元素的下标
                    minPos = j;
                }
            }
            if (i != minPos) {
                int temp = arr[minPos];
                arr[minPos] = arr[i];
                arr[i] = temp;
                System.out.println(Arrays.toString(arr));
            }
        }
        return arr;
    }


    //快速排序
    public static int[] quickSort(int[] arr, int L, int R) {
        if (L >= R)
            return arr;
        int left = L, right = R;
        /*
            基本思想
            1.选定Pivot中心轴
            2.将大于Pivot的数字放在Pivot的右边
            3.将小于Pivot的数字放在Pivot的左边
            4.分别对左右子序列重复前三部操作。
         */
        int pivot = arr[left];
        while (left < right) {
            //右下标对应的元素若大于pivot，则不进行操作，右下标自减
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            //退出上面的while循环，代表右下标遇到了比pivot小的元素，将该元素放到左边
            if (left < right) {
                arr[left] = arr[right];
            }
            //左右下标 双向奔赴
            //左下标对应的元素若小于pivot，则不进行操作，左下标自增
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //退出上面的while循环，代表左下标遇到了比pivot大的元素，将该元素放到右边
            if (left < right) {
                arr[right] = arr[left];
            }
            //左右下标 双向奔赴 将pivot放在左右下标交汇点
            if (left >= right) {
                arr[left] = pivot;
            }
        }
        System.out.println(Arrays.toString(arr));
        //递归调用，分别对左右子序列重复进行上述操作
        quickSort(arr, L, right - 1);
        quickSort(arr, right + 1, R);
        return arr;
    }


    //归并排序
    public static int[] mergeSort(int[] arr) {
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int[] temp = Arrays.copyOf(arr, arr.length);
        if (temp.length < 2) {
            return temp;
        }
        int mid = (int) Math.floor(temp.length / 2);
        //分而治之的分
        int[] left = Arrays.copyOfRange(temp, 0, mid);
        int[] right = Arrays.copyOfRange(temp, mid, temp.length);
        //递归调用，将左右子序列继续分为两组，直至每组只有一个元素
//        System.out.println(Arrays.toString(temp));
        return merge(mergeSort(left), mergeSort(right));
    }

    private static int[] merge(int[] left, int[] right) {

        int[] result = new int[left.length + right.length];
        int i = 0;

        while (left.length > 0 && right.length > 0) {
            //比较两个子序列中的第一个元素，将较小元素加入到结果序列中
            if (left[0] < right[0]) {
                result[i++] = left[0];
                //此步操作相当于剔除left序列中的第一个元素，从而诞生新的第一个元素
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }
        //当一方序列的元素全部加入到结果序列中后，将剩余子序列的元素全部加入到结果序列中
        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }
        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        System.out.println(Arrays.toString(result));
        return result;
    }


    // 堆排序
    public static int[] heapSort(int[] sourceArray) {

        //对传进来的数组拷贝
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        //获取传进来的数组的长度
        int len = arr.length;
        //以该数组来建一个堆
        buildMaxHeap(arr, len);
        //将堆尾元素和堆首元素交换，交换到堆尾的元素已经排好序了，所以数组长度/堆长度减一
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    //建立大顶堆  因为下标是从0开始 所以其实这里的len/2是最后一个非叶节点或非叶节点的下一个 但是不影响结果
    private static void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    /**
     * 功能： 完成将以i对应的非叶节点的数，调整成大顶堆
     *
     * @param arr 待调整数组
     * @param i   第一个非叶节点
     * @param len 调整长度
     */
    private static void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;    //根节点下标从0开始 双亲节点下标是i 子节点下标是2i+1和2i+2
        int right = 2 * i + 2;
        int largest = i;

        //左孩子的值比爹大  那就左孩子当爹
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }
        //有孩子的值比爹大  那就有孩子当爹
        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        //如果最大值发生了变化，则可能会产生新的最大值，进行递归调用
        if (largest != i) {
            //将最大值对应的下标作为双亲结点
            swap(arr, i, largest);
            //递归调用
            heapify(arr, largest, len);
        }
        System.out.println(Arrays.toString(arr));
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //******************************************************************************

    //直接插入排序
    public static int[] insertSortZ(int[] arr) {
        //第一张牌有序，所以从第二张牌开始往前比较
        for (int i = 1; i < arr.length; i++) {
            //把这张牌拿在手里
            int temp = arr[i];
        /*
            j=i-1就是从这张牌的前一张开始比较，
            只要还没到最左边的牌，就一直比较下去
         */
            int j;
            for (j = i - 1; j >= 0; j--) {
                //前面的牌比手牌大，那就把前面的牌往后移
                if (arr[j] > temp) {
                    arr[j + 1] = arr[j];
                } else
                    break;
            }
            arr[++j] = temp;
//            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    //折半插入排序
    public static int[] binInsertSortZ(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int low = 0;
            int high = i - 1;
            int mid;
            while (low <= high) {
                mid = (low + high) / 2;
                if (arr[mid] <= temp)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            high++;
            for (int j = i; j >= high + 1; j--) {
                arr[j] = arr[j - 1];
            }
            arr[high] = temp;
//            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    //希尔排序
    public static int[] shellSortZ(int[] arr) {
        int length = arr.length;
        int temp;
        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) {
                temp = arr[i];
                int j = i - step;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
//            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    //冒泡排序
    public static int[] bubbleSortZ(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            /*
                设定一个标记，若为true，则表示此次循环没有进行交换，
                也就是待排序列已经有序，排序已经完成。
                例如已经顺序排好的数列。
            */
            boolean flag = true;
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
//            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    //选择排序

    public static int[] selectSortZ(int[] arr) {
        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }
            int temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
//            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    //快速排序
    public static int[] quickSortZ(int[] arr, int L, int R) {
        if (L >= R)
            return arr;
        int left = L, right = R;
        /*
            基本思想
            1.选定Pivot中心轴
            2.将大于Pivot的数字放在Pivot的右边
            3.将小于Pivot的数字放在Pivot的左边
            4.分别对左右子序列重复前三部操作。
         */
        int pivot = arr[left];
        while (left < right) {
            //右下标对应的元素若大于pivot，则不进行操作，右下标自减
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            //退出上面的while循环，代表右下标遇到了比pivot小的元素，将该元素放到左边
            if (left < right) {
                arr[left] = arr[right];
            }
            //左右下标 双向奔赴
            //左下标对应的元素若小于pivot，则不进行操作，左下标自增
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //退出上面的while循环，代表左下标遇到了比pivot大的元素，将该元素放到右边
            if (left < right) {
                arr[right] = arr[left];
            }
            //左右下标 双向奔赴 将pivot放在左右下标交汇点
            if (left >= right) {
                arr[left] = pivot;
            }
        }
//        System.out.println(Arrays.toString(arr));
        //递归调用，分别对左右子序列重复进行上述操作
        quickSortZ(arr, L, right - 1);
        quickSortZ(arr, right + 1, R);
        return arr;
    }


    //归并排序
    public static int[] mergeSortZ(int[] arr) {
        //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int[] temp = Arrays.copyOf(arr, arr.length);
        if (temp.length < 2) {
            return temp;
        }
        int mid = (int) Math.floor(temp.length / 2);
        //分而治之的分
        int[] left = Arrays.copyOfRange(temp, 0, mid);
        int[] right = Arrays.copyOfRange(temp, mid, temp.length);
        //递归调用，将左右子序列继续分为两组，直至每组只有一个元素
//        System.out.println(Arrays.toString(arr));
        return mergeZ(mergeSortZ(left), mergeSortZ(right));
    }

    private static int[] mergeZ(int[] left, int[] right) {

        int[] result = new int[left.length + right.length];
        int i = 0;

        while (left.length > 0 && right.length > 0) {
            //比较两个子序列中的第一个元素，将较小元素加入到结果序列中
            if (left[0] < right[0]) {
                result[i++] = left[0];
                //此步操作相当于剔除left序列中的第一个元素，从而诞生新的第一个元素
                left = Arrays.copyOfRange(left, 1, left.length);
            } else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right, 1, right.length);
            }
        }
        //当一方序列的元素全部加入到结果序列中后，将剩余子序列的元素全部加入到结果序列中
        while (left.length > 0) {
            result[i++] = left[0];
            left = Arrays.copyOfRange(left, 1, left.length);
        }
        while (right.length > 0) {
            result[i++] = right[0];
            right = Arrays.copyOfRange(right, 1, right.length);
        }
        return result;
    }


    // 堆排序
    public static int[] heapSortZ(int[] sourceArray) {

        //对传进来的数组拷贝
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        //获取传进来的数组的长度
        int len = arr.length;
        //以该数组来建一个堆
        buildMaxHeapZ(arr, len);
        //将堆尾元素和堆首元素交换，交换到堆尾的元素已经排好序了，所以数组长度/堆长度减一
        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapifyZ(arr, 0, len);
        }
        return arr;
    }

    //建立大顶堆  因为下标是从0开始 所以其实这里的len/2是最后一个非叶节点或非叶节点的下一个 但是不影响结果
    private static void buildMaxHeapZ(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapifyZ(arr, i, len);
        }
    }

    /**
     * 功能： 完成将以i对应的非叶节点的数，调整成大顶堆
     *
     * @param arr 待调整数组
     * @param i   第一个非叶节点
     * @param len 调整长度
     */
    private static void heapifyZ(int[] arr, int i, int len) {
        int left = 2 * i + 1;    //根节点下标从0开始 双亲节点下标是i 子节点下标是2i+1和2i+2
        int right = 2 * i + 2;
        int largest = i;

        //左孩子的值比爹大  那就左孩子当爹
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }
        //有孩子的值比爹大  那就有孩子当爹
        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        //如果最大值发生了变化，则可能会产生新的最大值，进行递归调用
        if (largest != i) {
            //将最大值对应的下标作为双亲结点
            swap(arr, i, largest);
            //递归调用
            heapifyZ(arr, largest, len);
        }
    }
}