本文目标
掌握七大基于比较的排序算法基本原理及实现
掌握排序算法的性能分析
掌握 java 中的常用排序方法
概念
排序
排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 平时的上下文中，如果提到排序，通常指的是排升序（非降序）。
通常意义上的排序，都是指的原地排序(in place sort)。
稳定性(重要)
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
例如此处有两个5，5(a)这个数字在排序前就一直在5(b)的前面，在排序后，5(a)这个数字仍在5(b)的前面，就说说明这写的排序是稳定性排序
来记住两个结论：
1:我们认定如果当前这个排序中，在排序的过程当中，没有发生跳跃式的交换，那么我们就认为这个排序是稳定的排序
例如之前的堆排序就不是一个稳定的排序，因为它发生了跳跃式的交换
2:
如果一个排序是稳定的排序，那么它也可以被实现为一个不稳定的排序
但是如果一个排序本身就是不稳定的排序，那么就不可能实现为一个稳定的排序
七大基于比较的排序-总览
插入排序
直接插入排序–原理
现在假设我们要对如下的数组进行排序：
10，6，3，1，8
直接插入排序的思想是这样的:
1：先定义一个变量i来遍历我们的数组，此时要注意的是数组的第一个元素为10，已经为有序的，所以i此时指向我们的第二个元素6
2:此时我们就要想啦，6这个元素到底插入到哪里呢？我们发现需要6<10,所以需要插入到10的前面，但是10这个元素总的需要被记录下来把，于是我们就定义j这个下标，它的值等于i-1:如下所示：
3:此时再定义一个tmp变量用于存储我们i下标的值，然后每次判断j下标的值与tmp存储的值的大小：此时tmp存储的值为6，如下所示：
4：此时10>6,则让10往前走一步，到了1下标的位置，然后让j- -,我们会发现此时j=-1,-1的位置是没有元素的，所以就把tmp中的6放入到我们0下标的位置，如下图所示:
此时我们认为已经发生了一次直接插入排序了.
5:此时6和10就已经有序了，那么就让i++，此时i走到了2下标的位置，同时让2下标的位置的3元素放入到我们tmp变量中，让j指回我们的i-1下标处，也就是我们1下标处：如下图所示：
6：然后此时我们j所指向的元素10>3,所以10就往后移动一格到了2号下标处，然后j- -,后指向了1号下标处，此时1号下标处的6>3,那么6就移动到了1号下标位置处，然后j- -,后到了-1下标处，-1下标处此时没有元素，所以就把3放入到0号下标处：如下图所示：
7：此时接着往下走，i此时++后指向了我们的3下标处，j此时指向的下标为i-1=2处，然后把3下标处的值放入tmp中，如下所示:
8:还是重复刚才的步骤，只要j指向的元素大于1，这个元素就往后移动一个格子，然后j–,直到j=-1后，把我们tmp中所存储的值插入到空的格子当中即可，最后的示意图如下所示:
9:此时i继续++后指向了我们4下标处，j此时指向的下标的值为4-1=3，然后将i所指向的值8放入到我们的tmp当中去，如下图所示:
10:然后j下标所对应的元素为10，10>8，所以10移动到了4下标处，然后j- -后到了2下标处，此时6<8,那就直接把8放到j+1的位置即可
至此我们这个数组就完成了由小到大的排序。
代码实现
public class TestSort { public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int tmp = array[i]; int j = i - 1; for (; j >= 0; j--) { //注意此处应该为>,不应该为大于等于，因为大于等于就不是稳定排序了 if (array[j] > tmp) { array[j + 1] = array[j]; } else { break; } } //写到外面是以防循环走完了tmp中的元素还没有插入到对应的位置 array[j + 1] = tmp; } } public static void main(String[] args) { int[] array = {1, 14, 35, 7, 68, 79}; //排序前的数组，结果为：[1, 14, 35, 7, 68, 79] System.out.println(Arrays.toString(array)); insertSort(array); //排序后的数组，结果为[1, 7, 14, 35, 68, 79] System.out.println(Arrays.toString(array)); } }
注意事项
一.
首先我们再写比较的时候要注意是array[j] > tmp，原因是如果写成大于号就能确保我们直接插入排序是一个稳定的排序算法，我来举个例子：
就拿刚才的数组来说把：假设我们把数组变换一下,变换成如下数组：
10，6(a)，3，1，6(b)
那么还是按照刚才的步骤一直走，走到最后一步的示意图如下所示：
此时我们最后一个元素要插入到j+1下标处的时候先要进行array[j]与tmp的值的判断，此时array[j]=6(a),tmp=6(b)，假设6(a)在排序前就一直在6(b)的前面，那么我们直接插入法为了保证是一个稳定排序，也一定要保证排序后6(a)仍在6(b)的前面，当array[j]>tmp的时候，是可以保证6(a)仍在6(b)的前面，但是当array[j]>=tmp的时候，此时我们6(a)就直接跑到了array[j+1]处，然后我们的6(b)就跑到了aray[j]处，很明显这就是一个不稳定排序.
所以直接插入排序我们是可以把它实现成一个稳定排序的，既然可以实现成一个稳定排序，就不要实现成非稳定排序,如果面试官问直接插入排序是一个稳定排序还是非稳定排序，答案当然是稳定排序
二.
我们在i循环内，j循环外最后要写上array[j+1]=tmp，因为按照正常逻辑的话这句话应该写在j循环的else语句内部，但是会有一种特殊情况，当j循环完毕后可能tmp中的元素还没有插入到array[j+1]处，所以此时应该把这句话写到i循环内，j循环外部.
三.
关于直接排序算法的时间复杂度和空间复杂度:
此时需要分为两种情况:
(1)当需要排序的数组为无序的情况
时间复杂度：O(N 2 N^{2}N
2
)
空间复杂度: O(1)
(2)当需要排序的数组为有序的情况
例如这样一组数组：2，3，4，5，6
我们会发现当我们定义i和j的时候，j根本用不上，只有i一直在遍历，所以在需要排序的数组是有序的情况下，时间复杂度可以达到O(N),空间复杂度仍为O(1),在后面的排序中在最好的情况下时间复杂度可以达到O(N）的恐怕也只有直接插入法排序了
所以童鞋们要注意啦，假如此时笔试题出了这样一道题目:
问当前有一组待排序的序列，但是这组待排序序列大部分是有序的，请问，哪个排序更合适？
答：当然是选择直接插入排序
另外直接插入排序还会用到很多排序的优化上,例如快速排序
四.性能分析
希尔排序(了解，基本不考)
前提
假设10000份数据如果直接使用希尔排序的话，其时间复杂度为O(N^2),也就是10000 * 10000 = 1 0000 0000
但是如果我们将这10000个数据分成100份的话，每份相当于有100个数据，那么对每份数据进行插入排序的话，每份数据的时间复杂度为O(N^2),最终每份数据相当于100100，一共100份数据就是100100*100 = 1 0000 00，
我们会发现使用了分组法之后的时间复杂度明显下降了非常多，而分组法就是对希尔排序的核心思想。
原理
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有 距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时， 所有记录在统一组内排好序。
1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
假设有一组需要使用希尔排序的数据如下所示:
此时一共是15个数据.
1：一开始我们就分为五组:每组三个数据，所以图中有五条彩线
注意每个数据的中间差四个数据
然后先对红色线的数字进行直接排序，先排12和8
此时注意，按照之前的直接排序我们肯定会直接将i指向7然后，j指向12，然后再进行排序，但是希尔排序此处并不是这样的，此时我们的i应该指向12的下一个数字27，然后j指向8的下一个数字5，我们会发现此时到了蓝色线所对应的数字，然后再进行直接排序，排序完成后继续往下走，i指向58，j指向9，然后在进行直接排序，就这样依次往下循环往复，最终第一轮按照五组的排序的结果如下所示:
2:此时我们再分为三组，每组五个数据:
此时就有了三个颜色的线
然后再将i指向16，j指向7后进行直接排序，排完序后让i指向0，j指向4后继续进行直接排序，直到最终完成第二轮的排序，结果如下所示:
3：此时将整体看为一组再进行最终的排序
也就是将i指向0，j指向5，然后按照之前我们所讲的直接排序方法进行排序即可,因为整体已经趋于有序了，所以此时整体看为一组，速度更快.
在这里解释一下为什么我们要使用5，3，1作为我们的分组
1：首先5，3，1叫做增量数据，并且希尔排序中的这个取值也一定是一个素数，也就是我们的质数.假设我们使用2就不行，因为2不是质数.
并且注意增量序列的值没有除1之外的公因子，并且最后一个增量值必须等于1.
2：在解释下什么叫做增量，例如我们分为五组的话，每组是三个数据，如果分为三组的话，每组是五个数据，最后分为一组的话。每组是十五个数据，所以最终我们所获取的每组的数据是保持上升态势的，这样的情况就叫做增量.
代码示例
public static void shell(int[] array ,int gap) { for (int i = gap; i < array.length; i++) { int tmp = array[i]; int j = i-gap; for (; j >= 0 ; j = j-gap) { //如果这里是一个大于等于号 此时这个排序就不稳定了 if(array[j] > tmp) { array[j+gap] = array[j]; }else { //array[j+1] = tmp; break; } } array[j+gap] = tmp; } } /** * 了解： * 时间复杂度：O(1.5) O(n^2) * 空间复杂度：O(1) * 稳定性：不稳定 * @param array */ public static void shellSort(int[] array) { int[] drr = {5,3,1};//增量数组--> 16 5 3 1 for (int i = 0; i < drr.length; i++) { shell(array,drr[i]); } }
性能分析
选择排序
原理
假设此时有一组需要通过选择排序的数据如下所示:
1:首先定义两个下标，i和j,i指向第一个元素，j指向i+1所对应的元素，假设此时j所指向的元素大于i的话，那么就交换两个数据，如下所示:
2:然后将j这个下标继续向后移动，发现9比5大，那就继续朝后移动，到了16发现比5大，继续往后移动到了6，发现6比5大，欧克此时j继续往后走以后，这一趟就结束了，不再动了。
3:此时i继续往下走，走到了12这个位置，j走到i+1的位置也就是我们的9这个位置：
此时9<12，欧克交换位置：
然后j继续往后走发现6比9小，那就继续交换位置：
这一趟走完了，继续下一趟:
4:此时i指向12，j指向16，16大于12，j继续往下走，发现12大于9，则交换：
这一趟结束
5：继续下一趟，i指向16，j指向12，然后16>12，则进行交换，最终排序完毕.
代码示例
public class MapDemo1 { public static void chooseSort(int[] array) { for(int l = 0;l < array.length-1;l++){ for(int k = l+1;k < array.length;k++) { if(array[l]>array[k]) { int tmp = array[l]; array[l] = array[k]; array[k] = tmp; } } } } public static void main(String[] args) { int[] array = {12,5,9,16,6,23,1,45,24,13}; chooseSort(array); System.out.println(Arrays.toString(array)); } }
性能分析
