排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
通过算法进行排序后，这一组数就有序了， 但是要看两个相同的5的位置是否有改变。
5a仍在5b前面，那么这个排序算法就是稳定的 ，
5a跑到了5b后面，那么这个排序算法就是不稳定的 。
一个稳定的排序算法可以做到不稳定，
不稳定的排序算法一定做不到稳定。
至于为什么要讨论这个稳定性， 是为了以后应用到实际场景上。 比如，一场数学考试， 假设a用了30分钟做完了，并得了满分。
假设b用了一个小时做完了，并得了满分。 此时a与b都是得了满分，但是用的时间不一样，所以两个人的排名又会有所不同。
基本思想：任取待排序元素序列中的某元素作为基准值，将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
共有三种方法可以实现该思想。
挖坑发是后人对Hoare法的另一种实现方式。
需要排序的数列本身就是一个顺序或逆序的数列，此时找到的基准就会每次都分成极端的两组，一组一个数没有，另一组有n-1个数(这两组的边界一个是基准-1，一个是基准+1)
快速排序在最坏情况下，时间复杂度竟然达到了O(n2)，这哪里快速啊，所以下面就要进行优化了。
共有两种方案： 1️⃣随机选取基准法，这要是倒霉起来，依然有可能会次次都随机选到最极端最坏的情况，所以这个不用。 2️⃣三数取中法，这个可以保证不会让你选到最极端最坏的情况。
三数取中法：在上面的算法中，我们的基准选取的都是left下标，
而三数取中指的是在left，right，mid( (left + right)/2 )这三个下标在中选取一个中间值作为基准，不是最大也不是最小，就保证了不会出现极端情况。
出现了以上的最坏情况，也就是让快速排序变成了二分查找。
就像二叉树一样，每一组数据往下走一层都会被分成两组，而到了最后几层，则会因为数据量的庞大而被分成许多组进行递归，此时的递归开销就会很大，很有可能导致~~栈溢出~~，
因此我们可以设定一个数量闸口，当每组的数据小的到了这个闸口，就采用比较简单的直接插入排序。
而且在快速排序的不断递归下，数据一定是越来越有序的，直接插入排序的效率也会更高。
此时即便是一开始就用直接插入排序，时间也会相差无几。