【数据结构与算法】排序算法总结：冒泡 / 快排 / 直接插入 / 希尔 / 简单选择 / 堆排序 / 归并排序

1 排序

1.1 冒泡

内排序的交换排序类别

1.1.1 普通实现

public class BubbleSort {/*** 基本的 冒泡排序*/public static void bubbleSort(int[] srcArray) {int i,j; // 用于存放数组下标int temp = 0; // 用于交换数值时临时存放值for(i=0;i<srcArray.length-1;i++){// j 从后往前循环for(j=srcArray.length-2;j>=i;j--){// 若前者＞后者，则交换位置if(srcArray[j]>srcArray[j+1]){temp=srcArray[j];srcArray[j]=srcArray[j+1];srcArray[j+1]=temp;}}}// 输出排序后的序列for(int a =0;a<srcArray.length;a++)System.out.println(srcArray[a]);}/*** 执行 冒泡排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{9, 1, 5, 8, 3, 7, 4, 2, 6};// 输出结果bubbleSort(src);}
}

1.1.2 代码优化

  • 从j比到i，从0-i已经全部有序，i之前的不用再比较
  • flag = true：代表存在数据交换，即序列仍需排序，需继续循环
public class BubbleSort {/*** 优化的 冒泡排序*/public static void bubbleSortOpti(int[] srcArray) {int i,j; // 用于存放数组下标int temp = 0; // 用于交换数值时临时存放值// 标记位// flag = true：代表存在数据交换，即序列仍需排序，需继续循环// flag = false：代表不存在数据交换，即序列不需排序，已经是有序序列了，可停止循环Boolean flag = true;// 若flag = false时退出循环for(i=0;i<srcArray.length-1 && flag;i++){flag = false; // 初始化为false// j 从后往前循环for(j=srcArray.length-2;j>=i;j--){// 若前者＞后者，则交换位置if(srcArray[j]>srcArray[j+1]){temp=srcArray[j];srcArray[j]=srcArray[j+1];srcArray[j+1]=temp;flag = true; // 若有数据交换，则说明序列仍未无序}}}// 输出排序后的序列for(int a =0;a<srcArray.length;a++)System.out.println(srcArray[a]);}/*** 执行 优化后的冒泡排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{2, 1, 3, 4, 5, 6, 7, 8, 9};// 输出结果bubbleSortOpti(src);}
}

1.1.3 性能分析

在这里插入图片描述

1.2 快排

冒泡的升级，内排序的交换排序类别

1. 步骤1：将待排序列 分割成独立的2个子序列

  • 在待排序 序列中选择1个基准数据元素（第1个 / 最后1个，称为：枢轴）
  • 通过比较 基准数据元素 与 序列其余元素 大小，将待排序列分成2部分：（右序列）1部分 > 基准元素、（左序列）1部分 ＜ 基准元素

2. 步骤2：通过递归，分别对这2个子序列 进行快速排序
通过步骤2的方式，最终达到整个序列有序的目的

1.2.1 普通实现

  • 步骤1：通过分区函数Partition（）将序列分割成2个独立子序列（高、低）
  • 步骤2：对上述2个子序列使用快速排序方法进行递归
public class QuickSort {/*** 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static void quickSort(int[] srcArray, int low, int high) {if (low < high) {// 1. 将待排序列 根据所选的枢纽位置，分割成独立的2个子序列// 最终返回的是枢纽位置int privot = Partition(srcArray, low, high);// 2. 分别对这2个子序列 进行排序// a. 通过递归 对低字表进行排序quickSort(srcArray, low, privot - 1);// b. 通过递归 对高字表进行排序quickSort(srcArray, privot + 1, high);}}/*** 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static int Partition(int[] srcArray, int low, int high) {// 1. 将子表的第1个个记录作为枢纽int tmp = srcArray[low];while (low < high) {// 2. 比较高位元素 & 枢纽元素while (low < high && srcArray[high] >= tmp) {high--;}int temp = srcArray[low];srcArray[low] = srcArray[high];srcArray[high] = temp;// 3. 比较低位元素 & 枢纽元素while (low < high && srcArray[low] <= tmp) {low++;}int temp1 = srcArray[high];srcArray[high] = srcArray[low];srcArray[low] = temp1;}// 4. 最终低位、高位都会指向枢纽位置，返回return low;}/*** 执行 快速排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{ 50, 10, 90, 30, 70, 40, 80, 60, 20 };// 输出结果quickSort(src,0,src.length-1);// 输出 排序后的序列for (int a = 0; a < src.length; a++) {System.out.println(src[a]);}}
}

1.2.2 优化枢轴的选择

有随机数法、三数取中法、九数取中法，此处用三数取中法：

主要修改处：在分区函数Partition（）中将枢纽的选择方式改为三数取中，具体原理是：

  1. 找出中间元素
  2. 比较左、右端数据元素，保证左端较小（若左>右，就交换位置）
  3. 比较中、右端数据元素，保证中端较小（若中>右，就交换位置）
  4. 比较中、左端数据元素，保证中端较小（若中>左，就交换位置）
public class QuickSort {/*** 快速排序算法实现（基础实现）* 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static void quickSort(int[] srcArray, int low, int high) {if (low < high) {// 1. 将待排序列 根据所选的枢纽位置，分割成独立的2个子序列// 最终返回的是枢纽位置（主要优化在取取枢纽值里）int privot = Partition(srcArray, low, high);// 2. 分别对这2个子序列 进行排序// a. 通过递归 对低字表进行排序quickSort(srcArray, low, privot - 1);// b. 通过递归 对高字表进行排序quickSort(srcArray, privot + 1, high);}}/*** 作用：将待排序列 根据所选的枢纽位置，分割成独立的2个子序列（优化 = 选取枢轴 = 三数取中）* 返回值：所选的枢纽位置* 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static int Partition(int[] srcArray, int low, int high) {/*** 三数取中的方式*/// 1. 找出中间元素// 不是使用(low+high)/2的原因：容易溢出// 右移1位 = 除以2，但右移的运算速度更快int m = low + ( (high-low)>>1 );// 2. 比较左、右端数据元素，保证左端较小// 若左>右，就交换位置if(srcArray[low]>srcArray[high]) {int temp = srcArray[low];srcArray[low] = srcArray[high];srcArray[high] = temp;}// 3. 比较中、右端数据元素，保证中端较小// 若中>右，就交换位置if(srcArray[m]>srcArray[high]) {int temp1 = srcArray[m];srcArray[m] = srcArray[high];srcArray[high] = temp1;}// 4. 比较中、左端数据元素，保证中端较小if(srcArray[m]>srcArray[low]) {// 若中>左，就交换位置int temp2 = srcArray[m];srcArray[m] = srcArray[low];srcArray[low] = temp2;}// 此时，最低位 = srcArray[low] = 三数的中间数（即 最低位、最高位 & 中间数的中间值）// 将上述值作为枢纽int tmp = srcArray[low];System.out.println("枢轴位置 =" + srcArray[low]);/*** 下面代码类似未优化前（即，基础实现）*/while (low < high) {// 比较高位元素 & 枢纽元素while (low < high && srcArray[high] >= tmp) {high--;}int temp = srcArray[low];srcArray[low] = srcArray[high];srcArray[high] = temp;// 比较低位元素 & 枢纽元素while (low < high && srcArray[low] <= tmp) {low++;}int temp1 = srcArray[high];srcArray[high] = srcArray[low];srcArray[low] = temp1;}// 最终低位、高位都会指向枢纽位置，返回return low;}/*** 执行 快速排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{ 50, 10, 90, 30, 70, 40, 80, 60, 20 };// 输出结果quickSort(src,0,src.length-1);// 输出 排序后的序列for (int a = 0; a < src.length; a++) {System.out.println(src[a]);}}
}

1.2.3 减少不必要的交换

主要修改点在分区函数Partition（）中

   /*** 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static int Partition(int[] srcArray, int low, int high) {// 1. 将子表的第1个个记录作为枢纽int tmp = srcArray[low];while (low < high) {// 2. 比较高位元素 & 枢纽元素while (low < high && srcArray[high] >= tmp) {high--;}// 采用 替换操作 换掉之前的 交换操作srcArray[low] = srcArray[high];// 之前的交换操作// int temp = srcArray[low];// srcArray[low] = srcArray[high];// srcArray[high] = temp;// 3. 比较低位元素 & 枢纽元素while (low < high && srcArray[low] <= tmp) {low++;}// 采用 替换操作 换掉之前的 交换操作srcArray[high] = srcArray[low];// 之前的交换操作// int temp1 = srcArray[high];// srcArray[high] = srcArray[low];// srcArray[low] = temp1;}// 将枢轴元素替换到当前低位指针指向的元素 & 返回srcArray[low] = tmp;return low;}

1.2.4 优化数据量较小序列的排序方案

  • 对于数据量较大的序列：采用快速排序

资料显示，当序列的数据量>7时，视为大数据量序列

  • 对于数据量较小的序列：采用 直接插入排序
    a. 直接插入排序是简单排序算法中性能最好的
    b. 优化主要在quickSort（）中
public class QuickSort {/*** 快速排序算法实现（优化 = 优化数据量较小序列的排序方案）* 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static void quickSort(int[] srcArray, int low, int high) {// 当序列的数据量>7时，视为大数据量序列，此时采用 快速排序if (high-low > 7) {if (low < high) {System.out.println("采用快排");int privot = Partition(srcArray, low, high);quickSort(srcArray, low, privot - 1);quickSort(srcArray, privot + 1, high);}}else{// 当序列的数据量<7时，视为小数据量序列，此时采用 直接插入排序insertSort(srcArray);System.out.println("采用直接插入排序");};}/*** 作用：将待排序列 根据所选的枢纽位置，分割成独立的2个子序列（优化 = 优化数据量较小序列的排序方案）* 返回值：所选的枢纽位置* 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static int Partition(int[] srcArray, int low, int high) {// 1. 将子表的第1个个记录作为枢纽int tmp = srcArray[low];while (low < high) {// 2. 比较高位元素 & 枢纽元素// 若高位元素 > 枢纽元素，则继续比较前1个高位元素// 若高位元素 < 枢纽元素，则交换当前高位元素 与 低位元素 位置、开始比较低位元素 与 枢纽元素while (low < high && srcArray[high] >= tmp) {high--;}int temp = srcArray[low];srcArray[low] = srcArray[high];srcArray[high] = temp;// 3. 比较低位元素 & 枢纽元素// 若低位元素 < 基准元素，则继续比较下1个低位元素// 若低位元素 > 枢纽元素，就交换当前低位元素 与 高位元素 位置；重新开始比较高位元素 与 枢纽元素while (low < high && srcArray[low] <= tmp) {low++;}int temp1 = srcArray[high];srcArray[high] = srcArray[low];srcArray[low] = temp1;}// 最终低位、高位都会指向枢纽位置，返回return low;}/*** 直接插入排序 算法实现*/public static void insertSort(int[] srcArray) {int i; // 用于存放当前插入数据记录的数组下标int j; // 用于存放需要比较记录的下标int temp; // 用于交换数据// 从第1个数据记录 开始，该元素可以认为已经被排序for(i = 0 ; i < srcArray.length ; i++){temp = srcArray[i];// 取出下一个数据记录，在已经排序的序列中从后向前扫描// 将 当前数据记录 与 前面排序好的值进行比较for(j = i ; j > 0 && temp < srcArray[j-1] ; j --){// 按照顺序小 -> 大 将 当前需要插入的数据记录插入到合适位置 = 后移已排序好的元素 + 插入新的数据记录// a. 后移已排序好的元素srcArray[j] = srcArray[j-1];}// 插入新的数据记录srcArray[j] = temp;}}/*** 执行 快速排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{ 50, 10, 90, 30, 70, 40, 80, 60, 20 };// 输出结果quickSort(src,0,src.length-1);// 输出 排序后的序列for (int a = 0; a < src.length; a++) {System.out.println(src[a]);}}
}

特别注意：此处的排序方式选择不只是第一次排序，而是贯穿 整个快速排序过程，即 由于快速排序过程 = 逐步划分成半子表的过程，所以最后几次的排序一定会使用 直接插入排序

1.2.5 优化递归操作

将快速排序算法最后的 尾部递归操作 改成 迭代操作

  • 可有效缩减所需的堆栈深度，从而有效提高性能
  • 主要在主要算法的quickSort（）中
public class QuickSort {/*** 快速排序算法实现（优化 = 优化递归 = 采用 迭代操作 代替 递归操作）* 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static void quickSort(int[] srcArray, int low, int high) {// 将if 改成 While，原来操作为：if (low < high)while (low < high) {int privot = Partition(srcArray, low, high);quickSort(srcArray, low, privot - 1);low = privot +1 ;// 将 尾递归中对高字表的排序 改成 low = privot +1，原来操作为：quickSort(srcArray, privot + 1, high);// 原因：在第1次循环后，后1次循环中的Partition(srcArray, low, high) = quickSort(srcArray, privot + 1, high)// 故可删去该递归}}/*** 作用：将待排序列 根据所选的枢纽位置，分割成独立的2个子序列（优化 = 优化递归 = 采用 迭代操作 代替 递归操作）* 返回值：所选的枢纽位置* 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static int Partition(int[] srcArray, int low, int high) {// 1. 将子表的第1个个记录作为枢纽int tmp = srcArray[low];while (low < high) {// 2. 比较高位元素 & 枢纽元素while (low < high && srcArray[high] >= tmp) {high--;}int temp = srcArray[low];srcArray[low] = srcArray[high];srcArray[high] = temp;// 3. 比较低位元素 & 枢纽元素while (low < high && srcArray[low] <= tmp) {low++;}int temp1 = srcArray[high];srcArray[high] = srcArray[low];srcArray[low] = temp1;}// 最终低位、高位都会指向枢纽位置，返回return low;}/*** 执行 快速排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{ 50, 10, 90, 30, 70, 40, 80, 60, 20 };// 输出结果quickSort(src,0,src.length-1);// 输出 排序后的序列for (int a = 0; a < src.length; a++) {System.out.println(src[a]);}}
}

1.2.6 终极优化

结合上述4种优化的终极优化版：

public class QuickSort {/*** 快速排序算法实现（优化 = 选取枢轴、减少不必要的交换次数、优化数据量较小序列的排序方案、将尾递归操作->迭代操作）* 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static void quickSort(int[] srcArray, int low, int high) {/*** 优化3：优化数据量较小序列的排序方案 = 步骤8、9*/if (high-low > 7) {// 8. 当序列的数据量>7时，视为大数据量序列，此时采用 快速排序System.out.println("采用快排");/*** 优化4：将尾递归操作->迭代操作 = 步骤10、11*/// 10. 将if 改成 While，原来操作为：if (low < high)while (low < high) {int privot = Partition(srcArray, low, high);quickSort(srcArray, low, privot - 1);// 11. // 将 尾递归中对高字表的排序 改成 low = privot +1，原来操作为：quickSort(srcArray, privot + 1, high);// quickSort_RecursionOp(srcArray, middle + 1, high);low = privot +1 ;}}else{// 9. 当序列的数据量<7时，视为小数据量序列，此时采用 直接插入排序insertSort(srcArray);System.out.println("采用直接插入排序");}}/*** 快速排序算法中寻找中间元素 实现（优化 = 选取枢轴、减少不必要的交换次数、优化数据量较小序列的排序方案、将尾递归操作->迭代操作）* 参数说明：* @param srcArray = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static int Partition(int[] srcArray, int low, int high) {/*** 优化1：三数取中选取枢轴 = 步骤1、2、3、4、5*/// 1. 找出中间元素int m = low + (high - low) /2;// 2. 比较左、右端数据元素，保证左端较小// 若左>右，就交换位置if(srcArray[low]>srcArray[high]) {int temp = srcArray[low];srcArray[low] = srcArray[high];srcArray[high] = temp;}// 3. 比较中、右端数据元素，保证中端较小// 若中>右，就交换位置if(srcArray[m]>srcArray[high]) {int temp1 = srcArray[m];srcArray[m] = srcArray[high];srcArray[high] = temp1;}// 4. 比较中、左端数据元素，保证中端较小if(srcArray[m]>srcArray[low]) {// 若中>左，就交换位置int temp2 = srcArray[m];srcArray[m] = srcArray[low];srcArray[low] = temp2;}// 此时，最低位 = srcArray[low] = 三数的中间数（即 最低位、最高位 & 中间数的中间值）// 将上述值作为枢纽int tmp = srcArray[low];System.out.println("枢轴位置 =" + srcArray[low]);/*** 优化2：减少不必要的交换次数 = 步骤5.6.7*/while (low < high) {while (low < high && srcArray[high] >= tmp) {high--;}// 5. 采用 替换操作 换掉之前的 交换操作srcArray[low] = srcArray[high];// 之前的交换操作// int temp = srcArray[low];// srcArray[low] = srcArray[high];// srcArray[high] = temp;while (low < high && srcArray[low] <= tmp) {low++;}// 6. 采用 替换操作 换掉之前的 交换操作srcArray[high] = srcArray[low];// 之前的交换操作// int temp1 = srcArray[high];// srcArray[high] = srcArray[low];// srcArray[low] = temp1;}// 7. 将枢轴元素替换到当前低位指针指向的元素 & 返回srcArray[low] = tmp;return low;}/*** 直接插入排序 算法实现*/public static void insertSort(int[] srcArray) {int i; // 用于存放当前插入数据记录的数组下标int j; // 用于存放需要比较记录的下标int temp; // 用于交换数据// 从第1个数据记录 开始，该元素可以认为已经被排序for(i = 0 ; i < srcArray.length ; i++){temp = srcArray[i];// 取出下一个数据记录，在已经排序的序列中从后向前扫描// 将 当前数据记录 与 前面排序好的值进行比较for(j = i ; j > 0 && temp < srcArray[j-1] ; j --){// 按照顺序小 -> 大 将 当前需要插入的数据记录插入到合适位置 = 后移已排序好的元素 + 插入新的数据记录// a. 后移已排序好的元素srcArray[j] = srcArray[j-1];}// 插入新的数据记录srcArray[j] = temp;}}/*** 执行 快速排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{ 50, 10, 90, 30, 70, 40, 80, 60, 20 };// 输出结果quickSort(src,0,src.length-1);// 输出 排序后的序列for (int a = 0; a < src.length; a++) {System.out.println(src[a]);}}
}

1.2.7 性能分析

在这里插入图片描述

1.3 直接插入排序

属于 内排序算法中 的 插入排序类别

  • 将 1个待排序的数据 按顺序大小 插入到 1个已排序的序列中
  • 重复上述步骤，直到全部插入 & 排序完为止

1.3.1 代码实现

public class InsertSort {/*** 简单选择排序*/public static void insertSort(int[] srcArray) {int i; // 用于存放当前插入数据记录的数组下标int j; // 用于存放需要比较记录的下标int temp; // 用于交换数据// 1. 从第1个数据记录 开始，该元素可以认为已经被排序for(i = 0 ; i < srcArray.length ; i++){temp = srcArray[i];// 2. 取出下一个数据记录，在已经排序的序列中从后向前扫描// 3. 将 当前数据记录 与 前面排序好的值进行比较for(j = i ; j > 0 && temp < srcArray[j-1] ; j --){// 4. 按照顺序小 -> 大 将 当前需要插入的数据记录插入到合适位置 = 后移已排序好的元素 + 插入新的数据记录// a. 后移已排序好的元素srcArray[j] = srcArray[j-1];}// b. 插入新的数据记录srcArray[j] = temp;}// 5. 输出排序后的序列for(int a =0;a<srcArray.length;a++)System.out.println(srcArray[a]);}/*** 执行 直接插入排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{0, 5, 3, 4, 6, 2};// 输出结果insertSort(src);}}

1.3.2 性能分析

在这里插入图片描述

1.4 希尔排序

  • 也叫 缩小增量 排序，属于 内排序算法中 的 插入排序类别
  • 是对 直接插入排序算法 的优化和升级

核心思想：跳跃分割

  • 将相隔某个增量的记录组成一个子序列
  • 实现跳跃式移动，使得排序效率提高
  • 不是随便分组后各自排序

1.4.1 代码实现

public class ShellSort {/*** 希尔排序*/public static void shellSort(int[] srcArray) {int j = 0;int temp = 0;// 增量序列值 计算公式 = 前1个增量序列值 / 2，直到增量序列值 = 1为止// 第1个值 = 初始值 = 序列长度 / 2for (int increment = srcArray.length / 2; increment > 0; increment /= 2) {// 根据增量值选取子序列for (int i = increment; i < srcArray.length; i++) {temp = srcArray[i];// 对子序列执行直接插入排序，即 循环两两比较子序列的值for (j = i - increment; j >= 0; j -= increment) {if (temp < srcArray[j]) {// 将小的元素放到前面、大的元素放到后面srcArray[j + increment] = srcArray[j];} else {break;}}srcArray[j + increment] = temp;}// 输出 根据增量值排序后的序列System.out.println("增量值为:" + increment + "，排序结果如下：");for (int a = 0; a < srcArray.length; a++) {System.out.println(srcArray[a]);}}}/*** 执行 希尔排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{ 4, 3, 6, 2, 7, 1, 5, 8 };// 输出结果shellSort(src);}
}

1.4.2 性能分析

在这里插入图片描述

1.5 简单选择排序

n = 表长，i = 当前位置

  1. 比较 第 i 个记录 & 剩余的 （n-i）个记录
  2. 在（n - i +1）个记录中，选择最小的记录
  3. 将最小的记录 与 第 i 个记录进行交换

重复上述过程，直到 i 到序列最后1个元素比较后 结束。

1.5.1 代码实现

public class ChooseSort {/*** 简单选择排序*/public static void chooseSort(int[] srcArray) {int i; // 用于存放当前数组下标int j; // 用于存放需要比较记录的下标for(i=0;i<srcArray.length;i++){// 将当前记录 与 后面记录进行比较for(j=i+1;j<srcArray.length;j++){// 若 当前记录 < 后面记录，则交换位置if(srcArray[i] > srcArray[j]){int temp=srcArray [i];srcArray[i] = srcArray[j];srcArray[j] = temp;}}}// 输出排序后的序列for(int a =0;a<srcArray.length;a++)System.out.println(srcArray[a]);}/*** 执行 简单选择排序*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{9, 1, 5, 8, 3, 7, 4, 2, 6};// 输出结果chooseSort(src);}}

1.5.2 性能分析

在这里插入图片描述

1.6 堆排序

大顶堆 是 根节点值 > 左右孩子的值的 完全二叉树

利用堆（大 / 小顶堆） 进行排序 的方法

  • 充分利用了完全二叉树深度 = [log2n] + 1的特性
  • 是 简单选择排序 的优化 & 改进

1.6.1 代码实现

public class HeapSort {/*** 执行 堆排序 算法*/public static void main(String[] args) {// 定义待排序数列int[] src = new int[]{ 50, 10, 90, 30, 70, 40, 80, 60, 20 };// 输出结果heapSort(src);}/*** 堆排序算法*/private static void heapSort(int[] arr) {// 步骤1：将待排序的序列构建成一个大顶堆for (int i = arr.length / 2; i >= 0; i--){// i = i / 2 ：求出非终端结点（即，具备孩子的结点）// 逐渐递减： i = 4-3-2-1heapAdjust(arr, i, arr.length);}for (int i = arr.length - 1; i > 0; i--) {// 步骤2：交换 根节点 与 末尾元素swap(arr, 0, i);// 步骤3：将序列剩余的（n-1）个记录重新构造成大顶堆heapAdjust(arr, 0, i);// 循环步骤2 、3，直到整个序列有序}// 输出排序后的序列for(int a =0;a<arr.length;a++)System.out.println(arr[a]);}/*** 构建堆的过程* 参数说明：* @param arr = 需排序的数组* @param i = 需要构建堆的根节点的序号* @param n = 数组的长度*/private static void heapAdjust(int[] arr, int i, int n) {int child;int father;for (father = arr[i]; leftChild(i) < n; i = child) {child = leftChild(i);// 若左子树＜右子树，则比较右子树和父节点if (child != n - 1 && arr[child] < arr[child + 1]) {child++; // 序号增1，指向右子树}// 若父节点＜孩子结点，则需要交换if (father < arr[child]) {arr[i] = arr[child];} else {// 大顶堆结构未被破坏，不需要调整break;}}arr[i] = father;}// 获取左孩子结点 位置private static int leftChild(int i) {return 2 * i + 1;}// 交换元素位置private static void swap(int[] arr, int index1, int index2) {int tmp = arr[index1];arr[index1] = arr[index2];arr[index2] = tmp;}
}

1.6.2 性能分析

在这里插入图片描述
不适合待排序序列个数较少的情况，原因 = 初始构建堆的比较次数较多

1.7 归并排序

分治 + 归并

有2种实现方式：递归 & 非递归方式

1.7.1 递归实现

public class MergeSort {/*** 归并排序算法实现* 参数说明：* @param arr = 需排序的数组序列* @param low = 数组第1个元素下标* @param high = 数组最后1个元素下标*/public static void mergeSort(int[] arr, int low, int high) {// 1. 计算出序列中间元素下标// 使用(low+high)/2 求中间位置容易溢出// 右移1位，相当于除以2，但右移的运算速度更快int mid = low + ( (high-low)>>1 );if (low < high) {// 2. （分治） 将初始序列 逐步对半划分成半子表，直到初始序列 = n个子序列// 通过 递归 实现// a. 左一半（第1个元素 - 中间元素）mergeSort(arr, low, mid);// b. 右一半（ 中间元素后1位 - 最后1个元素）mergeSort(arr, mid + 1, high);// 3. （归并）将划分的子序列 有序的两两合并,最终合并成1个长度 = n 的有序序列merge(arr, low, mid, high);}}/*** 归并排序算法中的有序合并序列 实现* 参数说明：* @param arr = 需排序的数组序列* @param low = 数组第1个元素 下标* @param mid = 数组中间元素 下标* @param high = 数组最后1个元素 下标*/public static void merge(int[] arr, int low, int mid, int high) {// 1. 定义1个辅助数组用于存储结果int[] temp = new int[high - low + 1];int i = low; // 左指针，指向数组第1个元素 下标int j = mid + 1; // 右指针，指向数组中间元素的后1个下标int k = 0;// 2. 比较左、右两边的元素大小，将较小的数先移到新数组中while (i <= mid && j <= high) {if (arr[i] < arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 3. 把左边剩余的数移入新数组while (i <= mid) {temp[k++] = arr[i++];}// 4. 把右边剩余的数移入新数组while (j <= high) {temp[k++] = arr[j++];}// 5. 把新数组中的数覆盖到原有数组中for (int k2 = 0; k2 < temp.length; k2++) {arr[k2 + low] = temp[k2];}}/*** 执行 归并排序算法*/public static void main(String[] args) {// 待排序序列int arr[] = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };// 执行 归并排序序列mergeSort(arr, 0, arr.length - 1);// 输出排序后的序列for(int a =0;a<arr.length;a++)System.out.println(arr[a]);}
}

1.7.2 非递归实现

public class MergeSort {/*** 归并排序算法实现：非递归* 参数说明：* @param arr = 需排序的数组序列*/public static void mergeSort(int[] arr) {int len = arr.length;int k = 1;while(k < len){MergePass(arr, k, len);k *= 2; // 一组组归并：1、2、4、8、16}}/*** 辅助算法* 作用：归并 数组中的相邻长度 = k的元素*/private static void MergePass(int[] arr, int k, int n){int i = 0;int j;// 从前->后,将2个长度为k的子序列合并为1个while(i < n - 2*k + 1){merge(arr, i, i + k-1, i + 2*k - 1);// 参数2 = 距离长度// 参数3、4 = 合并的位置，如合并第1个 & 第2个位置的元素到新建的数组中i += 2*k;}// 该代码的作用：保证将最后“落单”的、长度不足两两合并的部分 和 前面的合并起来if(i < n - k ){merge(arr, i, i+k-1, n-1);}}/*** 归并排序算法中的有序合并序列 实现* 参数说明：* @param arr = 需排序的数组序列*/public static void merge(int[] arr, int low, int mid, int high) {// 辅助数组 = 暂存合并的结果int[] temp = new int[high - low + 1];int i = low; // 左指针int j = mid + 1; // 右指针int k = 0;// 把较小的数先移到新数组中while (i <= mid && j <= high) {if (arr[i] < arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 把左边剩余的数移入数组while (i <= mid) {temp[k++] = arr[i++];}// 把右边剩余的数移入数组while (j <= high) {temp[k++] = arr[j++];}// 把新数组中的数覆盖nums数组for (int k2 = 0; k2 < temp.length; k2++) {arr[k2 + low] = temp[k2];}}/*** 执行 归并排序算法*/public static void main(String[] args) {// 待排序序列int arr[] = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };// 执行 归并排序序列mergeSort(arr);// 输出排序后的序列for(int a =0;a<arr.length;a++)System.out.println(arr[a]);}
}

1.7.3 性能分析

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/479474.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

如何构建SAAS项目

如何构建SAAS项目

在后台使用JDBC方式动态创建用户输入的数据库信息&#xff08;库名、地址、用户名、密码&#xff09; 执行预先写好的sql文件&#xff08;如mybatis的scriptRunner)执行建表语句及插入基础数据&#xff08;管理员用户、普通用户&#xff09;
阅读更多...
MQ高级2：MQ的可靠性

MQ高级2：MQ的可靠性

欢迎来到“雪碧聊技术”CSDN博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…
阅读更多...
transformer学习笔记-神经网络原理

transformer学习笔记-神经网络原理

在深度学习领域&#xff0c;transformer可以说是在传统的神经网络的基础上发展而来&#xff0c;着重解决传统神经网络长距离关联、顺序处理、模型表达能力等问题。 在学习transformer之前&#xff0c;我想&#xff0c;有必要先对传统的神经网络做简要的了解。 一、神经网络基本…
阅读更多...
【前端】JavaScript中的字面量概念与应用详解

【前端】JavaScript中的字面量概念与应用详解

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: 前端 文章目录 &#x1f4af;前言&#x1f4af;字面量1. 数字字面量2. 字符串字面量3. 布尔字面量4. 空值字面量&#xff08;null&#xff09;5. 对象字面量6. 数组字面量7. 正则表达式字面量8. 特殊值字面量9. 函数字…
阅读更多...
字节跳动青训营刷题笔记19

字节跳动青训营刷题笔记19

问题描述 小R正在组织一个比赛&#xff0c;比赛中有 n 支队伍参赛。比赛遵循以下独特的赛制&#xff1a; 如果当前队伍数为 偶数&#xff0c;那么每支队伍都会与另一支队伍配对。总共进行 n / 2 场比赛&#xff0c;且产生 n / 2 支队伍进入下一轮。如果当前队伍数为 奇数&…
阅读更多...
Python中的简单爬虫

Python中的简单爬虫

文章目录 一. 基于FastAPI之Web站点开发1. 基于FastAPI搭建Web服务器2. Web服务器和浏览器的通讯流程3. 浏览器访问Web服务器的通讯流程4. 加载图片资源代码 二. 基于Web请求的FastAPI通用配置1. 目前Web服务器存在问题2. 基于Web请求的FastAPI通用配置 三. Python爬虫介绍1. 什…
阅读更多...
【ArcGISPro】使用AI提取要素-土地分类（sentinel2）

【ArcGISPro】使用AI提取要素-土地分类（sentinel2）

Sentinel2数据处理 【ArcGISPro】Sentinel-2数据处理-CSDN博客 土地覆盖类型分类 处理结果
阅读更多...
WinForm 的Combox下拉框 在FlatStyle.Flat的边框设置

WinForm 的Combox下拉框 在FlatStyle.Flat的边框设置

现象&#xff1a;Combox在设置FlatStyle.Flat时边框不见了 效果&#xff1a; 解决问题思路封装新控件&#xff1a; public class DBorderComboBox : ComboBox {private const int WM_PAINT 0xF;[Browsable(true)][Category("Appearance")][Description("边框…
阅读更多...
Python 爬虫入门教程：从零构建你的第一个网络爬虫

Python 爬虫入门教程：从零构建你的第一个网络爬虫

网络爬虫是一种自动化程序&#xff0c;用于从网站抓取数据。Python 凭借其丰富的库和简单的语法&#xff0c;是构建网络爬虫的理想语言。本文将带你从零开始学习 Python 爬虫的基本知识&#xff0c;并实现一个简单的爬虫项目。 1. 什么是网络爬虫&#xff1f; 网络爬虫&#x…
阅读更多...
使用UE5.5的Animator Kit变形器

使用UE5.5的Animator Kit变形器

UE5.5版本更新了AnimatorKit内置插件&#xff0c;其中包含了一些内置变形器&#xff0c;可以辅助我们的动画制作。 操作步骤 首先打开UE5.5&#xff0c;新建第三人称模板场景以便测试&#xff0c;并开启AnimatorKit组件。 新建Sequence&#xff0c;放入测试角色 点击角色右…
阅读更多...
Uniapp 安装安卓、IOS模拟器并调试

Uniapp 安装安卓、IOS模拟器并调试

一、安装Android模拟器并调试 1. 下载并安装 Android Studio 首先下载 Mac 环境下的 Android Studio 的安装包&#xff0c;为dmg 格式。 下载完将Android Studio 向右拖拽到Applications中&#xff0c;接下来等待安装完成就OK啦&#xff01; 打开过程界面如下图所示&#xf…
阅读更多...
shell(5)字符串运算符和逻辑运算符

shell(5)字符串运算符和逻辑运算符

声明&#xff01; 学习视频来自B站up主 泷羽sec 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&#…
阅读更多...
【金蝶双线指标】以看资金进出操作为主，兼顾波段跟踪和短线低吸

【金蝶双线指标】以看资金进出操作为主，兼顾波段跟踪和短线低吸

如上图&#xff0c;个股副图指标&#xff0c;大佬资金监控短线低吸攻击线操盘线趋势红蝴蝶&#xff0c;五大功能于一体。下面慢慢给大家仔细分享。 大佬资金监控指标&#xff0c;红绿进出&#xff0c;绿色缩小到极致&#xff0c;接近零轴&#xff0c;红绿柱分界线&#xff0c;为…
阅读更多...
多输入多输出 | Matlab实现TCN-GRU时间卷积神经网络结合门控循环单元多输入多输出预测

多输入多输出 | Matlab实现TCN-GRU时间卷积神经网络结合门控循环单元多输入多输出预测

多输入多输出 | Matlab实现TCN-GRU时间卷积神经网络结合门控循环单元多输入多输出预测 目录 多输入多输出 | Matlab实现TCN-GRU时间卷积神经网络结合门控循环单元多输入多输出预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 多输入多输出 | Matlab实现TCN-GRU时间卷积…
阅读更多...
HCIA笔记4--VLAN划分

HCIA笔记4--VLAN划分

1. vlan是什么 vlan: virtual lan; 虚拟局域网的简称。 主要目的是隔离广播域。 2. vlan报文格式 在普通的以太网数据帧开关的12字节后添加4字节的vlan tag。而来区分vlan的是其中的vid部分12个比特位&#xff0c;范围自然就是0~2^12-1(0~4095); 0 4095保留使用。实际使用的是…
阅读更多...
蓝牙定位的MATLAB仿真程序|基于信号强度的定位，平面、四个蓝牙基站（附源代码）

蓝牙定位的MATLAB仿真程序|基于信号强度的定位，平面、四个蓝牙基站（附源代码）

这段代码通过RSSI信号强度实现了蓝牙定位&#xff0c;展示了如何使用锚点位置和测量的信号强度来估计未知点的位置。它涵盖了信号衰减模型、距离计算和最小二乘法估计等基本概念。通过图形化输出&#xff0c;用户可以直观地看到真实位置与估计位置的关系。 文章目录 蓝牙定位原…
阅读更多...
基于Springboot企业级工位管理系统【附源码】

基于Springboot企业级工位管理系统【附源码】

基于Springboot企业级工位管理系统 效果如下&#xff1a; 系统登录页面 员工主页面 部门信息页面 员工管理页面 部门信息管理页面 工位信息管理页面 工位分配管理页面 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所。…
阅读更多...
Spring Boot教程之十： 使用 Spring Boot 实现从数据库动态下拉列表

Spring Boot教程之十： 使用 Spring Boot 实现从数据库动态下拉列表

使用 Spring Boot 实现从数据库动态下拉列表 动态下拉列表&#xff08;或依赖下拉列表&#xff09;的概念令人兴奋&#xff0c;但编写起来却颇具挑战性。动态下拉列表意味着一个下拉列表中的值依赖于前一个下拉列表中选择的值。一个简单的例子是三个下拉框&#xff0c;分别显示…
阅读更多...
SpringBoot源码-spring boot启动入口ruan方法主线分析（一）

SpringBoot源码-spring boot启动入口ruan方法主线分析（一）

一、SpringBoot启动的入口 1.当我们启动一个SpringBoot项目的时候&#xff0c;入口程序就是main方法&#xff0c;而在main方法中就执行了一个run方法。 SpringBootApplication public class StartApp {public static void main(String[] args) {// testSpringApplication.ru…
阅读更多...
AI 助力开发新篇章：云开发 Copilot 深度体验与技术解析

AI 助力开发新篇章：云开发 Copilot 深度体验与技术解析

本文 一、引言&#xff1a;技术浪潮中的个人视角1.1 AI 和低代码的崛起1.2 为什么选择云开发 Copilot&#xff1f; 二、云开发 Copilot 的核心功能解析2.1 自然语言驱动的低代码开发2.1.1 自然语言输入示例2.1.2 代码生成的模块化支持 2.2 实时预览与调整2.2.1 实时预览窗口功能…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023