6.希尔排序#
希尔排序其实可以理解成一种带步长的排序方式, 上面刚说了插入排序的实现方式,上面说我们默认从数组的第二个位置开始算,实际上就是说步长是1,下标的移动每次都是1
对于希尔排序来说,它默认的步长是 arr.length/2 , 每次步长都减少一半, 最终的步长也会是1
代码实现:
/** * 希尔排序,在插入排序的基础上,添加了步长 , * // todo 只要在本步长范围内，这些数字为组成一个组进行 插入排序 * 初始 步长=length/2 * 后来: 步长= 步长/2 * 直到最后: 步长=1; 正宗的插入排序 * @param ints */ private static void shellSort(int[] ints) { // 记录当前的步长 int step=ints.length/2; // 步长==》控制遍历几轮, 并且每次步长都是上一次的一半大小 for (int i=step;i>0;i/=2){ // 遍历当前步长下面的全部组,这里的j1, 就相当于插入排序中第一次开始的位置1前面的0下标 for (int j1=i;j1<ints.length;j1++){ // 遍历本组中全部元素 == > 从第二个位置开始遍历 // x 就相当于插入排序中第一次开始的位置1 for(int x=j1+i;x<=ints.length-1;x+=i){ // 从当前组的第二个元素开始,一旦发现它前面的元素比他小, // 插入排序, 1. 把当前的元素存起来 2. 循环它前面的元素往前移 3. 把当前元素插入到合适的位置 if(ints[x]<ints[x-i]){ int temp=ints[x]; int j ; for(j=x-i;j>=0&&ints[j]>temp;j=j-i) { ints[j+i]=ints[j]; } ints[j+i]=temp; } } } } }
空间复杂度: 和插入排序一样都是O(1)
稳定性: 希尔排序由于步长的原因,而不向插入排序,一经开始标准位置前的数组即刻有序, 所以希尔排序是不稳定的
希尔排序的性能无法准确量化，跟输入的数据有很大关系在实际应用中也不会用它，因为十分不稳定，虽然比传统的插入排序快，但比快速排序等慢
其时间复杂度介于O(nlogn) 到 O(n^2) 之间
7.堆排序#
堆排序是借助了堆这种数据结构完成的排序方式,堆有大顶堆和小顶堆, 将数组转换成大顶堆然后进行排序的会结果是数组将从小到大排序,小顶堆则相反
什么是堆呢? 堆其实是可以看成一颗完全二叉树的数组对象, 那什么是完全二叉树呢? 比如说, 这颗数的深度是h,那么除了h层外, 其他的1~h-1层的节点都达到了最大的数量
算法的实现思路: 通过递归,将数组看成一个堆,从最后一个非叶子节点开始,将这个节点转换成大顶堆, 什么是大顶堆呢? 就是根节点总是大于它的两个子节点, 重复这个过程一直递归到堆的根节点(此时根节点是最大值),此时整个堆为大顶堆, 然后交换根节点和最后一个叶子节点的位置,将最大值保存起来
例: 假设待排序序列是a[] = {7, 1, 6, 5, 3, 2, 4}，并且按大顶堆方式完成排序
- 第一步（构造初始堆）：
- 第二步（首尾交换，断尾重构）：
代码实现:
public static void sort(int[] ints) { // 开始位置是最后一个非叶子节点 int start = ints.length / 2-1; // 调整成大顶堆 for (int i = start; i >= 0; i--) { maxHeap(ints, ints.length, i); } // 调整第一个和最后一个数字, 在把剩下的转换为大定堆, j--实现了,不再调整本轮选出的最大的数 for (int j = ints.length - 1; j > 0; j--) { int temp = ints[0]; ints[0] = ints[j]; ints[j] = temp; maxHeap(ints, j, 0); } } /** * 转换为大顶堆, 其实就是比较根节点和两个子节点的大小,调换他们的顺序使得根节点的值大于它的两个子节点 * * @param arr * @param size * @param index 从哪个节点开始调整 (一开始转换为大顶堆时,使用的是最后一个非夜之节点, 但是转换完成之后,使用的就是0,从根节点开始调整) */ public static void maxHeap(int[] arr, int size, int index) { // 当前节点的左子节点 int leftNode = 2 * index + 1; // 当前节点的右子节点 int rightNode = 2 * index + 2; // 找出 当前节点和左右两个节点谁最大 int max = index; if (leftNode < size && arr[leftNode] > arr[max]) { max = leftNode; } if (rightNode < size && arr[rightNode] > arr[max]) { max = rightNode; } // 交换位置 if (max != index) { int temp = arr[index]; arr[index] = arr[max]; arr[max] = temp; // 交换位置后,可能破坏之前的平衡(跟节点比左右的节点小),递归 // 有可能会破坏以max为定点的子树的平衡 maxHeap(arr, size, max); } }
推荐的使用场景: n越大越好
时间复杂度: 堆排序的效率与快排、归并相同，都达到了基于比较的排序算法效率的峰值（时间复杂度为O(nlogn)）
空间复杂度: O(1)
稳定性: 不稳定
8.基数排序#
算法思路:
看上图中的绿色部分, 假设我们有下标从0-9,一共10个桶
第一排是给我们排序的一组数
我们分别对取出第一排数的个位数,放入到对应下标中的桶中,再依次取出,就得到了第三行的结果, 再取出三行的十位数,放入到桶中,再取出,就得到最后一行的结果
// 基数排序 // 创建10个数组,索引从0-9 // 第一次按照个位排序 // 第二次按照十位排序 // 第三次按照百位排序 // 排序的次数，就是数组中最大的数的位数 public static void radixSort(int[] arr){ int max = Integer.MIN_VALUE; // 循环找到最大的数，控制比较的次数 for (int i : arr) { if (i>max){ max=i; } } System.out.println(" 最大值: "+max); // 求最大数字的位数,获取需要比较的轮数 int maxLength = (max+"").length(); System.out.println(" 最大串的长度: "+maxLength); // 创建应用创建临时数据的数组, 整个大数组中存放着10个小数组, 这10个小数组中真正存放的着元素 int [][] temp = new int[10][arr.length]; // 10个 长度为arr.length长度的数组 // todo 用于记录在temp中相应的数组中存放的数字的数量 int [] counts = new int[10]; // 还需要添加另一个变量n 因为我们每轮的排序是从的1 - 10 - 100 - ... 开始求莫排序 for(int i=0,n=1;i<maxLength;i++,n*=10){ // 计算每一个数字的余数,遍历数组,将符合要求的放到指定的数组中 for (int j=0;j<arr.length;j++){ int x = arr[j]/n%10; // 把当前遍历到的数据放入到指定位置的二维数组中 temp[x][counts[x]] = arr[j]; // 更新二维数组中新更改的数组后的 新长度 counts[x]++; } int index =0; // 把存放进去的数据重新取出来 for (int y=0;y<counts.length;y++){ // 记录数量的那个数组的长度不为零,我们才区取数据 if (counts[y]!=0){ // 循环取出元素 for (int z =0;z<counts[y];z++){ // 取出 arr[index++] = temp[y][z]; } // 把数量置为0 counts[y]=0; } } } }
稳定性: 稳定
时间复杂度: 平均、最好、最坏都为O(k*n),其中k为常数,n为元素个数
空间复杂度: O(n+k)
9.桶排序#
算法思路: 相对比较好想, 给我们一组数,我们在选出这组数中最大值和数组的length的长度,选最大的值当成新数组的长度,然后遍历旧的数组,将旧数组中的值放入到新数组中index=旧数组中的值的位置
然后一次遍历旧数组中的值,就能得到最终的结果
代码实现:
private static void sort(int[] ints) { int max = Integer.MIN_VALUE; for (int anInt : ints) { if (anInt>max) max=anInt; } int maxLength = ints.length-max >0 ? ints.length:max; int[] result = new int[maxLength]; for (int i=0;i<ints.length;i++){ result[ints[i]] +=1 ; } for(int i=0 ,index = 0;i<result.length;i++){ if (result[i]!=0){ for (int j=result[i];j>0;j--){ ints[index++] = i; } } } }
时间复杂度:
- 平均时间复杂度：O(n + k)
- 最佳时间复杂度：O(n + k)
- 最差时间复杂度：O(n^2)
空间复杂度：O(n * k)
稳定性：稳定
典型的用空间换时间的算法
10.计数排序#
算法思路: 根据待排序集合中最大元素和最小元素的差值范围，申请额外空间；
遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内；
对额外空间内数据进行计算，得出每一个元素的正确位置；
将待排序集合每一个元素移动到计算得出的正确位置上。
代码实现:
public static int[] sort(int[] A) { //一：求取最大值和最小值，计算中间数组的长度：中间数组是用来记录原始数据中每个值出现的频率 int max = A[0], min = A[0]; for (int i : A) { if (i > max) { max = i; } if (i < min) { min = i; } } //二：有了最大值和最小值能够确定中间数组的长度 //存储5-0+1 = 6 int[] pxA = new int[max - min + 1]; //三.循环遍历旧数组计数排序: 就是统计原始数组值出现的频率到中间数组B中 for (int i : A) { pxA[i - min] += 1;//数的位置 上+1 } //四.遍历输出 //创建最终数组，就是返回的数组，和原始数组长度相等，但是排序完成的 int[] result = new int[A.length]; int index = 0;//记录最终数组的下标 //先循环每一个元素 在计数排序器的下标中 for (int i = 0; i < pxA.length; i++) { //循环出现的次数 for (int j = 0; j < pxA[i]; j++) {//pxA[i]:这个数出现的频率 result[index++] = i + min;//原来原来减少了min现在加上min，值就变成了原来的值 } } return result; }
也是典型的用空间换时间的算法
时间复杂度: O(n+k)
空间复杂度: O(n+k)
稳定性: 稳定
