# normal_algorithm

**Repository Path**: jieTan/normal_algorithm

## Basic Information

- **Project Name**: normal_algorithm
- **Description**: 常规算法（c++实现）。
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-07-27
- **Last Updated**: 2020-12-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 常规排序算法（c++实现）
### 1.插入排序
#### 1.1 直接插入排序（straight insertion sort）
##### 思路：
    1. 初始“有序区”怎么定义？
    答：将原序列中的第1个元素作为有序区的初始元素。
    2. 如何将无序区中的元素排到有序区中何是的位置？
    答：设无序区待排序的元素初始下标为 idx，且存放在临时空间，设为tmp。
        2.1 将 tmp 与 idx-1位置的元素比较：
            i 若tmp<idx-1，则idx-1位置的元素后移，idx--；
            ii 反之，将tmp的值放入到idx。
        2.2 重复2.1，直到找到
##### 步骤：
    1. 初始分为“有序区”和“无序区”两个概念；
    2. 将无序区的数据放进有序区里并排好序（具体实现参考“思路：2”）；
    3. 重复步骤2，直到无序区没有元素。
    
#### 1.2 希尔排序（shell sort）
##### 说明：
    将原序列分割为 n/d  个子序列（n：序列长度），并对每个子序列进行“直接插入排序”。
使得下一次排序时，原序列已“基本有序”，减少了元素的移动次数。
##### 思路：
    1. 初始 d 怎么确定？（d：相距为d的元素划分到一组）
    答：初始时，d=n/2。后续 d=d/2，直到d=1时，子序列进行一次完整的“直接插入排序”（排序前整个序列"基本上有序了"）。
    2. 子序列如何使用“直接插入排序”？（k=n/d）
    答：相当于划分了k个 相距为d的元素划分到一组 后进行”直接插入排序”。此时“直接插入排序”的step=d。
##### 步骤：
    1. 初始d=n/2；
    2. 划分子序列，之后d=d/2；
    3. 对每个子序列进行“直接插入排序”（此时“直接插入排序”的step=d）；
    4. 重复”2.“ ”3.“直到d=1。
    
### 2 交换排序：对被比较的两个元素，如不符合某种顺序，就交换两着的位置。
#### 2.1 冒泡排序（bubble sort）
##### 说明：
    两两比较，反序则交换二者的位置，每轮将最大的值放置到该轮的最后的位置，直至没有反序的元素。
##### 思路：
    1. 每轮排序的元素数量？
    答：由于每轮都会筛选出最大值到末端，则第i轮，排序的元素为 n-i个。（i>=1）
    2. 冒泡结束的判定标志？
    答：序列没有反序的元素时，结束。故可以设置一个结束标志（flag）来减少不必要的排序轮次。
##### 步骤：
    1. 从起始位置开始，两两比较，反序则交换元素位置。（若出现了交换，flag=false，反之flag=true）
    2. 重复1，直至序列中无反序元素。
    
#### 2.2 快速排序（quick sort）
##### 说明：
    选择一个轴值，每轮记录的较和交换是从两端向中间进行的（冒泡始终是从一端往另一端进行的），
这样每轮比较交换之后，轴值左边的元素均小于轴值，右边的均大于轴值。（明显的递归排序）
##### 思路：
    1. 如何选择轴值？
    答：一般选择第1个元素为轴值。（也可以从首值、尾值、中间值中取值在中间的那个位置的元素为轴值）
    2. 如何实现一次划分？（就是一轮排序）
    答：见”步骤1：一次划份“
    3. 怎么对排序后的左、右子序列再排序？
    答：继续对左、右子序列进行快速排序。
    4. 如何判断排序结束？
    答：直到左、右序列只有1个元素。
##### 步骤：
    1. 一次划分：（下面说的i值，j值，均是指i，j指向位置的值）（遵守”非轴值端移动“的准则） 
        I. 选择第1个元素为轴值，i指向首值（初始时轴值也指向首位），j指向尾值；
        II. 若 i值<j值，j--;反之，将轴值与j位置的元素交换（此时轴值指向j位置了），且i++；
        III. 若 j值>i值，i++；反之将轴值与i位置元素交换（此时轴值指向i位置了），且j--；
        IV. 重复II、III步骤，直至左边元素均小于轴值，右边元素均大于轴值。
    2. 继续对左右子序列进行一次划分，递归到左右子序列只有一个元素为止。
    
### 3.选择排序：每轮选出最小值，添加到有序序列中。元素移动次数少，但比较次数很多。
#### 3.1 简单选择排序（simple selection sort）
##### 说明：
    每轮选出最小值，添加到有序序列中的最简单（也是效率最低）的实现。即第i轮，比较n-i次，但最多只交换1次。
##### 步骤：
    1. 设min_idx来储存本轮的第1个元素的下标；
    2. 遍历序列，当找到小于array[min_idx]的元素，假设此时是j位置，则min_idx=j（注意是下标赋值，不是交换元素！），
并在本轮遍历完后，若min_idx!=i（i；本轮轮数），交换二者位置；
    3. 重复1，2步骤，直至序列有序。
    
#### 3.2 堆排序（heap sort）
##### 说明：
    在找出最小元素的同时，也找出次小的元素。从而减少后面比较的次数。
堆物理结构是数组，但是其逻辑结构可以看成一棵完全二叉树。并且把根结点成为堆顶。
有两种构造堆的方法：
        i 大根堆：堆顶为最大值。（即每个结点 大于 他的左右孩子）
        ii 小根堆：堆顶为最小值。（即每个结点 小于 他的左右孩子））
##### 思路：（以”大根堆“来思考）
    1. 对左右子树均是堆的完全二叉树，如何调整根结点的位置，使整棵树变为堆？=> 见”步骤1“。
    2. 如何构建序列对应的堆结构？（即初始建堆）=> 见”步骤2“。
    3. 如何处理堆顶元素？=> 见”步骤3“。
    4. 对剩下的元素如何重建堆结构？（即重建堆）=> 见”步骤4“。
##### 步骤：
    1. 寻找堆顶：
        i 先找出左右孩子中较大的（成为”大孩子“）；
        ii 让根结点与大孩子比较。若根大，则该根结点便是堆顶；反之，将根与大孩子交换。此时将原大孩子的位置看成根结点。
        iii 重复i，ii步骤，直到为叶子结点。
    2. 初始建堆：
        i 由完全二叉树性质有：前n/2才有孩子结点，后n/2全是叶子结点。叶子结点可以看成是堆。
        ii 对前n/2个结点寻找堆顶即可。（自底向上建立堆结构）
    3. 初始建堆之后，将堆顶元素与最后一个元素互换位置。（即将最大的元素排在了序列尾端）
    4. 重建堆：”步骤3“之后，其左右子树依旧是堆，此时又回到了”步骤1“寻找堆顶的问题。
    5. 重复3，4步骤，直至序列有序。
    
### 4 归并排序（merge sort）：将若干个 有序序列 两两归并，直至整个序列有序。
#### 4.1 非递归实现
##### 思路：
    1. 如何实现序列的一次归并？=> 见”步骤1“。
    2. 如何实现序列的一轮归并？=> 见”步骤2“。
    3. 怎么控制整个归并的结束？
    答：待归并的序列长度大于等于整个序列时，结束。
##### 步骤：orig：orig[1 ~ m]=>已有序序列1，orig[m+1 ~ end]=>原始已有序序列2。restlt => 将两个有序序列排好序存放的地方。
    1. 一次归并：将orig[1 ~ m]与orig[m+1 ~ end]归并排序，并将结果放进restlt；
    2. 一轮归并：设待归并序列长度为 h，整个元素个数为 n个。
        I 对于第i次”一次归并“。若i>n-h，表明只剩最后一个序列了，直接添加到restlt；反之，继续进行”一次归并“。
    3. 重复2步骤，直到h>=n时，停止。

#### 4.2 递归实现
##### 思路：restlt => 将两个有序序列排好序存放的地方。orig：初始待排序的序列。
    1. 怎么将序列划分为可以递归归并的序列？
    答：递归到每个子序列只有一个元素时（即start=end），开始递归归并（此时将元素放进restlt中）。
    2. 归并函数中有几次调用自身的地方？
    答：两次。由于每次归并都需要有两个有序的序列，可知函数里有两次调用自身的情况。
一次递归到第一个有序序列，另一次递归到第二个有序序列。
    3. 递归中，调用“一次归并”要注意什么？
    答：由于“一次归并”针对的时两个有序序列，而归并之后的有序结果却放在了restlt中，
故需要将result对应位置的元素复制到orig中（直接覆盖原位置的值）。

### 5 分配排序
#### 5.1 桶式排序（bucket sort）
##### 说明：（典型的以空间换时间的做法，适用于元素稠密的情况）
    适用于“已知序列（假设为orig）元素的取值范围”的排序。每个桶的序号对应这orig中的元素值，而桶的元素便是orig中某个元素出现的次数。
（对于十分分散的序列，“桶式排序”就会非常浪费空间（比如[1,10,100]要申请101个桶）！“基数排序”就是来解决这个问题的）
##### 思路：
    1. 如何表示一个桶，来存储相同元素的值？
    答：可单独用一个数组来存储相同元素的数量。（该数组的相应下标便是原序列元素的值）
    2. 如何进行分配操作？=> 步骤2
    3. 如何进行收集操作？=> 步骤3
    4. 扩展：对于有负值的序列怎么排序？（目前只提供思路，有具体应用场景再相应实现）
    答：假设min为最小非正值，max为最大正值。则创建bucket[max-min+1]，要收集的时候，对应下标=下标-abs(min)。（目前min=0）
##### 步骤：待排序序列：orig
    1. 根据orig的最大元素值m，创建一个bucket[m+1]，且初始化bukcet元素为0；
    2. 分配：遍历orig，并用bucket的来记录orig中元素出现的次数。
（如：orig[0]=5, 那么就++bucket[5],则此时bucket[5]记录orig中“5”出现的次数）
    3. 收集：遍历bucket，按下标顺序将和记录的次数将值写回orig。
    
#### 5.2 基数排序（radix sort）
##### 说明：记原始序列为orig
    1. “基数排序”也需要知道orig的最大值，但解决了“桶式排序”中桶的数量存在过多的情况。
    2. 对于“基数排序”来说，桶的数量总是为10个（来存放0,1,2,3,4,5,6,7,8,9）。
##### 思路：
    1. 什么是基数，其作用是什么？
    答：简单来说，就是orig中的元素要符合该轮比较所要除以的数。
比如：orig[i]=203, 而该轮是要比较orig总所有元素的百位上的值，则radix=100，得到orig[i]的百位是2。同理得到其他元素的百位值，之后就是普通的桶式排序了。
    2. “基数排序”原理是什么？
    答：假设orig中最大的元素是999，那么就存在百、十、个位的3轮比较。
这样三轮比较之后，自前向后看，百位是有序的，而百位相同的，十位也是有序的（个位也是如此）。
##### 步骤：
    1. 根据最大值确定需要桶式排序的轮数（假定为n轮）；
    2. 根据n，循环进行桶式排序（分配、收集）：假定该轮的序号为k,0<=k<n。则第k轮时，radix=10^k。
        2.1 分配：Bucket的元素类型BNode{data,*next}
            a）自定义一个Bucket队列，包含front（指向头元素）、rear（指向尾元素）两个属性;
            b）入队：
                i）遍历orig的元素，用bucket[orig[i]/radix%10] 来存放orig[i];
                ii）若bucket[orig[i]/radix%10] 存在指向相同位置的情况，rear后移，使rear始终指向最后一个元素。
        2.2 收集：
            a）出队：遍历bucket，对于每个桶，若front!=NULL，则遍历完front指向的元素，放进orig中。