数据结构与算法之排序(冒泡、选择、插入、希尔、归并、快速)(二)

简介: 数据结构与算法之排序(冒泡、选择、插入、希尔、归并、快速)

二、高级排序


上面我们学习过基础排序,包括冒泡排序,选择排序还有插入排序,并且对他们在最坏情况下的时间复杂度做了分析,发现都是O(N^2),而平方阶通过我们之前学习算法分析我们知道,随着输入规模的增大,时间成本将急剧上升,所以这些基本排序方法不能处理更大规模的问题,接下来我们学习一些高级的排序算法,争取降低算法的时间复杂度最高阶次幂


2.1.希尔排序


希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本


前面学习插入排序的时候,我们会发现一个很不友好的事儿,如果已排序的分组元素为 {2,5,7,9,10},未排序的分组元素为{1,8},那么下一个待插入元素为1,我们需要拿着1从后往前,依次和10,9,7,5,2进行交换位置,才能完成真正的插入,每次交换只能和相邻的元素交换位置。那如果我们要提高效率,直观的想法就是一次交换,能把1放到更前面的位置,比如一次交换就能把1插到2和5之间,这样一次交换1就向前走了5个位置,可以减少交换的次数,这样的需求如何实现呢?接下来我们来看看希尔排序的原理


需求:


排序前:{9,1,2,5,7,4,8,6,3,5}

排序后:{1,2,3,4,5,5,6,7,8,9}


排序原理:


1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组;

2.对分好组的每一组数据完成插入排序;

3.减小增长量,最小减为1,重复第二步操作。


3268ce4242d14abf8887cd2f66684b63.png

增长量 h的确定:增长量h的值每一固定的规则,我们这里采用以下规则:

int h=1
while(h<5){
  h=2h+1;//3,7
}
//循环结束后我们就可以确定h的最大值;
//h的减小规则为:
  h=h/2


希尔排序的API设计:


image.png

希尔排序的代码实现:

//排序代码
public class Shell {
  /*
  对数组a中的元素进行排序
  */
  public static void sort(Comparable[] a){
    int N = a.length;
    //确定增长量h的最大值
    int h=1;
    while(h<N/2){
      h=h*2+1;
    }
    //当增长量h小于1,排序结束
    while(h>=1){
      //找到待插入的元素
      for (int i=h;i<N;i++){
      //a[i]就是待插入的元素
      //把a[i]插入到a[i-h],a[i-2h],a[i-3h]...序列中
        for (int j=i;j>=h;j-=h){
        //a[j]就是待插入元素,依次和a[j-h],a[j-2h],a[j-3h]进行比较,如果a[j]小,那么
        交换位置,如果不小于,a[j]大,则插入完成。
        if (greater(a[j-h],a[j])){
          exch(a,j,j-h);
        }else{
        break;
        }
      }
    }
    h/=2;
  }
}
  /*
  比较v元素是否大于w元素
  */
  private static boolean greater(Comparable v,Comparable w){
    return v.compareTo(w)>0;
  }
  /*
  数组元素i和j交换位置
  */
  private static void exch(Comparable[] a,int i,int j){
    Comparable t = a[i];
    a[i]=a[j];
    a[j]=t;
  }
}
//测试代码
public class Test {
  public static void main(String[] args) {
    Integer[] a = {9,1,2,5,7,4,8,6,3,5} ;
    Shell.sort(a);
    System.out.println(Arrays.toString(a));
  }
}


希尔排序的时间复杂度分析:


在希尔排序中,增长量h并没有固定的规则,有很多论文研究了各种不同的递增序列,但都无法证明某个序列是最好的,对于希尔排序的时间复杂度分析,已经超出了我们课程设计的范畴,所以在这里就不做分析了。我们可以使用事后分析法对希尔排序和插入排序做性能比较。在资料的测试数据文件夹下有一个reverse_shell_insertion.txt文件,里面存放的是从100000到1的逆向数据,我们可以根据这个批量数据完成测试。测试的思想:在执行排序前前记录一个时间,在排序完成后记录一个时间,两个时间的时间差就是排序的耗时。


希尔排序和插入排序性能比较测试代码:

public class SortCompare {
  public static void main(String[] args) throws Exception{
    ArrayList<Integer> list = new ArrayList<>();
    //读取reverse_arr.txt文件
    BufferedReader reader = new BufferedReader(new InputStreamReader(new
    FileInputStream("reverse_shell_insertion.txt")));
    String line=null;
    while((line=reader.readLine())!=null){
      //把每一个数字存入到集合中
      list.add(Integer.valueOf(line));
    }
    reader.close();
    //把集合转换成数组
    Integer[] arr = new Integer[list.size()];
    list.toArray(arr);
    testInsertion(arr);//使用插入排序耗时:20859
    // testShell(arr);//使用希尔排序耗时:31
  }
  public static void testInsertion(Integer[] arr){
    //使用插入排序完成测试
    long start = System.currentTimeMillis();
    Insertion.sort(arr);
    long end= System.currentTimeMillis();
    System.out.println("使用插入排序耗时:"+(end-start));
  }
  public static void testShell(Integer[] arr){
    //使用希尔排序完成测试
    long start = System.currentTimeMillis();
    Shell.sort(arr);
    long end = System.currentTimeMillis();
    System.out.println("使用希尔排序耗时:"+(end-start));
  }
}


通过测试发现,在处理大批量数据时,希尔排序的性能确实高于插入排序


2.2.归并排序


2.2.1. 递归


正式学习归并排序之前,我们得先学习一下递归算法。


定义:


定义方法时,在方法内部调用方法本身,称之为递归

public void show(){
  System.out.println("aaaa");
  show();
}

作用:


它通常把一个大型复杂的问题,层层转换为一个与原问题相似的,规模较小的问题来求解。递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。


注意事项:


在递归中,不能无限制的调用自己,必须要有边界条件,能够让递归结束,因为每一次递归调用都会在栈内存开辟新的空间,重新执行方法,如果递归的层级太深,很容易造成栈内存溢出


4866458320c041aa910af586fad7eff7.png

需求:


请定义一个方法,使用递归完成求N的阶乘

分析:
1!: 1
2!: 2*1=2*1!
3!: 3*2*1=3*2!
4!: 4*3*2*1=4*3!
...
n!: n*(n-1)*(n-2)...*2*1=n*(n-1)!
所以,假设有一个方法factorial(n)用来求n的阶乘,那么n的阶乘还可以表示为n*factorial(n-1)

代码实现:

public class Test {
  public static void main(String[] args) throws Exception {
    int result = factorial(5);
    System.out.println(result);
  }
  public static int factorial(int n){
    if (n==1){
    return 1;
  }
  return n*factorial(n-1);
  }
}


2.2.2 归并排序


归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。


需求:


排序前:{8,4,5,7,1,3,6,2}

排序后:{1,2,3,4,5,6,7,8}

排序原理:


1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止。


2.将相邻的两个子组进行合并成一个有序的大组;


3.不断的重复步骤2,直到最终只有一个组为止


fdca0249c61e4b0294382870e43590a1.png


归并排序 API设计:


image.png


归并原理:


a7beadb45ee040969156ef847c7a563a.png

b68d23c0a5e2498391a6ba8b620edc72.png

ec47bab7b5194549afa05c3365ed0830.png

65483221c1ec489ab7a81249c9af6e78.png

b5d7526751ea499a84886f036997c04f.png

归并排序代码实现:

// 排序代码
public class Merge {
  private static Comparable[] assist;//归并所需要的辅助数组
  /*
  对数组a中的元素进行排序
  */
  public static void sort(Comparable[] a) {
    assist = new Comparable[a.length];
    int lo = 0;
    int hi = a.length-1;
    sort(a, lo, hi);
  }
  /*
  对数组a中从lo到hi的元素进行排序
  */
  private static void sort(Comparable[] a, int lo, int hi) {
    if (hi <= lo) {
    return;
  }
  int mid = lo + (hi - lo) / 2;
  //对lo到mid之间的元素进行排序;
  sort(a, lo, mid);
  //对mid+1到hi之间的元素进行排序;
  sort(a, mid+1, hi);
  //对lo到mid这组数据和mid到hi这组数据进行归并
  merge(a, lo, mid, hi);
}
/*
对数组中,从lo到mid为一组,从mid+1到hi为一组,对这两组数据进行归并
*/
private static void merge(Comparable[] a, int lo, int mid, int hi) {
  //lo到mid这组数据和mid+1到hi这组数据归并到辅助数组assist对应的索引处
  int i = lo;//定义一个指针,指向assist数组中开始填充数据的索引
  int p1 = lo;//定义一个指针,指向第一组数据的第一个元素
  int p2 = mid + 1;//定义一个指针,指向第二组数据的第一个元素
  //比较左边小组和右边小组中的元素大小,哪个小,就把哪个数据填充到assist数组中
  while (p1 <= mid && p2 <= hi) {
    if (less(a[p1], a[p2])) {
      assist[i++] = a[p1++];
    } else {
      assist[i++] = a[p2++];
    }
  }
  //上面的循环结束后,如果退出循环的条件是p1<=mid,则证明左边小组中的数据已经归 并完毕,如果退
  出循环的条件是p2<=hi,则证明右边小组的数据已经填充完毕;
  //所以需要把未填充完毕的数据继续填充到assist中,//下面两个循环,只会执行其中的一个
  while(p1<=mid){
    assist[i++]=a[p1++];
  }
  while(p2<=hi){
    assist[i++]=a[p2++];
  }
  //到现在为止,assist数组中,从lo到hi的元素是有序的,再把数据拷贝到a数组中对应的索引处
  for (int index=lo;index<=hi;index++){
    a[index]=assist[index];
  }
}
/*
比较v元素是否小于w元素
*/
private static boolean less(Comparable v, Comparable w) {
  return v.compareTo(w) < 0;
}
/*
数组元素i和j交换位置
*/
private static void exch(Comparable[] a, int i, int j) {
  Comparable t = a[i];
  a[i] = a[j];
  a[j] = t;
}
}
//测试代码
public class Test {
  public static void main(String[] args) throws Exception {
    Integer[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
    Merge.sort(arr);
    System.out.println(Arrays.toString(arr));
  }
}

归并排序时间复杂度分析:


归并排序是分治思想的最典型的例子,上面的算法中,对a[lo…hi]进行排序,先将它分为a[lo…mid]和a[mid+1…hi]两部分,分别通过递归调用将他们单独排序,最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果一个数组不能再被分为两个子数组,那么就会执行merge进行归并,在归并的时候判断元素的大小进行排序


438f41dcf12c4dec8eb59a2ba7e87771.png

用树状图来描述归并,如果一个数组有8个元素,那么它将每次除以2找最小的子数组,共拆log8次,值为3,所以树共有3层,那么自顶向下第k层有2k个子数组,每个数组的长度为2(3-k),归并最多需要2^(3-k)次比较。因此每层的比较次数为 2^k * 2(3-k)=23,那么3层总共为 32^3。


假设元素的个数为n,那么使用归并排序拆分的次数为log2(n),所以共log2(n)层,那么使用log2(n)替换上面32^3中的3这个层数,最终得出的归并排序的时间复杂度为:log2(n)* 2^(log2(n))=log2(n)*n,根据大O推导法则,忽略底数,最终归并排序的时间复杂度为O(nlogn);


归并排序的缺点:


需要申请额外的数组空间,导致空间复杂度提升,是典型的以空间换时间的操作。


归并排序与希尔排序性能测试:


之前我们通过测试可以知道希尔排序的性能是由于插入排序的,那现在学习了归并排序后,归并排序的效率与希尔排序的效率哪个高呢?我们使用同样的测试方式来完成一样这两个排序算法之间的性能比较。


在资料的测试数据文件夹下有一个reverse_arr.txt文件,里面存放的是从1000000到1的逆向数据,我们可以根据这个批量数据完成测试。测试的思想:在执行排序前前记录一个时间,在排序完成后记录一个时间,两个时间的时间差就是排序的耗时。


希尔排序和插入排序性能比较测试代码:

public class SortCompare {
  public static void main(String[] args) throws Exception{
    ArrayList<Integer> list = new ArrayList<>();
    //读取a.txt文件
    BufferedReader reader = new BufferedReader(new InputStreamReader(newFileInputStream("reverse_merge_shell.txt")));
    String line=null;
    while((line=reader.readLine())!=null){
      //把每一个数字存入到集合中
      list.add(Integer.valueOf(line));
    }
    reader.close();
    //把集合转换成数组
    Integer[] arr = new Integer[list.size()];
    list.toArray(arr);
    // testMerge(arr);//使用归并排序耗时:1200
    testShell(arr);//使用希尔排序耗时:1277
  }
  public static void testMerge(Integer[] arr){
    //使用插入排序完成测试
    long start = System.currentTimeMillis();
    Merge.sort(arr);
    long end= System.currentTimeMillis();
    System.out.println("使用归并排序耗时:"+(end-start));
  }
  public static void testShell(Integer[] arr){
    //使用希尔排序完成测试
    long start = System.currentTimeMillis();
    Shell.sort(arr);
    long end = System.currentTimeMillis();
    System.out.println("使用希尔排序耗时:"+(end-start));
  }
}

通过测试,发现希尔排序和归并排序在处理大批量数据时差别不是很大

目录
相关文章
|
2月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
172 7
|
2月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
142 8
|
3月前
|
搜索推荐 Shell
解析排序算法:十大排序方法的工作原理与性能比较
解析排序算法:十大排序方法的工作原理与性能比较
110 9
|
3月前
|
算法 搜索推荐 Java
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
50 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
|
3月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
32 0
|
3月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
40 0
|
3月前
|
搜索推荐 算法
排序算法---冒泡&选择&插入总结
排序算法---冒泡&选择&插入总结
23 0
|
3月前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
92 0
|
8天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
8天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
104 68

热门文章

最新文章