常见排序算法实现（一）+https://developer.aliyun.com/article/1413532
代码实现：
/** * 堆排 从小到大 * 1.创建大根堆 * 2.交换 向下调整 */ public static void heapSort(int[] arr) { creatBigHeap(arr); int end = arr.length-1; while(end > 0) { swap(arr,0,end); shiftDown(arr,0,end); end--; } } private static void creatBigHeap(int[] arr) { for (int parent = (arr.length-1-1)/2; parent >= 0; parent--) { shiftDown(arr,parent,arr.length); } } private static void shiftDown(int[] arr, int parent, int end) { int child = 2*parent+1; while (child < end) { // 判断左右孩子谁是最大的 if(child+1 < end && arr[child] < arr[child+1]) { child++; } if(arr[child] > arr[parent]) { swap(arr,child,parent); parent = child; child = 2*parent+1; }else { break; } } }
5.快速排序
核心思路：分而治之
概念：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序 本质上是一个递归的过程 有序时 会出现单叉树 此时时间复杂度最高 达到0(N^2)
代码实现
/** * 快速排序 *时间复杂度：O(N*logN); 每次分而治之需要遍历的数字都是N 最好情况是一颗完全二叉树 高度为logN 所以时间复杂度是N*logn * * 容易溢出 占用内存大 * 三种写法：hore法 挖坑法（推荐） 前后指针法 * 递归方法 最好的情况是一种完全二叉树 */ public static void quickSort(int[] arr) { quick(arr,0,arr.length-1); } private static void quick(int[] arr,int start,int end) { if(start >= end) return; if(end - start + 1 > 7) { insertSortRange(arr,start,end); return; } midOfThree(arr,start,end); // 获得按照规则交换后的基准值的下标 int pivot = parttion(arr,start,end); // 遍历左子树 分而治之 quick(arr,start,pivot-1); // 遍历右子树 分而治之 quick(arr,pivot+1,end); } public static void insertSortRange(int[] arr,int begin,int end) { for (int i = 1; i <= end; i++) { int tmp = arr[i]; int j = i-1; for (; j >= begin; j--) { // >tmp j向后挪动 if(arr[j] > tmp) { arr[j+1] = arr[j]; }else { // 要插入的元素已经是最大的了 不需要再去比较了 //arr[j+1] = tmp; break; } } // 跳出循环有两种情况 1.tmp是最小的需要插入到第一个元素 此时j=-1 结束条件是j不>=0了 2.else语句中的break； arr[j+1] = tmp; } } private static void midOfThree(int[] arr, int left, int right) { int mid = (left + right) / 2; if(arr[left] > arr[right]) swap(arr,left,right);// 保证左边元素是较小值 if(arr[mid] > arr[right]) swap(arr,mid,right);// 保证中间元素是较小值 if(arr[mid] > arr[left]) swap(arr,mid,left);// 此时保证left下标的值是中间大小 } private static int parttionHoare(int[] arr,int left,int right) { int i = left; // 每次都选取第一个元素为基准值 int key = arr[left]; // 遍历交换 // left 从左往右 找比Key大的 // right 从右往左 找比key小的 while (left < right) { /** * 为什么先走右边 * 先走right保证他们相遇时 一定是比key值小的数据 * 如果先走left 相遇时碰到的一定是比key大的 此时再交换 则key的左边存在比key大的数据了 */ // 先从右边找 while (left < right && arr[right] >= key) { // 等号必须要取 万一两个都是6 会陷入死循环 right--; } // 此时right下标的元素比key小 while (left < right && arr[left] <= key) { left++; } swap(arr,left,right); } // 使基准值位于中间（即左边都比key小 右边都比key大） swap(arr,i,left); return left; } /** * 快排的优化 * 1.三数取中法：解决特殊情况 --》第一个数字是最小的 或者是最大的 减少了树的高度 开辟的空间更小 * 2.小区间内采用插入排序 减少递归的次数（但时间有可能会增加） 降低了内存的要求 */
parttion的第二种写法：挖坑法
// 挖坑法 private static int parttion2(int[] arr,int left,int right) { // 每次都选取第一个元素为基准值 int key = arr[left]; // 遍历交换 // left 从左往右 找比Key大的 // right 从右往左 找比key小的 while (left < right) { // 先从右边找 while (left < right && arr[right] >= key) { // 等号必须要取 万一两个都是6 会陷入死循环 right--; } // 此时right下标的元素比key小 arr[left] = arr[right]; while (left < right && arr[left] <= key) { left++; } arr[right] = arr[left]; } // 使基准值位于中间（即左边都比key小 右边都比key大） arr[left] = key; return left; }
parttion的第三种写法：前后指针法
private static int parttion(int[] arr,int left,int right) { // 前后指针法 int prev = left; int cur = left+1; while (cur <= right) { // 后面那个条件：cur和prev之间必须至少间隔一个元素 // 如果没有间隔元素 交换后又把比left大的移到了左边 if(arr[cur] < arr[left] && arr[++prev] != arr[cur]) { swap(arr,cur,prev); } cur++; } // 遍历完整个数组了 swap(arr,left,prev); return prev; }
注意：
1.parttion一共有三种写法，推荐以挖坑法为先 前后指针或者Hoare法次之
2.为什么快速排序要先走right？因为这样能够保证left和right最后相遇的位置的元素是比key小的元素交换过后仍满足条件
快速排序的非递归写法
// 快排的非递归写法 public static void quickSortNor(int[] arr) { Stack<Integer> stack = new Stack<>(); int left = 0; int right = arr.length-1; int pivot = parttion(arr,left,right); // 如果等于 证明pivot左边只有一个数据 此时不需要再去排列了 下面的right同理 if(pivot-1 > left) { stack.push(left); stack.push(pivot-1); } if (pivot + 1 < right) { stack.push(pivot+1); stack.push(right); } while(!stack.isEmpty()) { right = stack.pop(); left = stack.pop(); pivot = parttion(arr,left,right); if(pivot-1 > left) { stack.push(left); stack.push(pivot-1); } if (pivot + 1 < right) { stack.push(pivot+1); stack.push(right); } } }
6.冒泡排序法（不做讲解）
/** * 冒泡排序 * 时间复杂度：O(N^2) 最好（加了优化）O(N) * 空间复杂度：O(1) * 稳定性好 */ public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length; 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) { return; } } }
7.归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使 子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
分解左边 分解右边 合并
代码实现
/** * 归并排序： * 时间复杂度：O(n*logN) * 空间复杂度：O(N); * 稳定 * * 分解左边 分解右边 归并(合并两个有序数组) * * 稳定的排序：冒泡 插入 归并 */ public static void mergeSort(int[] arr) { mergeSortFunc(arr,0,arr.length-1); } private static void mergeSortFunc(int[] arr, int left, int right) { if(left >= right) return; int mid = (left+right) / 2; mergeSortFunc(arr,left,mid); mergeSortFunc(arr,mid+1,right); merge(arr,left,mid,right); } private static void merge(int[] arr, int left, int mid, int right) { // 这里边的思路相当于是 合并两个有序序列 int[] tmpArr = new int[right-left+1]; int k = 0; // 分别定义两个需要合并的数组的首元素的下标 int s1 = left; int s2 = mid+1; // 遍历两个数组 while(s1 <= mid && s2 <= right) { if(arr[s1] < arr[s2]) { tmpArr[k++] = arr[s1++]; }else { tmpArr[k++] = arr[s2++]; } } // 出循环证明有一个数组不为空 while(s1 <= mid) { tmpArr[k++] = arr[s1++]; } while (s2 <= right) { tmpArr[k++] = arr[s2++]; } // 将排序好的元素返回给原数组 for (int i = 0; i < tmpArr.length; i++) { arr[i+left] = tmpArr[i]; } }
非递归写法
// 归并排序的非递归写法 public static void mergeSortNor(int[] arr) { int gap = 1; while(gap < arr.length) { for (int i = 0; i < arr.length; i+= 2*gap) { int left = i; int mid = i+gap-1; int right = mid+gap; if(mid >= arr.length) { mid = arr.length-1; } if(right >= arr.length) { right = arr.length-1; } merge(arr,left,mid,right); } gap *= 2; } }
8.计数排序
设置一个计数数组 用于记录待排序数组中相应元素出现的次数 并按照下标排列 最后返回给原数组
/** * 计数排序 * 时间复杂度：O(N+范围） * 空间复杂度：O(范围) * 适用于数据范围集中 数据量较小的情况 * 稳定性好 */ public static void countSort(int[] arr) { // 1.得到数组的最大值和最小值（数组的下标只能从0开始） int minVal = arr[0]; int maxVal = arr[0]; for (int i = 0; i < arr.length; i++) { if (arr[i] < minVal) { minVal = arr[i]; } if (arr[i] > maxVal) { maxVal = arr[i]; } } //2.遍历arr 并在计数数组中存放对应的次数 int[] count = new int[maxVal - minVal + 1]; for (int i = 0; i < arr.length; i++) { count[arr[i] - minVal]++; } //3.重新写入到原数组 int index = 0; for (int i = 0; i < count.length; i++) { while(count[i] > 0) { arr[index] = i + minVal; index++; count[i]--; } } }
总结：
1. 稳定的排序：插入排序 冒泡排序 归并排序
2.希尔排序的时间复杂度很复杂，到现在也没有一个具体的结论
3.初始序列顺序对排序的影响
选择排序无论你的顺序如何 都要遍历整个数组去寻找最小值/最大值 所以对于初始顺序不敏感
4.表格汇总
