1.排序的稳定性：
简单地说就是原来这两个相等的数假设为5第一个5记为5a第二个记为5b此时他们下标分别为0和1，当排序之后他们的下标就发生了变化，5a的下标为1，5b的下标为0，此时就是不稳定的。如果排完序之后的5a和5b的下标还是和原先一样，5a在5b之前，那么就是稳定的。需要注意的是：稳定的排序可以变成不稳定的排序，但是本身不稳定的排序，就不能改成稳定的排序。
2.内部排序：
数据元素全部放在内存中的排序。
3.外部排序：
数据元素太多不能同时放在内存中，根据排序过程的要求不断在内外存之间移动数据的排序。
4.插入排序：
从第二个数据开始遍历数组，在遍历数组的过程中，用临时变量保存当前下标的值，并且不断和之前的数据进行比较，未找到比当前下标数据小的值就不断让前面的数据往后覆盖，最终将当前下标的值放在0下标，如果在和之前的数据进行比较的时候找到了比当前下标小的值的数据，就插入到这个数据的后面。（希尔是插入排序的优化）
（1）代码思路：
如果只有一个数据就不需要排序，所以外层循环的下标是从1开始的，这里是通过tmp保存当前i下标的值（必须用tmp的临时变量来保存当前i下标的值，不能直接使用array[i]在进行插入数据的时候来作为比较值，因为在插入数据 的时候，如果当前i下标的值小于前一个数据的值，那么前面一个数据的值就会覆盖当前i下标位置的值，那么此时array[i]的值就不是一开始那个数据了，就发生了改变，这是细节！），再通过内层循环遍历0~i-1的数据中是否存在比tmp小的数据，如果比tmp小，那么这个数据插入该下标数据的后面，并且退出循环，如果数据中不存在比tmp数据小的数据就一直遍历并且把每一个数据向后移动因为这些数据都比tmp的数值大，直到遍历的下标小于0就结束，如果循环结束并且没有比tmp小的数据就让0下标的数据值等于tmp，因为此时tmp的值就是最小的。需要注意的是把array[j+1] = tmp;写在外面就是为了当tmp遍历完数组，使0下标的数据等于tmp并且也可以在比tmp小的数据后面插入数据。（时间复杂度：O（N^2） 空间复杂度O（1） 稳定性：稳定（如果把array[j] > tmp改成array[j] > =tmp就变成不稳定的排序了））优点：越有续越快
（2）希尔排序（缩小量排序）：
（思路：通过一个数值gap来将一个数据不断分成几组数据，并把每组数据进行插入排序的操作，然后再减小gap的大小，以此把数据分成组数更少的几组数据，再进行插入排序，当gap=1的时候分为一组再进行最后一次插入排序就结束，此时的数组就是有序的，其本质是在于不断把复杂的数据变的有序使插入排序的速度变得更快。需要注意的是gap的值也就是如何分组是不确定的，还有就是我们在进行插入排序的分组时，是通过当前数据和距离当前数据gap大小的数据进行分组而不是相邻的数据进行分组。（图二当gap = 2的时候的分组，黑线为一组白线为一组，也就是前面说的相距gap为一组的意思是gap等于几就会分几组数据，并且会让相距gap大小的数据为一组）所以当我们拿到第一个gap的时候，就让此时i下标等于这个gap，因为他是第一组数据的第二个数值，j下标就为i-gap就为第一组的第一个值，然后进行插入排序，并且j = j - gap，因为需要与这一组的数据比较，而不是这个数据之前的所有数据比较，所以不是j--。这里外层循环i++是因为下一个数据就是另外一组数据了，这样就可以把每一组数据都进行插入排序。而不需要在重复进行另一组数据的排序。时间复杂度（O（N*log以某个数为底数 N为对数））空间复杂度是O（1），稳定性：不稳定）（对插入法进行了优化）
5.选择排序：
选择排序我可以叫为找最大最小值下标来进行排序，在找最大值下标的时候需要判断最大值是否就是起始位置的下标，如果是的话就需要让最大值数据的下标等于最小值数据的下标。当找到最小值的时候，最小值的数据和起始位置的数据进行了互换，那么此时的最大值数据的下标就是被换之后的下标，所以才要用最大值的下标等于最小值的下标。
（1）思路：
先假定i下标的数据最小，拿去和剩下的数据比较，找到最小的数据和i下标的数据进行交换位置，当遍历完数组就完成了。（时间复杂度是：O（N^2），空间复杂度是：O（1），稳定性：不稳定（不稳定的数组案例：arr = [5 8 5 2 9]））
（2）思路：
优化选择排序的基础上在找最小值的时候增加了找最大值，这里需要注意的是，此时最小值进行了值的交换，那么第一个值（最大值）就不在left的下标了，此时就需要去判断我们找到的最大值下表是否为left，如果还是left也就是刚刚说的情况那么就需要让maxIndex等于minIndex再进行交换不然就会导致排序有问题。
6.冒泡排序：
先排序后面的数据，再根据数组长度减去已经排过序的趟数的大小就是后面趟数排序的范围，（趟数等于长度-1（不优化的情况下））
思路就是遍历数组把最大的换到最后。时间复杂度：O（N^2） 空间复杂度O（1） 稳定性：稳定：
7.快速排序：
一个看成树的排序，通过递归不断的使用Hoare或者挖坑法来进行排序并且找到基准值再进行子树的排序，直到所有数据有序位置。
（1）排序思路：
找一个 基准值拿来作比较，给数组起始位置和结束位置定义left和right，先从右边找数据小于基准值的下标，然后找左边大于基准值的数据的下标，然后给这两个数据交换位置，最终比较完数组，基准值左边为比他小的，右边是比他大的。此时可以看成左右子树，然后就再对左右子树进行同样的排序。（时间复杂度：O（N*log2 N）最好的情况，最坏的情况是O（N^2） 空间复杂度：O（log2 N）稳定性：不稳定（不稳定的数组例子：8 5a 5b 9 10））
（2）解释时间复杂度的问题：
最好的情况是因为第一次遍历找到基准值之后，基准值的左边就是比他小的，右边就是比它大的。那么此时可以看成二叉树的遍历的过程，每次数据都减少一半来进行递归遍历，并且左子树遍历完回归到基准值在进行右边的遍历也是同样的方式进行的，那么此时就可以看成两边是一起进行的（这样好理解），那么每层的都是进行遍历数组，每层的时间复杂度就是n，那么树的高度×每层时间复杂度就是快速排序最好的情况，那么就是O（N*log2 N） 最坏的情况就是有序的情况下，基准值在最左边的第一个数据，那么此时只进行右边的进行，那么此时有n个数据就有N层树的高度，那么此时就是树的高度N*每层遍历数据的时间复杂度N，就是N^2。
（3）解释空间复杂度：
快排并没有开辟空间，但是使用了递归，递归会开辟栈帧。递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度。每次递归所需要的空间大小都是一样的，而且就算是第N次递归，每次递归所需的栈空间也是一样的，所以每次递归中需要的空间是一个常量，并不会随着n的变化而变化，每次递归的空间复杂度就是O(1)每次递归所需的空间都被压到调用栈里（压栈），所以快速排序的空间复杂度就是递归算法的空间复杂度 = 每次递归的空间复杂度O(1) * 递归深度。非顺序:空间复杂度=深度：O(log2 N) 顺序:空间复杂度=深度：O(N)
（4）Hoare法代码思路：
第一次排序的时候先拿最左边的数据作为基准值，此时拿来比较这个数组，我们给数组的起始位置和结束位置定义为left和right，先从右边遍历找到比基准值小的数据的下标，然后再找左边比基准值大的下标，需要注意的是，在找下标的时候，left还是要小于right，找到时候让left和right下标的元素互换位置，当left和right相等的时候，就比较完了。然后最后此时将left和right相遇的下标的数据和基准值数据交换位置，此时基准值左边为比他小的，右边是比他大的。然后在对基准值的左右进行相同的排序就可以了，需要注意的是，进行左边数据的递归的时候，传入的是此时基准值下标-1为左边结束的下标，右边下标起始位置为基准值的下标+1。当此次排好序之后，递归的起始位置大于等于结束位置。就可以直接回归上一步了。（需要注意的是，当left和right相遇的时候，我们需要把此时的位置记录下来，那么这里是通过写了一个函数来进行查找的也就是Hoare法，但是这里需要注意的是，我们传入的起始位置不能是0，因为当此时是右子树的时候，右边的起始位置是par+1，而不是0，所以查找par下标的时候，起始位置是传入的start，而不是0，并且右子树也有左子树，所以判断左边的时候，起始位置也应该写start而不是0）
（5）挖坑法代码思路：
和Hoare法差不太多，就是挖坑法是直接把第一个数据挖出，然后作为比较值，如果右边的数据比比较值小，直接填入此时第一个数据也就是left下标，然后此时被挖出填入left的坑的数据的原来位置就空了，那么此时开始从左边找比比较值大的数据，找到之后填入右边的坑，如此循环往复，最后left和right相遇就让比较值填入这个坑，然后也形成了左右子树，再进行相同的操作即可。
（6）前后指针（了解）：
同样拿第一个数据来当作基准值来进行比较大小，并且此时定义prev和cur两个指针，通过++prev来判断下++prev之后的下标和cur是否相等，如果相等就不进行交换数据，如果不相等才进行交换数据，要注意的是，当array[cur] < array[left]不成立的时候，就不会进行后面语句的判断也就导致了prev不会++了。当cur超出了right的大小，再把基准值拿来放到prev的位置上，这样左边就是比基准值小的值，右边就是比基准值大的值了。
（7）优化1：
三数取中法是通过让有序的数据变得不那么有序，这样可以减少时间的消耗。原理就是把第一个数据作为数组中的小数据和最后一个数据看成大数据，mid是除了这两个之外的数据都可以，这里找的是下标为中间的数据，然后通过这三个数据的比较大小，处于中间大小的哪个数据就放在首元素的位置，这样数据就不会趋于有序，减少了快速排序所需要的时间。（在排序之间进行三数取中法如图二）
（8）优化2：
快速排序的后续进行的时候，数据越来越趋于有序，那么此时我们可以在快速排序的过程中加入插入排序，这样快速排序就会更加的快速，不会栈溢出。因为此时可以减少递归的次数，就不会增加栈帧的个数。相当于左右子树减少了遍历。可以减少很多数据的遍历。（是在递归到后面的子区间比较小的时候进行插入排序而不是一开始就进行插入排序，因为子区间进行递归就会有很多子区间不断的去递归，因为这时已经趋于有序了不需要一直递归浪费空间和时间。）
（9）快速排序的非递归：
通过栈来实现，先分别对left和right赋值为0和数组长度-1，在找到par的下标，并且找到par下标的时候就进行了一次排序，实际找par下标就是进行排序的过程。（先压入数据是为了进入循环，循环的条件是当栈不为空的时候进入，栈为空就代表循环结束了）此时就压入左子树的起始位置和结束位置，再对右子树进行压入起始位置和结束位置（两次压栈操作必须是相同的，要么是先压入起始位置要么就是先压入结束位置，方便后续再循环中拿出起始位置和结束位置来进行排序），然后进入循环，出栈两个值，分别作为right和left，然后再找到一个新的基准值（又进行了一次排序），与未进入循环之前的操作一样，进入循环是为了让不断对数据进行排序，直到数据有序为止。需要注意的是，这里是否有左右子树是通过par和当时再找par的left和right来比较，如果par>left+1（起始位置和结束位置之间还有一个数据，就需要进行排序），就说明有左子树，如果par < right - 1就说明有右子树，以上两种情况就可以入栈left和right的下标，不断地压栈和出栈，并且找par基准值的下标，当栈为空的时候也就是排序结束的时候。
8.归并排序：
将数据通过递归的形式不断的分解成范围更小的数据，再通过把这个小范围的数据分为两组数据进行比较，这两组数据都有起始下标和结束下标，一开始都是通过起始下标来进行比较数据的大小，最后把数据放在了临时创建的数组里面，在把临时数组的值的顺序放入原数组中。
（1）思路：
不断的通过找数组的中间下标，来对一个数据不断的进行分解，当每一个数据的左边不断分解，直到分解为一个数据的时候返回，（这里拿8个数据来举例）此时就有两个数据，然后走数据的右边，也只有一个数据就返回，此时左右走完，就进行对这个小范围的数据进行排序，排好序之后再返回到上一级，此时就有四个数据，然后进入右边（此时就只有两个数据了，因为进入右边的时候又要进行分解），然后再从左边分解到一个数据返回，此时又是两个数据，然后进入进入右边来分解成一个数据，又返回此时再进行排序之后，返回到四个数据，然后此时再对这四个数据排序。以此往复。（合并和分解是在一起的，而不是把每个数据分解了才进行合并）
（2）代码思路：
先传入0下标和最后一个数据的下标位置，然后把此时的中间坐标算出来，然后进入左右的递归，左边的递归的right就是mid的下标，右边递归的起始位置就是mid+1的下标，结束位置还是right。当有两个数据的时候我们就会进行排序，排序的思路就是把数据分成两组，第一组的数据起始位置就是left下标，结束位置就是mid下标。第二组数据的起始位置就是mid+1下标，结束位置是right。分别比较s1和s2下标的数据，谁小就把谁的数组放进我们临时变量的数组，当第一组数据的起始位置大于结束位置或者第二组数据的起始位置大于结束位置就结束循环，但是这里就可能由一组数据没有进行循环，所以我们就需要再对数据进行判断，若s1小于等于e1或者s2小于等于e2我们就直接把剩余的数据直接添加到临时数组的后面就行了，最后在进行数组的拷贝就完成了排序。
（3）时间复杂度：
O（N*log2 N）空间复杂度：O（N） 稳定性：稳定
（4）非递归的归并排序：
思路：通过定义一个gap来确定left，mid和right的下标位置（mid = left + gap - 1; right = mid + gap 巧妙的实现了把一个数组进行了分解然后再不断归并成数据的过程），从而实现分解并归并数据，gap的值小于数组的长度，并且gap是成二倍增长，先是小范围的进行排序最后不断将排序的数据范围增大，最后直到比数组的长度还大的时候就 排序完成，需要注意的是，mid和right下标可能会越界此时就需要判断这两个值得下标位置，越界了就都指向最后一个数据的位置就行了。还需要注意的是在内层循环也就是进行数据分解的时候，i每次的增加量是两倍的gap大小，这样才能让left的下一次位置在right的右边。每次拿到left，mid和right下标的时候我们还是用的归并的排序方法来排序的。
5.归并应用：
9.习题
1.选A
2.选C：题设意思是先把前面的排为有序的时候，开始排这个45的数据，并且是从后面开始比较的，一共比较了5次。
3.选D:
4.选B:
5.选D:
6.选A：一般用挖坑法，其次是Hoare，最后才是前后指针。
10.其他基于非比较的排序（了解）
1.计数排序：
思路就是通过用户创建一个数组来记录每个下标对应的数据出现的次数，记录完次数，遍历计数数组来进行把数据在原数组里面排序。需要注意的是，这里需要找到最大值和最小值才能进行创建数组，并且记录数据的时候需要当前数据的大小减去最小值，目的是为了减少数组空间的浪费。在进行数组的排序的时候，需要定义一个k来作为array数组的下标，这样才能从记录数组中把数据放在原数组当中。
2.基数排序：
拿出十个队列，先把每个数据的个位与每个队列的下标进行比较，如果相同就放入队列当中，直到把数据放满。此时数据放好之后再把数据按照队列先进先出的方式拿出来，顺序还是从队列的下标0~9的顺序进行出队，数据拿出之后，在比对数据的十位和队列的下标是否相同，和个位一样的方式放进去再拿出来，以此往复直到数据的最高位，最后一次拿出来的时候数据就有序了。
3.桶排序：看图
)
