图解数据结构-算法部分（Java语言实现）

数据结构与算法一直是比较薄弱的地方，不仅在面试的时候会问相关问题、手写代码，而且在笔试的时候发挥重要作用。

前面一直学习的数据结构，下面排序、查找属于算法的范畴了。

排序

所谓 “排序” (Sorting) 就是指将一组数据，按特定规则调换位置，使数据具有某种顺序关系（递增或递减）。

排序分类，可分为内部（内存中）和外部（外部存储器）排序两大类。

常见的内部排序法有：冒泡排序法、选择排序法、插入排序法、合并排序法、快速排序 法、堆积排序法、希尔排序法、基数排序法等。 至于比较常见的外部排序法有：直接合并排序法、K 路合并法、多相合并法等。

排序算法分析：算法是否稳定、时间复杂度、空间复杂度。

稳定的排序是指数据在经过排序后，两个相同键值的记录仍然保待原来的次序。

内部排序法

内部排序法的时间复杂度及键值整理。

1、冒泡排序法

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

实现算法：

int i, j, tmp;
int data[] = {6, 5, 9, 7, 2, 8};    //原始数据
for (i = 5; i > 0; i--)             //扫描次数
{
    for (j = 0; j < i; j++)         //比较、交换次数
    {
        // 比较相邻两数，如第一数较大则交换
        if (data[j] > data[j + 1]) {
            tmp = data[j];
            data[j] = data[j + 1];
            data[j + 1] = tmp;
        }
    }
    
}

但是这样如论如何都会执行 $ n(n-1)/2 $ 次，我们可以加一个判断在没有可替换的数据时终止程序。

public void bubble() {
    int i, j, tmp, flag;
    for (i = 5; i >= 0; i--) {
        flag = 0;           //flag用来判断是否有执行交换的动作
        for (j = 0; j < i; j++) {
            if (data[j + 1] < data[j]) {
                tmp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = tmp;
                flag++;    //如果有执行过交换，则flag不为0
            }
        }
        //当执行完一次扫描就判断是否做过交换动作，如果没有交换过数据，
        //表示此时数组已完成排序，故可直接跳出循环
        if (flag == 0) {
            break;
        }
    }

冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近 n²/2 次, 时间复杂度为 O(n²) . 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n).

平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的 temp 变量需要内存空间, 因此空间复杂度为常量O(1).

Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

2、选择排序法

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

算法描述：

(1) 从待排序序列中，找到关键字最小的元素；
(2) 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
(3) 从余下的 N - 1 个元素中，找出关键字最小的元素，重复 (1)、(2) 步，直到排序结束。

void select() {
    int i, j, tmp;
    for (i = 0; i < 5; i++) {            //扫描 5 次
        for (j = i + 1; j < 6; j++) {    //由 i+1 比较起，比较 5 次
            if (data[i] > data[j]) {     //比较第 i 及第 j 个元素
                tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;
            }
        }
    }
}

选择排序的简单和直观名副其实，这也造就了它 “出了名的慢性子” ，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近 n²/2 次遍历来确认一遍。即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。

3、插入排序法

将数组中的所有元素依次跟前面已经排好的元素相比较，再将数组元素插入合适的位置。

实现算法：

void insert() {
    int i;     // i 为扫描次数
    int j;     // j 来定位比较的元素
    int tmp;   // tmp 用来暂存数据
    for (i = 1; i < size; i++) {  // 扫描循环次数为 SIZE-1
        tmp = data[i];
        j = i - 1;
        while (j >= 0 && tmp < data[j]) {  // 如果第二元素小于第一元素
            data[j + 1] = data[j]; // 就把所有元素往后推一个位置
            j--;
        }
        data[j + 1] = tmp;       // 最小的元素放到第一个元素
    }
}

Tips: 由于直接插入排序每次只移动一个元素的位，并不会改变值相同的元素之间的排序，因此它是一种稳定排序。

4、希尔排序法

希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。

实现算法：

void shell() {
    int i;        // i 为扫描次数
    int j;        // j 来定位比较的元素
    int k = 1;    // k 打印计数
    int tmp;      // tmp 用来暂存数据
    int jmp;      // 设定间隔位移量
    jmp = size / 2;
    while (jmp != 0) {
        for (i = jmp; i < size; i++) {
            tmp = data[i];
            j = i - jmp;
            while (j >= 0 && tmp < data[j])  //插入排序法
            {
                data[j + jmp] = data[j];
                j = j - jmp;
            }
            data[jmp + j] = tmp;
        }
        jmp = jmp / 2;    //控制循环数
    }
}

5、合并排序法

合并排序算法是将两个（或两个以上）有序表合并成一个新的有序表；
即把待排序序列分为若干个子序列，每个子序列是有序的，然后再把有序子序列合并为整体有序序列。

6、快速排序法

快速排序法又称分割交换排序法，是目前公认最佳的排序法。

它的原理和冒泡排序法一样都是用交换的方式，不过它会先在数据中找到一个虚拟的中间值，把小于中间值的数据放在左边，而大于中间值的数据放在右边，再以同样的方式分别处理左右两边的数据，直到完成为止。

7、堆积排序法

堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。

8、基数排序法

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

外部排序法

直接合井排序法 (Direct Merge Sort) 是外部存储设备最常用的排序方法。

它可以分为两个步骤：
步骤1: 将要排序的文件分为几个大小可以加载到内存空间的小文件，再使用内部排序法将各文件内的数据排序。
步骤2: 将第一步所建立的小文件每两个合并成一个文件。两两合井后，把所有文件合并成一个文件后就可以完成排序了。

查找

所谓查找，就是从数据文件中，寻找符合某特定条件的记录。而用来查找的条件就称为 “键值” 。

一般来说，如果数据在查找前经过排序，将可大幅减少查找的时间。至于查找技巧中比 较常见的方法有顺序法、二分查找法、斐波那契法、插值法、哈希法、m 路查找树、B-tree 等。

数据结构：https://www.wshunli.com/posts/850e5c53.html
算法：https://www.wshunli.com/posts/444e2c0f.html

参考资料
1、八大排序算法总结与java实现 | iTimeTraveler
https://itimetraveler.github.io/2017/07/18/八大排序算法总结与java实现/