排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
插入排序分为两种，一种是简单插入，一种是直接插入。
1.1(简单插入)
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
依次类推直到全部有序为止。
直接插入总结：
1.时间复杂度为O(N^2)
时间复杂度我们就看一个算法的最坏情况。
最坏的情况下,从无序数组中拿一个值放到有序数组中遍历一遍前面已经排好的有序数组，从第二个值开始，第一次找1次，第三个值找两次，以此类推，也就是1+2+3+....n-1。用Sn=n(n+1)/2算出时间效率为O(N^2)。
2.空间复杂度总结
没有开辟新的空间,只是用到新的变量，所以为O(1)。
我们会定义一个变量gap，gap是相邻为gap的元素进行交换，希尔排序分为两步(1)预排序(只要gap不为1就是预排序)，预排序的意义：大的数更快跳到后面去，小的数更快跳到前面来，gap越大跳的越快，越不接近有序，gap越小跳的越慢，越接近有序，当gap==1时候，直接就相当于直接插入排序。在gap的前几次排序后，当为gap==1时候，这时候数组相邻的数的大小基本就是相差为1左右(对于举例数组来说)，就可以把数组分为有序。
和无序两块区域，然后以直接插入算法排序。
下面是希尔排序的两种算法：
希尔排序总结：
时间复杂度：我们按最差情况来分析，我们在分析时可知，当gap==n/3时候，若整个数组逆序，gap==n/3的数组，每组比较(1+2)，也就是n/3*3；若gap==n/9的数组，全部逆序，每组比较36(1+2+3+4+....8)，也就是n/9*36=4n次，但当gap==1的时候，无线接近n次。因此我们可以通过结论来画出一个关联图。
时间效率我查询资料为O(N^1.3)，
空间复杂度：O(1),没有开别的空间。
3.选择排序
这是没有优化之前的代码 (按升序)，选择排序代码就是把数组分为已排序和待排序的两部分，第一次是拿数组的第一个当已排序的数(其实并没有排)。之后每一次就是拿已排序的最后一个和待排序的其中一个最小值进行交换，如果没有就自己交换自己。
简单选择总结：
时间效率:O(N^2),每次查找交换就是遍历数组，N次查找就是N^2。
空间效率:O(1)
优化后版本：
优化前我们 一次遍历我们只找一个值并把它按正确位置排好，优化后我们可以一次遍历同时找到最小值和最大值。
这里会有错误：
当max和begin 重合时就发发生错误，begin先和min交换，然后才交换max和end，所以交换数字错误，因此写代码这里要加一层判断，当max==begin时候，把min的位置赋给max。
4.堆排序
堆排序我认为是排序算法中比较难理解的算法。因为要各种换来换去的，如果不熟悉很容易晕。
堆排序分为两步：
1.建堆：
将一堆无序的数按建大根堆或者小根堆的规则建立起来。
大根堆:根结点的元素是最大的，并且根的左右孩子的比它小，也可以叫父亲结点，以此类推，小根堆就是它的相反过程。
如图所示就是一个大堆。
在完全二叉树，下面每一层结点个数都是上一层的两倍，最后一个下标减1除以二就是最后一个非叶子结点的下标。
这里面执行四次操作，需要四次循环，在下面的排序代码中进行循环。
2.排序
排序就是每次将堆顶的元素和堆的最后一位进行交换，然后接着将剩余n-1个元素再次建堆，接着交换堆顶和第n-2个元素，后面重复此操作，直到全部有序。
堆排序总结：
时间效率: O(N*logN) ,因为在 每次将堆顶元素交换后，需要重新建堆，需要遍历堆中剩余所有元素。
空间效率：O(1)
5.冒泡排序
冒泡排序总结:
时间效率:排好一个数要遍历一遍数组，所以排好N个数要O(N^2)的时间效率。
空间效率：仅开了一个遍历tmp所有空间为O(1)。
6.快速排序
1.
2.快速排序的优化
快速排序对于无序的序列来说，排的非常快O(N*logN)，但对于有序序列或者接近有序序列来说,需要O(N^2)，差距是非常明显的，因此我们需要在任何一次排序前对当前序列进行一次优化，叫三数取中。三数取中就是将序列第一个和最后一个数的下标除以2，得到一个中间下标，然后比较这三个下标对应的值，取中间大小的值把它与第一个交换，然后让它当keyi。这样的目的是让每次排序都可以更快速的让大值往后走，小值往前走。
无序序列：
快速排序总结:
时间效率:O(N*logN)。
空间效率:O(1)。
7.归并排序
归并排序总结:
时间效率(N*logN)。
空间效率O(1)。
如果觉得有帮助，麻烦一件三连。