目录
1.直接插入排序
思路：
代码以及解析
2.希尔排序
思路
代码以及解析
3.选择排序
思路1
代码1以及解析
思路2
代码2以及解析
4.冒泡排序
思路
代码
5.堆排序
思路
代码以及解析
6.快速排序
思路1（Hoare版）
编辑
代码1
思路2（挖坑法）
编辑
代码2
思路3（前后指针法）
代码3
快速排序的优化
思路4（非递归法）
代码4
7.归并排序
思路1（递归法）
代码1
思路2（非递归法）
代码2
1.直接插入排序
思路：
实际生活中我们在玩扑克牌的时候，当我们在整理牌的时候我们用到的排序就是直接插入排序
那么我们根据扑克牌这个思想来描述直接插入排序的过程就是
选定一张牌为基准向前不断地比较
如果这一张牌比前面的牌要大，那么就插入进去前面这一张牌的位置
如果这一张牌比前面的牌要小不插入，继续向前进行比较，直到插入进去为止
代码以及解析
public static void insertSort(int[] arr){for (int i = 1; i < arr.length; i++) {int j = i - 1;int tmp = arr[i];for (;j >= 0; j--) {if (tmp < arr[j]){arr[j+1] = arr[j];}else {arr[j+1] = tmp;break;}}arr[j+1] = tmp;//如果是最后一个结束那么结束循环之后还要将值放进数组里面}}
既然是通过不断的向前比较那么我们就应该定义两个for循环
一个外循环来遍历我们的数组，一个内循环来遍历当前数字往前的数据并不断的比较
所以我们就有了这两段代码
int j = i - 1; 以及 for (;j >= 0; j--)
那么设计好循环以后我们就要开始进行比较了
我们先用一个tmp来记录当前i所在下标的数据，然后通过j下标来进行不断的比较
如果我们tmp的数据是小于 j 所在下标的数据的，那么j下标的数据向后移动一位
当我们发现j所在下标的数据是 小于tmp的那么我们直接在j下标的后一位进行插入
arr[j+1] = tmp;
为什么我们还要在最后一行再写一次这段代码呢？
因为我们假设当 j 下标是整个数组最小的值
那么当 j 下标走到了 -1 的位置，如果我们不加上这一行代码
那么我们就不能把最小数添加到数组里面
所以为了防止这种情况的发生我们需要再写一次这段代码
直接插入排序适用于数据量比较小而且相对来说趋于有序的情况
这个时候使用直接插入排序那么速度是最快的
2.希尔排序
思路
本质上是直接插入排序的优化
通过分组来进行直接插入排序，每隔gap个元素就分为一组
然后再将gap进行降低，再分成一个组
最后当gap为1的时候，这个时候的数据是趋于有序的，那么再次使用插入排序就会很快
用图解的形式表示
当gap = 5的时候我们就这样进行分组，然后对每一个组使用直接插入排序
当gap = 2的时候我们就这样进行分组，然后对每一个组使用直接插入排序
最后当gap = 1的时候我们再次使用直接插入排序，这个时候的排序时间复杂度就大大减低了
代码以及解析
public class ShellSort {public static void shellSort(int[] arr) {int gap = arr.length;while (gap > 1) {gap /= 2;shell(arr, gap);}}public static void shell(int[] arr, int gap) {for (int i = gap; i < arr.length; i++) {int tmp = arr[i];int j = i - gap;for (; j >= 0; j-=gap) {if (arr[j] > tmp){arr[j+gap] = arr[j];}else break;}arr[j+gap] = tmp;}}}
关于gap值，我们每次都对其进行除2的操作，使用一个while循环直到 gap = 1
对组内的直接插入排序操作，所有的操作都和直接插入排序的操作是类似的
我们需要改变的值是
将外循环的 i 设置为 gap，每次都向后走一位
而对于内循环的j我们就设置i - gap 值
这样就能保证每次j进行排序的位置都是同一个组里面的元素
3.选择排序
思路1
我们的选择排序，先记录第一个元素的值，从第一个元素向后进行比较
然后寻找整个数组里面最小的元素，直到找到为止
当我们遍历完整个数组以后，我们将两个元素进行交换，然后开始比较数组里面的第二个元素
重复上面的操作直到整个数组被遍历完
代码1以及解析
public void selectSort1(int[] arr){for (int i = 0;i < arr.length;i++){int minIndex = i;int j = i + 1;for (;j < arr.length;j++) {if (arr[j] > arr[minIndex]){minIndex = j;}}swap(arr,i,minIndex);}}public void swap(int arr[],int a,int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;}
设置外循环来遍历数组，设置内循环来向后进行比较
我们设置一个minIndex 来记录第一个元素的下标
当我们发现比minIndex下标所记录的元素更小的值时，就更新 minIndex 的值
最后当比较完成以后我们就进行交换
思路2
第一种思路我们是从第一个元素开始寻找最小值然后进行交换，直到数组被遍历完成
那么第二种思路我们可以寻找最小的值给第一个元素，寻找最大值的给最后一个元素
那么我们就可以使用双指针，一个指向第一个元素，一个指向最后一个元素
然后从第一个元素开始寻找最小的元素和最大的元素
最后我们将第一个元素和最小的元素进行交换，最大的元素和最后一个元素进行交换
然后左指针向后走一步，右指针向前走一步，直到两个指针相遇那么就说明数组遍历完毕
代码2以及解析
public void selectSort2(int[] arr){int left = 0;int right = arr.length;while (left < right){int minIndex = left;int maxIndex = left;for (int i = left + 1; i < right; i++) {if (arr[i] > arr[minIndex]){minIndex = i;}if (arr[i] < arr[maxIndex]){maxIndex = i;}swap(arr,minIndex,left);if (maxIndex == left){maxIndex = minIndex;/** Date:11/9* Description:最大值是在第一个位置，那么将最小值换完以后最大值就跑走了* 当我们再次交换的时候换到的就不是最大值了* 所以要赋值让maxIndex = minIndex，这样就是最大值交换了*/}swap(arr,maxIndex,right);}left++;right--;}}public void swap(int arr[],int a,int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;}
我们需要注意的是，当我们的最大元素就在left指针所指向的元素的时候
如果先执行交换最小元素那么我们的最大值以后就找不到了同时我们的排序也会失效
我们用图解的方式来解释
通过这三步我们就可以很清楚的看到如果最大值就在左指针所在的下标是怎么交换的了
所以为了防止这种情况的出现，我们在交换完minIndex以后我们需要找到最大值的位置
于是就有了这么一段代码
if (maxIndex == left){maxIndex = minIndex;}
当交换完最小元素以后那么maxIndex就在minIndex的位置上了
这个时候更新一下maxIndex即可
4.冒泡排序
思路
冒泡排序实际上是两个相邻的元素进行比较
假设有一个i下标 那么这个i下标指向第一个元素，然后i下标和i+1下标两个元素进行比较
如果后面的元素比前面的元素要小，那么两个元素就进行交换后 i下标向后走一位
不断重复上面的操作，直至走位倒数第二个元素
如果后面的元素比前面的的元素要大，那么就继续向后进行比较
操作还是一样的 i下标向后走一位，不断重复上面的操作，直至走位倒数第二个元素
代码
public class BubbleSort {public static void bubbleSort(int[] arr){for (int i = 0; i < arr.length-1; i++) {boolean flg = false;for (int j = 0; j < arr.length-1-i; j++) {if (arr[j] > arr[j+1]){swap(arr,j,j+1);flg = true;}}if (!flg){break;}}}public static void swap(int[] arr,int a,int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;}}
这段代码外循环表示需要走多少趟，内循环则是j下标进行不断地比较
由于只需要走到倒数第二个元素，所以我们只用走arr.length - 1趟即可
那么内循环 我们就只用只用走arr.length - 1 - i趟
为什么？
因为每一趟我们都把最大的元素排序到最后一位了
那么这个时候我们就不需要再重复得走到最后一位进行比较了
我同时对这个冒泡排序进行了优化，当我们发现数组是有序的时候
如果再不断的进行无意义的比较，那么就会提升我们代码的时间复杂度
所以我设计了一个布尔值 flg如果第一趟比较完成以后发现flg 依然是 false
那么就说明没有进行任何的交换，此时数组有序，直接跳出循环即可
5.堆排序
思路
我们在利用堆进行排序的时候首先创建一个大根堆来进行排序，
为什么不是小根堆？难道用小根堆不好吗？
使用大根堆的原因是我们不断的弹出堆顶元素，从后向前进行排序
因为我们知道大根堆的堆顶元素一定是目前堆里面最大的元素
那么我们从第一次弹出的是最大的元素，第二次弹出的就是第二大的元素，那么我们不断地弹出
最后一定是可以拿到从小往大排序好的数
代码以及解析
public static void heapSort(int[] arr){createHeap(arr);int end = arr.length - 1;while (end > 0){swap(arr,0,end);shiftDown(arr,0,end);end--;}}public static void createHeap(int[] arr){for (int parent = (arr.length - 1- 1)/2; parent >= 0 ; parent--) {shiftDown(arr,parent,arr.length);}}public static void shiftDown(int[] arr,int parent,int len){int child = (parent * 2) + 1 ;while (child < len){if (child + 1 < len && arr[child] < arr[child+ 1] ){child++;}if (arr[child] > arr[parent]){swap(arr,child,parent);parent = child;child = (parent * 2) + 1;}else {break;}}}public static void swap(int[] arr,int a,int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;}
我们每弹出一次堆顶元素就向下调整一次
最后当我们的end变成0时那么我们的堆也就排序完成了
6.快速排序
思路1（Hoare版）
对于快速排序我们使用的是分而治之的思想
我们先取第一个值作为基准，然后在基准的两边，使得左边的值小于基准值，右边的值大于基准值
然后又从两边开始重复上述的操作直到所有的元素都排列到应该在的位置
由于采用的是分而治之，所以这就像是二叉树的遍历一样
所以我们就可以采用子问题的思想来解决
代码1
private static int quickSortHoare(int[] array,int left,int right) {int i = left;int pivot = array[left];while (left < right) {//left < right && 这个条件不能少 预防后面都比基准大就会数组越界while (left < right && array[right] >= pivot) {right--;}//right下标的值 小于pivotwhile (left < right && array[left] <= pivot) {left++;}//left下标的值 大于pivotswap(array,left,right);}//交换 和 原来的leftswap(array,left,i);return left;}public static void quick(int[] arr,int start,int end){if (start >= end){return;}int piovt = quickSortHoare(arr, start, end);quick(arr, start, piovt-1);quick(arr, piovt+1, end);}public static void swap(int[] arr,int a,int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;}
1.关于为什么Hoare版快速排序如果左边作为key，就要从右边开始走
反之如果从右边作为key，就要从左边开始走这件事，我看了很多博客好像都没有讲的很清楚
那么我就在这里演示一遍，如果我们将左边作为key同时从左边开始走会有什么后果
我们就可以发现如果是这样子走的话，那么我们最后的基准交换完成以后不能达到
基准左边的值比基准小，基准右边的值比基准大这一原则
2.为什么要在array[left] <= pivot 这里加上等于号？
答案是如果不加上等于号那么如果在数组里面出现了一个与基准相同的数字
当我们在最后两个那么就会陷入死循环，最简单的例子就是首尾都是相同的元素
如果不加上等于号那么从一开始就直接进入死循环
思路2（挖坑法）
挖坑法的总体思路和Hoare法是类似的，只不过是在交换元素的时候有所不同
还是一样的从右边找到比基准小的
左指针不动，右指针不停的走直到找到位置
然后把右指针所指向的元素给到左指针的位置上，然后右指针不动，左指针开始寻找比基准大的值
找到以后把元素给到右指针上，然后重复上面的过程，直到两个指针相遇
代码2
public static void quick2(int[] arr,int start,int end){if (start >= end){return;}int piovt = quickSortDig(arr, start, end);quick2(arr, start, piovt-1);quick2(arr, piovt+1, end);}public static int quickSortDig(int[] arr,int start,int end){int pivot = arr[start];while (start < end){while (start < end && arr[end] >= pivot){end--;}swap(arr, start, end);while (start < end && arr[start] <= pivot){start++;}swap(arr, start, end);}return start;}public static void swap(int[] arr,int a,int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;}
这里我用的是交换的方法，如果是直接进行赋值操作的话需要定义变量来记录下基准的值
最后在两个指针相遇的地方把基准的值赋到这两个指针所指向的位置
思路3（前后指针法）
故名思意，我们要设置前后两个指针，一个指向头元素prev，一个指向头元素后面一位元素cur
然后cur先找到一个比头元素大的值，然后让prev记录下来
然后cur自己再去寻找一个比头元素小的值
当两个指针各自所找到的元素就进行交换，不断重复上面的操作
最后将prev所指向的下标和头元素进行交换，并且将prev所指向的下标作为基准
代码3
public static int quickSortFrontAndLast(int[] arr,int left,int right){int cur = left+1;int prev = left;while (cur <= right){if (arr[cur] < arr[left] && arr[++prev] != arr[cur]){swap(arr, cur, prev);}cur++;}swap(arr, left, prev);return prev;}public static void swap(int[] arr,int a,int b){int tmp = arr[a];arr[a] = arr[b];arr[b] = tmp;}
cur值是要寻找比头元素小的值，而prev是要寻找比头元素大的值
所以就有了这么一行代码
if(arr[cur] < arr[left] && arr[++prev] != arr[cur])
这段代码的涵义是如果cur先找到了一个比基准值大的元素那么就会让prev先记录下来
然后cur再不断往后走直到找到一个比基准值小的，最后两个指针所指向的下标交换元素
快速排序的优化
优化1：三数取中法
当我们数据有序的时候，这个时候使用快速排序的时间复杂度是非常高的！
这个时候就像是链表了，需要从尾巴遍历一遍再从头部遍历一遍，时间复杂度为O（n） = n^2
如果在这个时候使用三数取中法，取头尾中间三个元素的中间值和头元素进行交换
那么我们再次使用快速排序的时候
从左边的第一个元素作为基准值，我们左右指针就不用将整个数组遍历完了，而是只需要遍历到交换后得头元素值位置即可
那么这个时候我们得时间复杂度也就降低了
public static int findMidOfNumber(int[] arr,int left,int right){int mid = (left + right) / 2;if (arr[left] < arr[right]){if (arr[left] > arr[mid]){return left;}else if (arr[left] < arr[mid]){return mid;}else return right;}else {if (arr[right] > arr[mid]) {return right;} else if (arr[mid] > arr[right]) {return mid;} else return left;}}
优化2：直接插入排序
我们发现快速排序其实和二叉树的前序遍历十分相似
那么到后面随着结点越来越多，树的高度越来越高，数据这个时候也是趋于有序的
那么我们再使用递归的方式来进行排序就提高了我们的时间复杂度了
所以这个是我们可以设条件来进行直接插入排序
因为数据量相对较少且数据趋于有序，这个时候使用直接插入排序是十分快的
if (end - start <= 15){insertSort(arr,start,end);}
思路4（非递归法）
利用非递归来实现我们的快速排序主要是将递归的过程给非递归化，最主要的找基准方法是不变的
所以我们要用栈和while循环来模拟递归的过程
我们可以创建一个栈用来记录起点和终点的位置
记录下头元素，基准前一个元素，基准后一个元素，尾元素，四个数据
然后存入我们的栈里面，然后使用while循环来模拟我们的递归
当我们要开始基准左边的排序时，弹出栈顶两个元素然后进行找基准
然后再次记录好四个元素，当我们的栈为空时，这个时候也就排序完毕了
代码4
public static void quickSortNor(int[] arr){Stack<Integer> stack = new Stack<>();int start = 0;int end = arr.length -1;int pivot = quickSortHoare(arr,start,end);if (start + 1 < pivot){stack.push(start);stack.push(pivot-1);}if (pivot < end -1){stack.push(end);stack.push(pivot+1);}while (!stack.isEmpty()){end = stack.pop();start = stack.pop();pivot = quickSortHoare(arr,start,end);if (start + 1 < pivot){stack.push(start);stack.push(pivot-1);}if (pivot < end -1){stack.push(end);stack.push(pivot+1);}}}
为什么代码要写成
start + 1 < pivot 以及 pivot < end -1
这样来进行判断呢？
原因就在于当我们的基准左边或者右边的元素 小于等于一个的时候我们就不再需要进行排序了
根据快速排序的定义
当只有一个元素的时候左边的元素左边的元素都是小于基准的，右边的元素都是大于基准的
所以只有大于等于两个元素的时候我们才需要进行pai'xu
7.归并排序
思路1（递归法）
归并排序的思想也是利用分而治之的思想进行排序的
归并排序是将数组不断地进行对半拆分，拆分到只有一个元素
然后相邻的两组数据再进行排序，再不断进行排序，将两个有序表合并成一个有序表
我们将这个思路称为二路归并
代码1
public class MergeSort {public static void mergeSort(int[] arr){mergeSortChild(arr,0, arr.length-1);}public static void mergeSortChild(int[] arr ,int left,int right){if (left >= right){return;}int mid = (left+right) / 2;mergeSortChild(arr,mid,right);mergeSortChild(arr,left,mid-1);merge(arr,left,mid,right);}public static void merge(int[] arr,int left,int mid,int right){int start1 = left;int end1 = mid-1;int start2 = mid;int end2 = right;int[] array = new int[right-left+1];int k = 0;while (start1 <= end1 && start2 <= end2){if (arr[start1] < arr[start2]){array[k] = arr[start1];start1++;k++;}else {array[k] = arr[start2];start2++;k++;}}while (start1 <= end1){array[k] = start1;start1++;k++;}while (start2 <= end2){array[k] = start2;start2++;k++;}for (int i = 0; i < k; i++) {arr[i+left] = array[i];}}}
我们设置四个变量，分别记录头元素，中间元素的前一个元素，中间元素，以及尾元素
通过这种方式来进行两个数组的合并
之后合并的思想和链表中的两个链表进行有序排序的思路是一样的
这里就不过多赘述了
由于我们是创建了一个新的数组，所以我们要把这个排序好的数组赋值给原来的数组
for (int i = 0; i < k; i++) {arr[i+left] = array[i];}
为什么这里的要写成这样？
arr[ i + left ] = array [ i ]
因为如果直接把i写成0的话，那么我们把第一路归并完成了以后
那么再次进行第二路进行归并时会把第一路的数据给覆盖掉（因为此时的 i 又是0）
那么为了避免这个现象的出现我们要写成i + left这样就可以避免这种情况的发生
思路2（非递归法）
利用非递归来实现我们的快速排序主要是将递归的过程给非递归化，最主要的找归并方法是不变的
我们从思路一可以知道递归法是“从上到下”的，是“从多到一”的过程
那么我们非递归就是“从下到上”，是“从一到多”的过程
通过gap值得不断遍历我们就可以完成图中每一层的归并
那么是怎么从两个排序到四个排序再到二路归并的？
我们将 gap*=2 就可以完成这种操作了
代码2
public static void mergeSortChild(int[] arr){int gap = 1;while(gap < arr.length){for (int i = 0; i < arr.length; i += gap) {int start = i;int mid = start + gap - 1;int end = mid + gap;if (mid >= arr.length){mid = arr.length-1;}if (end >= arr.length-1){end = arr.length-1;}merge(arr,start,mid,end);}gap *= 2;}
这里写成这样我们就可以数组越界的情况发生
因为当我们的元素只有一个的时候
我们的归并很有可能会发生数组越界的情况所以为了避免这种情况的发生
我们直接将越界的数据变成数组中的最后一个元素
if (mid >= arr.length){mid = arr.length-1;}if (end >= arr.length-1){end = arr.length-1;}
