手撕八大排序（上）

排序的概念及其引用：

排序的概念：

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的；

画图说明：

排序前A在B前面，排序后说明该排序稳定，如果排序后B在A前面则说明不稳定。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

八大排序我们一般将其分为五类，分别为：

一：  插入排序

1. 直接插入排序

2. 希尔排序

二： 选择排序

1.直接选择排序

2.堆排序

三： 交换排序

1. 冒泡排序

2. 快速排序

四： 归并排序

五：基数排序

插入排序：

直接插入排序：

基本思路：

思路：从第二个数开始，假设此数为 tmp ，逐个往前进行比对，如果前数大于 tmp ，就将前数值赋值到 tmp 处，然后继续往前比对，直到找到小于或等于 tmp 的数（或者比对至数据首）就停止，最后将 tmp 的值赋值到此处就行了

动图演示：

代码：

 public void insertSort(int[] array) {if (array.length == 0) {return;}for (int i = 1; i < array.length; i++) {int temp = array[i];int j = i - 1;for ( ; j >= 0 ; j--) {if (array[j] > temp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = temp;}}

 直接插入排序总结：

1. 集合元素越接近有序，时间效率越高

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1)

4. 稳定性： 稳定 

希尔排序：

前言：

既然同为插入排序，那必然是有共同点的。

希尔排序是建立在直接插入排序基础上，经过优化的插入排序。

希尔排序分为两步：

• 1、预排序，使得数据尽可能接近有序
• 2、直接插入排序，最后调用一次直接插入排序，快速的完成排序

基本思路：

思路：预排序是通过区间划分实现的，假设当前区间为 gap，那么 1、1+gap*n 可以分成一组，同理2、3、4 都可以分，将这些组分别进行直接插入排序（数据少，效率高）。每完成一次分组排序，gap 就会缩小，直到 gap 为1时，进行一次直接插入排序，整个希尔排序就完成了

代码如下：

public static void shellSort(int[] array) {int gap = array.length;while (gap > 1) {shell(array,gap);gap /= 2;}//整体进行插入排序shell(array,1);}public static void shell(int[] array,int gap) {for (int i = 1; i < array.length; i++) {int temp = array[i];int j = i - gap;for ( ; j >= 0 ; j-= gap) {if (array[j] > temp) {array[j + gap] = array[j];} else {break;}}array[j + gap] = temp;}}

动图演示：

预排序：

 直接插入排序：

希尔排序总结：

1. 希尔排序的时间复杂度要用到高数中的知识，“根据大量的数据的得到了局部的结论...”，我们直接记答案即可：O(N^1.25)

2. 空间复杂度： O(1)；

我们仅仅只创建了一个gap

3. 稳定性： 不稳定；

我们在排序过程中gap会有多次的改变，不同的组别中可能会发生交换现象。

选择排序：

直接选择排序：

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

代码：

//选择排序public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if(array[j] < array[minIndex]) {minIndex = j;}}int temp = array[i];array[i] = array[minIndex];array[minIndex] = temp;}}

如果像这样去遍历的话，时间复杂度为O(N^2)不算是个很优解我们可以考虑对此进行优化

优化：每次遍历选最大与最小，分别与 end 值和 begin 值交换

动图演示：

 直接选择排序总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

堆排序：

我们之前也介绍过堆排序，PriorityQueue本质就是个小根堆，这里就不过多介绍了。

思路：堆排序用到了堆的知识，如果想排升序的话建大堆，因为大堆中堆顶是最大值，将堆顶值与堆低值交换后，执行向下调整，使其再次变为大堆，就这样反复交换、调整，堆排序就完成了。

 /***  堆排序* @param array 目标数组*/public static void heapSort(int[] array) {createBigHeap(array);int end = array.length - 1;while (end > 0) {swap(array,0,end);shiftDown(array,0, end);end--;}}public static void createBigHeap(int[] array) {//父下标 从倒数第二层开始int parent = (array.length - 1 -1) / 2;for (; parent > 0 ; parent-- ) {shiftDown(array,parent, array.length);}}public static void shiftDown(int[] array,int parent,int len) {int child = 2*parent + 1;while (child < len) {if (child + 1 < len && array[child] < array[child + 1]) {child++;}if (array[child] > array[parent]) {swap(array, parent, child);parent = child;child = 2 * parent + 1;} else {break;}}}private static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

向上调整动图演示：

 堆排序总结：

1. 堆排序使用堆来选数相对于直接插入排序，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

本文只是排序的上半部分，涉及的排序思想都还算简单，下一篇文章中将会介绍排序大哥：快速排序，知识点很难敬请期待吧。