排序：通过重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便,通常希望计算机中的表是按关键字有序的。

比较类排序：通过比较来决定元素间的相对次序。

非比较类排序：不通过比较来决定元素间的相对次序，可以线性时间运行。?

算法的稳定性：若待排序表中有两个元素R和R,若使用某一排序算法排序后, R仍然在R的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。’

时间复杂度：是指算法中基本操作的执行次数。反映当n变化时，操作次数呈现什么规律。

空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

算法复杂度

插入排序是一种简单直观的排序方法,其基本思想是每次将一个待排序的记录按其关键字大
小插入前面已排好序的子序列，直到全部记录插入完成。

算法描述：

1.将第一个数当作有序序列，后面的数字当作无序序列；

2.从第二个数开始往前面依次比较，如果该数大于新数则将该数移到新数的下一个位置，小于则向前寻找，直到找到比该数小于或者等于的新元素的后面位置并插入；

3.将排列好的序列认定为有序序列，重复上述操作

算法优化：折半插入排序，①从前面的有序子表中查找出待插入元素应该被插入的位置;②给插入位置腾出空间，将待插入元素复制到表中的插入位置

动图演示

代码实现

希尔排序本质上是对插入排序的优化，希尔排序又叫缩小增量排序，本质还是插入排序，更适用于基本有序和数据量不大的排序表。每次排序都会按照增量大小将表分成多组列表进行插入排序

算法描述：

1.初始增量gap为n/2，根据增量大小将待排序列分成多组序列? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

2.每组序列按照简单插入排序进行排列? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

3.增量缩减为初始增量的gap/2，继续1-2操作

动图演示

代码实现

冒泡排序是交换排序，通过从后往前（或从前往后）两两进行比较相邻元素的值，若为逆序则交换，直到序列比较完成。如第一趟冒泡是将最小的值放置在第一个位置，第二趟是第二小的值放在第二。。。依此类推

算法思想

1.从后往前倒数第一个值开始第一趟排序，比较相邻元素，小值向前移，最后最小值放在第一位? ?

2.第二趟开始，从倒数第二个值往前比较，小值向前移，值放在第二位? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

3.直到最终实现序列有序

算法优化1：在每次循环完成之后进行判断本趟排序是否进行交换，若为交换则直接判定为序列有序，直接跳出循环

算法优化2：向前排序过程中每次记录最后交换位置，也就是下一趟进行排序的第一个位置，下一趟排序直接从最后到该位置就行比较交换即可

动画演示（动画为从前往后排序）

代码实现（代码为从后往前排序）

快速排序是基于分治法的：在待排序表去一个元素pivot作为枢轴（一般取首元素），通过第一趟排序将排序表划分为两个部分，前面的小于该枢轴，后面的大于枢轴，这是一趟快速排序；然后重复将子表进行上述操作，直到排序完成

算法思想：

1.分解：以 pivot为基准将 a[low，high]划分为三段a[low，pivot-1]，a[pivot] 和 a[pivot+1，high]，使得a[low，p-1] 中任何一个元素小于等于a[pivot]，而 a[p+1，high] 中任何一个元素大于等于? ?a[pivot]

2.递归求解：通过递归调用快速排序算法分别对a[low，pivot-1]和 a[pivot+1，high]进行排序? ? ? ? ? ?

3.合并：由于对a[low，pivot-1]和 a[pivot+1，high]的排序是就地进行的，所以在a[low，pivot-1]和 a[pivot+1，high]都已排好序后，不需要执行任何计算，a[low: high] 就已经排好序了。

算法优化1之基准选择：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）本文代码给的基准为固定基准，在排序列表基本有序的情况下一直选择第一个数为基准，则会出现每次排序都是后面代排序列比基准大，相当于冒泡排序。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）随机基准Random(a, low, high)：基准选的最差的概率1/n,最好也是1/n，但是数组元素越多，随机数算法的效果越好，不容易出现最坏的情况? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （3）三数取中：即每次基准都从[第一个元素，最中间元素，最后一个元素]中选择一个最中间元素，就可以避免待排序数组基本有序的情况，选取的基准没有随机性，处理效果最好

算法优化2：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）序列长度达到一定大小时，使用插入排序? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）尾递归优化? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （3）聚集相同元素：在一次分割结束后，将与本次基准相等的元素聚集在一起，再分割时，不再对聚集过的元素进行分割。具体过程①在划分过程中将与基准值相等的元素放入数组两端,②划分结束后，再将两端的元素移到基准值周围。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）多线程处理快排

算法优化详细请参考：(12条消息) 快速排序的4种优化_快速排序优化_Tyler_Zx的博客-CSDN博客

动画演示

代码实现

选择排序是通过比较选择出最小的值，再将最小值和第一个值进行交换

算法思想：

1.第一趟：从左到右进行比较，将最小值记录在min中，如果最小值不等于初始位置则交换俩值? ? ?

2.第二趟：从第二个值开始执行上述操作? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

3.直到序列有序即可

算法优化:每次选出最小值和最大值并放入对应位置

动画演示?

代码实现

堆的定义如下，n个关键字序列L[...n]称为堆，当且仅当该序列满足:
①L(i)>=L(2i)且L(i)>=L(2i+1) 或②L(i)<=L(2i) 且L(i)<=L(2i+1) (1si≤L Ln/2」)
可以将该一维数组视为一棵完全二叉树，满足条件①的堆称为大根堆(大顶堆)，满足条件②的堆称为小根堆( 小顶堆)；大根堆的最大值在顶端，小根堆的最小值在顶端

算法思想：

首先将存放在L[1..n]中的n个元素建成初始堆,（大顶堆为例)堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 此时根结点已不满足大顶堆的性质，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?如此重复，直到堆中仅剩一个元素为止。
关键是构造初始堆。n个结点的完全二叉树，最后一个结点是第Ln/2」个结点的孩子。对第Ln/2」个结点为根的子树筛选(对于大根堆，若根结点的关键字小于左右孩子中关键字较大者，则交换),使该子树成为堆。之后向前依次对各结点(Ln/2」-1~1)为根的子树进行筛选，看该结点值是否大于其左右子结点的值,若不大于，则将左右子结点中的较大值与之交换，交换后可能会破坏下一级堆，于是继续采用上述方法构造下一级的堆，直到以该结点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根结点。
?

动画演示

代码实现

“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。假定待排序表含有n个记录，则可将其视为n个有序的子表，每个子表的长度为I,然后两两归并，得到「n/21个长度为2或1的有序表;继续两两.....如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2路归并排序。

算法思想?
分解:将含有n个元素的待排序表分成各含n/2 个元素的子表，采用2路归并排序算法对两个子表递归地进行排序。
合并:合并两个已排序的子表得到排序结果。

动画演示

代码实现

计数排序的原理：统计数组中每个数出现的次数，数组中每个数排序后的位置，就是比它小的数的出现次数累加和，只能适用于数值型的数组

动画演示

?代码实现

桶排序（箱排序）是一种基于分治思想、效率很高的排序算法，理想情况时间复杂度为O(n)，工作的原理是将数组分到有限数量的桶里，每个桶再个别排序（可用其他排序算法或递归使用桶序），最后依次把各个桶中的记录列出成有序序列。

动画演示

?

代码实现

基数排序是一种很特别的排序方法，它不基于比较和移动进行排序，而基于关键字各位的大小进行排序。基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。基数排序是桶排序的扩展，速度快，占用内存很大

为实现多关键字排序，通常有两种方法:第一种是最高位优先法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列。第二种是最低位优先(LSD) 法，按关键字权重递增依次进行排序，最后形成一个有序序列

算法思想：

如图片所示，第一趟：先进行个位分配，按照顺序依次将其放入个位数字对应的队列中，按照先进先出进行收集，先从下往上依次取出；第二趟：进行十位上分配，从前往后依次放入对应的队列，进行收集，从下往上取出，最终得到排序序列

动画演示

?

代码实现

图片参考：十大经典排序算法（动图演示）

代码参考：王道数据结构

桶排序基数排序代码来自(8条消息) 十大排序算法及优化 ( C++简洁实现)_c++ 桶排序优化_阿祖_in_coding的博客-CSDN博客