一、排序算法

1.快速排序

快速排序（QuickSort）是排除稳定性因素后最常用的排序。给看官介绍两种使用方法，一种值直接在我文件 stdlib.h 头文件中的 qsort 函数实现是和正常写代码一样的。通过使用qsort（数组名，长度，sizeof（第一个数长度），compInc/comoDec) 进行实现数组的排序。后面的是通过递归调用的形式。
算法描述：

  1. 从数列中挑出一个元素作为基准。
  2. 重新排列数列，把所有的比基准小的放在基准前面，反之放在后面（一样大可任意一边）完成后基准处在分区的中间位置。
  3. 通过递归调用把小于基准元素和大雨基准元素的子序列进行排序。

算法可视化：
ks.gif

2.冒泡排序

冒泡排序（Bubble Sort） 最为简单的一种排序，通过重复走完数组的所有元素，通过打擂台的方式两个两个比较，直到没有数可以交换的时候结束这个数，再到下个数，直到整个数组排好顺序。因一个个浮出所以叫冒泡排序。双重循环时间 O(n^2)

  1. 比较相邻两个数据如果。第一个比第二个大，就交换两个数
  2. 对每一个相邻的数做同样1的工作，这样从开始一队到结尾一队在最后的数就是最大的数。
  3. 针对所有元素上面的操作，除了最后一个。
  4. 重复1~3步骤，知道顺序完成。

算法直观可视图：
mp.gif

3.选择排序。

选择排序（Select Sort） 是直观的排序，通过确定一个 Key 最大或最小值，再从带排序的的数中找出最大或最小的交换到对应位置。再选择次之。双重循环时间复杂度为 O(n^2)
算法描述：

  1. 在一个长度为 N 的无序数组中，第一次遍历 n-1 个数找到最小的和第一个数交换。
  2. 第二次从下一个数开始遍历 n-2 个数，找到最小的数和第二个数交换。
  3. 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换，排序完成。

算法直观可视图：
sz.gif

4.插入排序

假设有个这样的问题：打扑克。分成两部分：一部分是你手里的牌（已经排好序），一部分是要拿的牌（无序）。把一个无序的数列一个个插入到有序数列中。
一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？我们只要遍历数组，找到数据应该插入的位置将其插入即可。
image.png

5.希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。
image.png

6.二分查找

image.png

7.归并排序（二分排序）

image.png
gb.gif

8.桶排序

image.png

9.堆排序，基数排序，插入O （n^2）

堆是一棵顺序存储的完全二叉树。
其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
image.png

二、排序算法稳定性分析

我们通常从哪几个方面来分析一个排序算法？
1.时间效率：决定了算法运行多久，O（1）
2.空间复杂度：
3.比较次数&交换次数:排序肯定会牵涉到两个操作，一个比较是肯定的。交换。
4.稳定性：这是什么？
1 9 3 5 3
第一种：1 33 5 9
第二种：1 33 5 9
第一种是稳定的，相同的两个数排完序后，相对位置不变。
稳定排序有什么意义？应用在哪里呢？
电商里面订单排序：首先会按金额从小到大排，金额相同的按下单时间。我从订单中心过来的时候已经按照时间排好序了。
如果我选择不稳定的排序算法 那我还要比较两次的，如果我选择稳定的排序算法 那我就只要比较一个字段。
1 8:01 65
2 20:05 30
3 21:10 30
4 22:01 45
image.png