目录
分类
直接插入排序
希尔排序
选择排序
堆排序
冒泡排序
快速排序
挖坑法
hoare法
双指针法
优化
非递归实现
归并排序
非递归实现
计数排序
分类
这里的排序可以分为两大类，
- 基于比较的排序
- 非基于比较的排序
其中有七种基于比较的排序：
- 直接插入排序
- 希尔排序
- 选择排序
- 堆排序
- 冒泡排序
- 快速排序
- 归并排序
一种非基于比较的排序：计数排序。
下面会通过Java来实现这八种排序，快速排序 和 归并排序 会有递归和非递归的实现。
直接插入排序
思路：
- 以两个for循环， 来实现两个数及两数中小数与前面数进行比较
- 假设第一个数为tmp，认为第一个数已经是排好序的，然后去和后面一个数进行比较
- 如果 j位置 的数 > j+1位置的数，把 j位置的数 赋值给 j+1位置；如果否，则向 j位置的前面去做，直到 j >= 0
- 重复进行步骤3，直到不符合循环条件
动图如下：
代码 ：
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{array[j+1] = tmp;break;}}array[j+1] = tmp;}
}时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
注意：
- 本身是一个稳定的排序，那么可以实现为不稳定的 。但是 如果一个排序 本身就是不稳定，那就不能实现稳定的排序。
- 数据越有序，直接插入排序越快
希尔排序
步骤：
希尔排序算是对直接排序进行优化，把其中的数据通过分组来不断简化 其中的有序性，上面有提到数据越有序，直接插入排序越快，不过这个分组并不是常规理解的那种把几个临近的数字化为一个组，而是，如下图所示：
通过间隔（gap）来实现分组，以上面 紫色的原图 为例，这时的gap为5，这代表着隔着5个空格的数为一组，然后进行组内排序，不断缩小间隔，增加每组内元素个数，再次进一步比较。
动图如下：
代码：
通过代码部分，我们也能看出这里面有直接排序的存在，只不过其中的部分和希尔排序有些出入。
public static void shellInsert(int[] array){int gap = array.length;while(gap > 1){gap /= 2;shell(array, gap);}
}private 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-= gap) {if(array[j] > tmp){array[j+gap] = array[j];}else{array[j+gap] = tmp;break;}}array[j+gap] = tmp;}
}时间复杂度：O(N^1.2) - O(N^1.3)
空间复杂度：O(1)
稳定性：不稳定
选择排序
第一种思路
步骤：
- 选择排序，从名字上我们可以理解为从中不断选择出最小值，然后把它交换、排到前面
- 之所以说是不断选出最小值，是因为每次选出最小值都是以 i位置为准，而i位置也会不断变化，两个for循环来实现
动图如下：
代码：
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;}}swap(array,i,minIndex);}
}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;
}因为其中有元素位置的交换，所以我们可以自己写一个元素位置交换的方法。
时间复杂度：O(N^2) 和数据 是否有序无关
空间复杂度：O(1)
稳定性：不稳定
第二种思路
步骤：
这里主要是通过双指针的方法来找到 最小值 和 最大值的位置，当然，这是相对于每次i位置的数的大小。整体过程和上面一种思路有些相似的部分，相对来说，掌握两种方法还是要好一点。
public static void selectSort1(int[] array){int left = 0;int right = array.length-1;while(left < right){int minIndex = left;int maxIndex = left;for (int i = left+1; i <= right; i++) {if(array[i] < array[minIndex]){minIndex = i;}if(array[i] > array[maxIndex]){maxIndex = i;}}swap(array, left, minIndex);//确保最大值的位置，最大值正好是 left 下标//此时把最大值换到了minIndex下标if(maxIndex == 0){maxIndex = minIndex;}swap(array, right, maxIndex);left++;right--;}
}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;
}堆排序
步骤：
- 通过向下调整，创建一棵大根堆的树
- 通过把根节点和最后一个分支节点进行交换
- 再进行向下调整，完成排序
这个思路主要是通过大根堆的由大到小的原理，再通过换位来实现排序。
代码：
public static void heapSort(int[] array){createHeap(array);int end = array.length-1;while(end > 0){swap(array, 0 ,end);siftDown(array, 0,end);end--;}
}//创建大根堆
public static void createHeap(int[] array){//length-1为最后一棵子树，-1 / 2 是为了找到最后一棵子树的根节点for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {siftDown(array,parent,array.length);//向下调整，创建大根堆}
}/**** @param array* @param parent 每棵子树调整的根节点* @param length 每棵子树调整的结束节点，跳到最后*/
public static void siftDown(int[] array, int parent, int length) {int child = 2*parent+1;while(child < length){if(child + 1 < length && array[child] < array[child +1]){child++;}if(array[child] > array[parent]){swap(array, child, parent);parent = child;child = 2*parent+1;}else{break;}}
}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;
}时间复杂度：O(N*logN)
空间复杂度：O(1)稳定性：不稳定
冒泡排序
步骤：
通过相邻的两个元素相互比较，若 前位置 比 后位置的数要大，进行交换
动图如下：
下面代码部分是优化后的部分，未优化则不包含(flg元素 和 -i操作 )
代码：
public static void bubbleSort(int[] array){for (int i = 0; i < array.length-1; i++) {boolean flg = false;for (int j = 0; j < array.length-1-i; j++) {if(array[j] > array[j+1]){swap(array, j, j+1);flg = true;}}//优化后的情况//n个数据，比较n-1次，有可能其中i次就有序了if(!flg){break;}}
}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;
}
时间复杂度：不优化的情况（没有下方的boolean元素和-i操作） O(n^2)
优化以后，最快情况能达到O(N)
空间复杂度：O(1)
稳定性：稳定
快速排序
快速排序有三种方式能来实现
- 挖坑法
- hoare法
- 双指针法
如果问题问到快速排序，优先使用挖坑法，其次hoare法、双指针法
挖坑法
步骤：
- 先是实现 保证一个数的左边都比它小，右边都比它大，具体步骤如下步骤2，3，4
- 把第一个数存起来，为tmp，第一个位置当作是坑
- 从后面找比tmp小的值，放到坑里面，后面被放入坑的数的位置再当作坑
- 从前面找比tmp大的值，放到坑里面，前面被放入坑的数的位置当作坑
- 再向两边进行递归来处理
动图如下：
代码：
public static void quickSort(int[] array){quick(array,0,array.length-1);
}private static void quick(int[] array, int start, int end){// = 是为了应对没有右边的情况，递归结束条件if(start >= end){return;}//整个方法走完之后，为第一次交换位置int pivot = partition1(array, start, end);quick(array, start, pivot-1);quick(array, pivot+1, end);
}private static int partition1(int[] array, int left, int right) {int tmp = array[left];while(left < right){//循环找，不循环时则代表找到，找到比tmp小的数while(left < right && array[right] >= tmp){right--;}//挖坑法，然后填坑//先是把第一个位置当作空，从后面数，如果有数比它小，就放到第一位//然后是从前数，找最大值，找到后放到，刚刚的位置//最后再把第一个数放到right和left相交的位置//方法就是把两边的数分大小放到第一个数两边array[left] = array[right];//找到比tmp大的数while(left < right && array[left] <= tmp){left++;}array[right] = array[left];}array[left] = tmp;return left;
}hoare法
步骤：
- 先是实现 保证一个数的左边都比它小，右边都比它大，具体步骤如下步骤2，3，4
- 把第一个数存起来，为tmp
- tmp和后面的数进行比较，然后把小数放到tmp前面，大数放到tmp后面
- 递归实现对tmp两边进行排序
代码如下：
public static void quickSort(int[] array){quick(array,0,array.length-1);
}private static void quick(int[] array, int start, int end){// = 是为了应对没有右边的情况，递归结束条件if(start >= end){return;}//整个方法走完之后，为第一次交换位置int pivot = partition(array, start, end);quick(array, start, pivot-1);quick(array, pivot+1, end);
}private static int partition(int[] array, int left, int right) {int tmp = array[left];int tmpleft = left;while(left < right){//循环找，不循环时则代表找到//right是为了把右边的小数移到左边while(left < right && array[right] >= tmp){right--;}while(left < right && array[left] <= tmp){left++;}swap(array, left, right);}//因为left所找的是把左边的大数放到右边，所以找到最后的数会比left小，进行交换swap(array,left,tmpleft);return left;
}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;
}双指针法
步骤：
这个主要是靠 cur + left 双指针来实现排序的，通过前后条件判断来进行排序
代码如下：
public static void quickSort(int[] array){quick(array,0,array.length-1);
}private static void quick(int[] array, int start, int end){// = 是为了应对没有右边的情况，递归结束条件if(start >= end){return;}//整个方法走完之后，为第一次交换位置int pivot = partition3(array, start, end);quick(array, start, pivot-1);quick(array, pivot+1, end);
}public static int partition3(int[] array, int left, int right){int prev = left;int cur = left+1;while(cur <= right){if(array[left] > array[cur] && array[cur] != array[prev]){swap(array, cur, prev);}cur++;}swap(array,prev,left);return prev;
}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;
}关于快速排序
时间复杂度：当数据给定的是1 2 3 4 5 6……有序的情况是 O(n^2)
最好的情况是O(N*logN)均匀分为叉，满二叉树
空间复杂度：最坏情况，递归是要开辟内存的O(N),最好的情况，满二叉树O(logN)
稳定性：不稳定
优化
通过上面三种方法，我们能看到三种方法中都有递归方式，每次递归都需要开辟内存，那么我们可以采取怎样的方式来减少递归的次数？
通过下面两种方法可以实现我们的想法：
三数取中
直接插入法【针对一定范围】
关于三数取中的意思是：找到左、右、中三个数的中位数。
部分直接插入，也可以减少递归次数，因为数据有越有序，直接插入法越快。
代码部分如下：
public class Sort {public static void quickSort(int[] array){quick(array,0,array.length-1);}private static void quick(int[] array, int start, int end){// = 是为了应对没有右边的情况，递归结束条件if(start >= end){return;}if(end - start + 1 <= 7){insertSortRange(array, start, end);return;}int minIndex = getMiddleNum(array, start, end);swap(array, start, minIndex);//整个方法走完之后，为第一次交换位置int pivot = partition1(array, start, end);quick(array, start, pivot-1);quick(array, pivot+1, end);}public static void insertSortRange(int[] array, int start, int end){for (int i = start+1; i <= end; i++) {int tmp = array[i];int j = i-1;for (; j >= start; j--) {if(array[j] > tmp){array[j+1] = array[j];}else{array[j+1] = tmp;break;}}array[j+1] = tmp;}}private static int getMiddleNum(int[] array, int left, int right){int mid = (left+right)/2;if(array[left] < array[right]){if(array[mid] < array[left]){return left;}else if(array[mid] > array[right]){return right;}else{return mid;}}else{if(array[mid] > array[left]){return left;}else if(array[mid] < array[right]){return right;}else{return mid;}}}private static int partition1(int[] array, int left, int right) {int tmp = array[left];while(left < right){//循环找，不循环时则代表找到，找到比tmp小的数while(left < right && array[right] >= tmp){right--;}//挖坑法，然后填坑//先是把第一个位置当作空，从后面数，如果有数比它小，就放到第一位//然后是从前数，找最大值，找到后放到，刚刚的位置//最后再把第一个数放到right和left相交的位置//方法就是把两边的数分大小放到第一个数两边array[left] = array[right];//找到比tmp大的数while(left < right && array[left] <= tmp){left++;}array[right] = array[left];}array[left] = tmp;return left;}private static void swap(int[] array, int left, int right){int tmp = array[left];array[left] = array[right];array[right] = tmp;}
}非递归实现
非递归实现，主要是栈的使用，通过控制出栈和入栈的元素及其顺序来实现
代码如下：
public static void quickSort(int[] array){quickNor(array,0,array.length-1);
}private static void quickNor(int[] array, int start, int end){Deque<Integer> stack = new ArrayDeque<>();int pivot = partition1(array, start, end);//pivot左边有两个元素if(pivot > start+1){stack.push(start);stack.push(pivot-1);}if(pivot < end-1){stack.push(pivot+1);stack.push(end);}while(!stack.isEmpty()){end = stack.pop();start = stack.pop();pivot = partition1(array, start, end);if(pivot > start+1){stack.push(start);stack.push(pivot-1);}if(pivot < end-1){stack.push(pivot+1);stack.push(end);}}
}private static int partition1(int[] array, int left, int right) {int tmp = array[left];while(left < right){//循环找，不循环时则代表找到，找到比tmp小的数while(left < right && array[right] >= tmp){right--;}//挖坑法，然后填坑//先是把第一个位置当作空，从后面数，如果有数比它小，就放到第一位//然后是从前数，找最大值，找到后放到，刚刚的位置//最后再把第一个数放到right和left相交的位置//方法就是把两边的数分大小放到第一个数两边array[left] = array[right];//找到比tmp大的数while(left < right && array[left] <= tmp){left++;}array[right] = array[left];}array[left] = tmp;return left;
}private static void swap(int[] array, int left, int right){int tmp = array[left];array[left] = array[right];array[right] = tmp;
}归并排序
步骤：
- 先把要排序的元素分为两个组，接着继续向下分组(有种递归的味道了)
- 把每组元素比较完后，再把两个有序数组组合起来
代码如下：
public static void mergeSort(int[] array){mergeSortTmp(array, 0, array.length-1);
}//递归实现归并排序
private static void mergeSortTmp(int[] array, int left, int right) {if(left >= right){return;}//找中间值int mid = (left + right)/2;mergeSortTmp(array, left, mid-1);mergeSortTmp(array, mid+1, right);//走到这里，相当于全部分解完//合并，合并有序数组merge(array, left, mid, right);}private static void merge(int[] array, int left, int mid, int right) {int[] tmp = new int[right-left+1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;while(s1 <= e1 && s2 <= e2){if(array[s1] <= array[s2]){tmp[k++] = array[s1++];}else {tmp[k++] = array[s2++];}}while(s1 <= e1){tmp[k++] = array[s1++];}while(s2 <= e2){tmp[k++] = array[s2++];}//可以保证tmp数组是有序的for (int i = 0; i < k; i++) {array[i+left] = tmp[i];}
}时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定
非递归实现
非递归的实现，主要依靠的间隔gap的不断变大，然后通过每一小部分的排序进而来实现整个数据组的排序
代码如下：
public static void mergeSortNor(int[] array){int gap =1;while(gap < array.length){for (int i = 0; i < array.length; i = i + gap*2) {int left = i;int mid = (left + gap -1);if(mid >= array.length){mid = array.length-1;}int right = mid + gap;if(right >= array.length){right = array.length-1;}merge(array, left, mid, right);}gap *= 2;}
}private static void merge(int[] array, int left, int mid, int right) {int[] tmp = new int[right-left+1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;while(s1 <= e1 && s2 <= e2){if(array[s1] <= array[s2]){tmp[k++] = array[s1++];}else {tmp[k++] = array[s2++];}}while(s1 <= e1){tmp[k++] = array[s1++];}while(s2 <= e2){tmp[k++] = array[s2++];}//可以保证tmp数组是有序的for (int i = 0; i < k; i++) {array[i+left] = tmp[i];}
}计数排序
非基于比较的排序
还有桶排序， 基数排序，感兴趣可以了解一下
使用场景：集中在某个范围内的一组数据
步骤：
- 根据数据的个数来创建数组
- 把对应元素出现的个数给到对应的位置，记录出现的次数
- 根据记录的次数，依次输出元素
代码如下 ：
public static void countSort(int[] array){//1.找最大值 和 最小值 来确定 计数数组的大小int maxVal = array[0];int minVal = array[0];for (int i = 1; i < array.length; i++) {if(array[i] > maxVal){maxVal = array[i];}if(array[i] < minVal){minVal = array[i];}}int len = maxVal - minVal + 1;int[] count = new int[len];//2.遍历原来的数组array， 把每个元素 放到对应的计数数组中 进行比较for (int i = 0; i < array.length; i++) {int index = array[i];count[index-minVal]++;}//3.依次 遍历计数数组int index = 0;for (int i = 0; i < count.length; i++) {while(count[i] != 0){array[index] = i+minVal;index++;count[i]--;}}
}
