目录
一，排序
二，稳定性
三，冒泡排序
四，选择排序
五，插入排序
六， 希尔排序(缩小增量排序)
八，堆排序
九，快速排序
十，排序总结
一，排序
排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
通常意义上的排序，都是指的原地排序(in place sort)。
二，稳定性
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
1，3(a)，4，2，6，3(b)，7，3(c) -------->1，2，3(a)，3(b)，3(c)，4，6，7
三，冒泡排序
原理：在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序
分析时间复杂度与空间复杂度：
冒泡排序属于交换排序，是稳定排序，平均时间复杂度为 O(n²)，空间复杂度为 O(1)。
但是我们常看到冒泡排序的最优时间复杂度是 O(n)，那要如何优化呢？
我们可以用一个 参数记录新一轮的排序中元素是否做过交换，如果没有，说明前面参与比较过的元素已经是正序，那就没必要再从头比较了。代码实现如下：
四，选择排序
每一次从无需区间选出最大值（或最小值）的一个元素，存放在无序区间的最后面（或最前面），直到所有元素排序完成。
代码实现：
优化：双向选择排序
每一次从无序区间找出最大值和最小值，将最小值放到无序区间的最开始位置，最大值放到无序区间的最后位置。
分析时间复杂度与空间复杂度
选择排序是不稳定排序，时间复杂度固定为 O(n²)，因此它不适用于数据规模较大的序列。不过它也有优点，空间复杂度为O(1)，就是不占用额外的内存空间。
五，插入排序
原理：将待排序的数组集合分为两部分，已排序的区间和待排序区间；每一次从无序区间的第一个元素插入有序区间的合适位置，直到整个数组有序。
刚开始排序时有序区间没有元素，整个数组都为无序区间。
当已经排序的集合最后元素< 当前无序区间的第一个元素，内层循环直接可以退出。大大的降低了时间，如果出现极端情况（待排序的数组就是一个完全升序的数组)，插入排序就会进化为O(n)的时间复杂度
优化：二分插入排序（提升插入时的效率）
分析时间复杂度与空间复杂度：
插入排序是稳定排序，平均时间复杂度为 O(n²)，空间复杂度为 O(1)。
六， 希尔排序(缩小增量排序)
人们发现数组接近有序时插入排序的效率很高，希尔排序就是对 插入排序的优化；
原理：1.先选定一个整数（gap）将待排序的分成gap组，所有距离为gap的为同一组，对每一个小数组进行插入排序。
2.缩小gap值，一般取gap = gao / 2，重复第一步过程，直至gap = 1（此时数组已经近乎有序）。在进行整个数组的插入排序即可
代码实现：
分析时间复杂度与空间复杂度：
希尔排序是不稳定排序，它的分析是一个复杂的问题，因为它的运行时间依赖于增量序列的选择，它的平均时间复杂度为O(n^1.3)，最好情况是 O(n)，最差情况是 O(n²)。空间复杂度为 O(1)。
归并排序
建立在归并操作上的一种排序算法。与快速排序都采用了分治思想
原理：不断将原数组一分为二为两个子数组，直到每个子数组只剩下一个元素；不断合并相邻的两个数组为一个大的子数组，直到合并到整个数组。
示例代码：
分析时间复杂度与空间复杂度：
希尔排序是不稳定排序，它的分析是一个复杂的问题，因为它的运行时间依赖于增量序列的选择，它的平均时间复杂度为O(n^1.3)，最好情况是 O(n)，最差情况是 O(n²)。空间复杂度为 O(1)。
八，堆排序
原理：将待排序数组构造为一个最大堆，此时数组中最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就是最大值，调整剩余n-1个元素为一个最大堆，再将根节点与调整后的末尾元素进行交换，直至数组有序。
示例：arr={4,6,8,5,9};
第一步：将无序数组创建为完全二叉树，调整为最大堆。
第二步：将堆顶元素与末尾元素交换，重新调整结构为最大堆结构
第三步：重复执行第二步，直至数组完全有序
代码实现：
分析时间复杂度与空间复杂度：
堆排序是不稳定排序，适合数据量较大的序列，它的平均时间复杂度为 Ο(nlogn)，空间复杂度为 O(1)。 此外，堆排序仅需一个记录大小供交换用的辅助存储空间。
九，快速排序
核心思想：分区
分区值：默认选择最左侧pivot
原理：从无序区间选择一个值作为分界点pivot开始扫描原集合，将数组中所有小于pivot的元素放在分界点的左侧，大于等于的元素放在分界点的右侧。经过本轮交换，pivot放在了最终的位置，pivot的左侧都是小于pivot的元素，右侧都是大于该值的元素，在两个子区间重复上述过程，知道集合有序。
此时arr[l+1~j] 1.若arr[i] >= v: 此时只需要i++，继续处理下一个元素。 2.若arr[i] < v : 需要将arr[i] 放在[l+1~j]区间中，将arr[i] 和 arr[j+1]进行交换； j++； 在i++继续处理下一个元素。 当i扫描完整个数组后，数组的划分情况： 这时只需要交换 arr[l]和arr[j]的位置。交换后 j 的左边全都是 < v的元素；j的右边全都是 > v的元素，元素 v 就落在了最终位置 j 。 代码实现： 分析时间复杂度与空间复杂度： 空间复杂度：递归函数的调次数（nlogn）; 时间复杂度：nlogn n-为每次分区函数的数组扫描 logn-递归函数的调用次数平均情况下就是一个二叉树的高度； 极端情况：数组为近乎完全有序时，按照最左侧元素进行分区的时候，会造成左右两颗递归树严重不平衡，甚至极端情况下退化为链表，时间复杂度退化从O(logn) 为O(n); 快速排序的优化：合理的分区点的选择可以避免快速排序性能退化的问题；每次随机选择最左侧，最右侧，中间值中的任意一个作为分区点。十，排序总结
排序算法 时间复杂度 最差 最好 空间复杂度 稳定性 冒泡排序 O(n²) O(n²) O(n) O(1) 稳定 快速排序 O(nlogn) O(n²) O(nlogn) O(logn) 不稳定 插入排序 O(n²) O(n²) O(n) O(1) 稳定 希尔排序 O(n^1.3) O(n²) O(n) O(1) 不稳定 选择排序 O(n²) O(n²) O(n²) O(1) 不稳定 堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定 归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定
