Saul's blog
SaulJWu
2020-12-08

排序算法

# 前言

前面学习了数组，接下来掌握一些算法。

# 排序算法

前面用二分法的前提是有序，接下来我们了解一下排序的相关知识。

# 概念

排序：假设含有n个记录的序列为{R1,R2,…,Rn}，其相应的关键字序列为{K1,K2,…,Kn}。将这些记录重新排序为{Ri1,Ri2,…,Rin}，使得相应的关键字值满足Ki1<=Ki2<=…<=Kin，这样的一种操作称为排序。

通常来说，排序的目的是快速查找。

# 优劣判断

衡量排序算法的优劣：（高效率、低存储）

  1. 时间复杂度：分析关键字的比较次数和记录的移动次数。
  2. 空间复杂度：分析排序算法中需要多少辅助内存。
  3. 稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。

# 分类

拍讯算法分类：内部排序和外部排序。

  • 内部排序：整个排序的过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。
  • 外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。

# 十大内部排序算法

  • 选择排序
    • 直接选择拍讯、堆拍讯
  • 交换排序
    • 冒泡排序、快速排序
  • 插入排序
    • 直接插入排序、折半插入排序、Shell排序
  • 归并排序
  • 桶试排序
  • 基数排序

冒泡排序和快速排序必须要会手写，堆排序和归并排序要能讲出来的，能够手写当然是最好的。

# 算法的5大特征

输入（Input） 有0个或多个输入数据，这些输入必须有清楚的描述和定义
输出（Output） 至少有1个或多个输出结果，不可以没有输出结果
有穷性（有限性，Finitenness） 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成
确定性（明确性，Definiteness） 算法中的每一步都有确定的含义，不会出现二义性
可行性（有效性，Effectiveness） 算法的每一步都是清楚且可行的，能让用户用纸笔计算而求出答案

说明：满足确定性的算法也称为：确定性算法。现在人民也关注更广发的概念，例如考虑各种非确定性的算法，如并行算法、概率算法等。另外，人们也关注并不要求终止的计算描述，这种描述有时被称为过程（procedure）。

# 线性查找

查找也可以称为搜索，所谓线性查找，就是直接遍历，找到一个符合条件的结果。

package arrayTest;

public class Demo11 {
    public static void main(String[] args) {
        String[] arr = new String[]{"JJ", "DD", "MM", "BB", "GG", "AA"};
        String dest = "BB";
        boolean isFlag = true;
        for (int i = 0; i < arr.length; i++) {
            if (dest.equals(arr[i])) {
                System.out.println("找到了指定的元素，位置为" + i);
                isFlag = false;
                break;
            }
        }
        if (isFlag) {
            System.out.println("很遗憾，没有找到！");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
找到了指定的元素，位置为3
1

# 二分法查找

二分法查找也叫折半查找，

（1）确定该区间的中间位置K

（2）将查找的值T与array[k]比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。

image-20201208110127248

前提：所要查找的数组必须有序。

二分法查找特点是效率高。

package arrayTest;

public class Demo12 {
    public static void main(String[] args) {
        int[] arr = new int[]{-98, -34, 2, 34, 54, 66, 79, 105, 210, 333};
        int dest = 35;
        //初始的首索引
        int head = 0;
        //初始的末尾索引
        int end = arr.length - 1;
        boolean isFlag = true;
        while (head <= end) {
            int middle = (head + end) / 2;
            if (dest == arr[middle]) {
                System.out.println("找到了，索引位置为：" + middle);
                isFlag = false;
                break;
            } else if (arr[middle] > dest) {
                end = middle - 1;
            } else {
                head = middle + 1;
            }
        }
        if(isFlag){
            System.out.println("很遗憾，没有找到！");
        }
    }
}
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

# 回型算法

输入一个数字n，生成回型数字n，数字是n列，n行。并打印。

例如输入3

1 2 3
8 9 4
7 6 5

例如输入5

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

分析：

  • 最大值为输入值的平方。
  • 存在4条线

image-20201207195704120

  • 走完4个方向为一圈

假设输入5

第一圈

方向 步数 这条线多少个数字 见到倒数第n个截止 生成值
向右 4 5 1 1 2 3 4
向下 4 5 1 5 6 7 8
向左 4 5 1 9 10 11 12
向上 4 5 1 13 14 15 16

第二圈

方向 步数 这条线多少个数字 见到倒数第n个截止 生成值
向右 2 5 2 17 18
向下 2 5 2 19 20
向左 2 5 2 21 22
向上 2 5 2 23 24
package arrayTest;

import java.util.Scanner;

/**
 * 输入一个数字n，生成回型数字n，数字是n列，n行。并打印。
 */
public class Demo7 {
    public static void main(String[] args) {
        //获取输入的数字
        //初始化化二维数组
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数字，将会自动成回形数：");
        if (!scan.hasNextInt()) {
            System.out.println("您输入的不是数字！");
        }
        int input = scan.nextInt();
        if (input <= 0) {
            System.out.println("请输入正整数！");
            return;
        }
        int[][] arr = new int[input][input];
        //控制赋值数字
        int count = 0;
        for (int i = 0; i < input * input; i++) {
            //向右，y轴不变，x轴自增，最多写入倒数第二个
            for (int y = i, x = i; x < input - i - 1; x++) {
                count++;
                arr[y][x] = count;
            }
            //向下，x轴不变，y轴自增，最多写入倒数第二个
            for (int y = i, x = input - i - 1; y < input - i - 1; y++) {
                count++;
                arr[y][x] = count;
            }
            //向左，y轴不变，x轴自减，最多写入倒数第二个
            for (int y = input - i - 1, x = input - i - 1; x > i; x--) {
                count++;
                arr[y][x] = count;

            }
            //向上，x轴不变，y轴自减，最多写入倒数第二个
            for (int y = input - i - 1, x = i; y > i; y--) {
                count++;
                arr[y][x] = count;
            }
        }
        //输出
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }

    }
}
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

输入5：

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

输入6：

1	2	3	4	5	6	
20	21	22	23	24	7	
19	32	33	34	25	8	
18	31	36	35	26	9	
17	30	29	28	27	10	
16	15	14	13	12	11
1
2
3
4
5
6

输入3：

1	2	3	
8	0	4	
7	6	5
1
2
3

发现了一个bug，当数字为奇数的时候，为0，那么很简单，只需要计算出来单独设置就可以了。

//当为奇数时，需要单独设置中心点数字
if (input % 2 != 0) {
    arr[input / 2][input / 2] = input * input;
}
1
2
3
4

完整代码如下：

package arrayTest;

import java.util.Scanner;

/**
 * 输入一个数字n，生成回型数字n，数字是n列，n行。并打印。
 */
public class Demo7 {
    public static void main(String[] args) {
        //获取输入的数字
        //初始化化二维数组
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数字，将会自动成回形数：");
        if (!scan.hasNextInt()) {
            System.out.println("您输入的不是数字！");
        }
        int input = scan.nextInt();
        if (input <= 0) {
            System.out.println("请输入正整数！");
            return;
        }
        int[][] arr = new int[input][input];
        //当为奇数时，需要单独设置中心点数字
        if (input % 2 != 0) {
            arr[input / 2][input / 2] = input * input;
        }
        //控制赋值数字
        int count = 0;
        for (int i = 0; i < input * input; i++) {
            //向右，y轴不变，x轴自增，最多写入倒数第二个
            for (int y = i, x = i; x < input - i - 1; x++) {
                count++;
                arr[y][x] = count;
            }
            //向下，x轴不变，y轴自增，最多写入倒数第二个
            for (int y = i, x = input - i - 1; y < input - i - 1; y++) {
                count++;
                arr[y][x] = count;
            }
            //向左，y轴不变，x轴自减，最多写入倒数第二个
            for (int y = input - i - 1, x = input - i - 1; x > i; x--) {
                count++;
                arr[y][x] = count;

            }
            //向上，x轴不变，y轴自减，最多写入倒数第二个
            for (int y = input - i - 1, x = i; y > i; y--) {
                count++;
                arr[y][x] = count;
            }
        }
        //输出
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }

    }
}
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

似乎还有另一种走法：

image-20201207195752590

package arrayTest;

import java.util.Scanner;

/**
 * 输入一个数字n，生成回型数字n，数字是n列，n行。并打印。
 */
public class Demo8 {
    public static void main(String[] args) {
        //获取输入的数字
        //初始化化二维数组
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个数字，将会自动成回形数：");
        if (!scan.hasNextInt()) {
            System.out.println("您输入的不是数字！");
        }
        int input = scan.nextInt();
        if (input <= 0) {
            System.out.println("请输入正整数！");
            return;
        }
        int[][] arr = new int[input][input];
        //控制赋值数字
        int count = 0;
        for (int i = 0; i < input * input; i++) {
            //向右，y轴不变，x轴自增
            for (int y = i, x = i; x < input - i; x++) {
                count++;
                arr[y][x] = count;
            }
            //向下，x轴不变，y轴自增
            for (int y = i + 1, x = input - i - 1; y < input - i; y++) {
                count++;
                arr[y][x] = count;
            }
            //向左，y轴不变，x轴自减
            for (int y = input - i - 1, x = input - i - 2; x >= i; x--) {
                count++;
                arr[y][x] = count;

            }
            //向上，x轴不变，y轴自减
            for (int y = input - i - 2, x = i; y > i; y--) {
                count++;
                arr[y][x] = count;
            }
        }
        //输出
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
    }
}
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

至此，已经实现了回型算法！

# 冒泡排序

# 介绍

冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

# 排序思想

  1. 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较为止。

# 测试代码

package arrayTest;

public class BubbleSortDemo {
    public static void main(String[] args) {
        int[] arr = new int[10];
        //随机赋值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100);
            System.out.print(arr[i] + "\t");
        }
        //冒泡排序
        for (int i = 0; i < arr.length - 1; i++) {
            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;
                }

            }
        }
        System.out.println();
        //输出
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
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
28	31	98	41	71	62	53	23	11	69	
11	23	28	31	41	53	62	69	71	98
1
2

# 快速排序（Quick Sort）

# 介绍

快速排序通常明显比同为O(nlogn)的其他算法更快，因此常被采用，而且快排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可见掌握快排的重要性。

快速排序（Quick Sort）由图灵奖获得者Tony Hoare发明，被列为20世纪十大算法之一，是迄今为止所有内排序算法中速度最快的一种。冒泡排序的升级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n))。

# 排序思想

  1. 从数列中挑出一个元素，称为"基准"（pivot），

  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

  4. 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

# 图解

image-20201208145351542 image-20201208145402523

image-20201208145436237

# 排序算法的性能对比

image-20201208145510817

# 各种内部排序方法性能比较

  1. 从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。

  2. 从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法。对于Shell排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。

  3. 从稳定性看：直接插入排序、冒泡排序和归并排序时稳定的；而直接选择排序、快速排序、Shell排序和堆排序是不稳定排序

  4. 从待排序的记录数n的大小看，n较小时，宜采用简单排序；而n较大时宜采用改进排序。

# 排序算法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；

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

# 总结

算法不是一周一夕能掌握的，需要长期大量学习，才能掌握越来越多。而且随着大量写代码会不断加深自己的学习能力，算法到那时再深入学习也不晚，目前来说，先掌握几种算法，后续其他算法再慢慢学，所以持之以恒吧。

# 后续拓展

堆排序。

归并排序。

帮我改善此页面 (opens new window)
#算法#排序
上次更新: 2020/12/18, 12:50:58
数组
Arrays工具类

← Arrays工具类→

最近更新
01
zabbix学习笔记二
02-28
02
zabbix学习笔记一
02-10
03
Linux访问不了github
12-08
更多文章>
Theme by Vdoing | Copyright © 2020-2022 Saul.J.Wu | MIT License