八大排序之插入排序和归并排序

简介: 八大排序之插入排序和归并排序

排序的概念:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持 不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳 定的;否则称为不稳定的。

1、插入排序

1)直接插入排序

基本思想:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。步骤:每次从无序部分中取出一个元素,与有序部分中的元素从后向前依次进行比较,并找到合适的位置,将该元素插到有序组当中。可以看下面动画展示:



网络异常,图片无法展示
|

public class 直接插入排序 {
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
                swap(arr, j, j + 1);
            }
        }
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) {
        int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48
        insertionSort(arr);
    }
}

插入排序优化(二分)

将待排序的元素与有序部分的元素比较时,不再挨个比较,而是用二分折中的方式进行比较,去寻找到arr[i]的位置,加快了比较效率

import java.util.Arrays;
public class 直接插入排序二分 {
    public static void insertionSort(int[] arr) {
        int j,left,mid,right,temp;
        for(int i = 1;i<arr.length;i++){
            left = 0;
            right = i-1;
            temp = arr[i];
            /*找到合适的插入位置right+1,如果中间位置元素
             *比要插入元素大,则查找区域向低半区移动,否则向高半区移动
             */
            while(left <= right){
                mid = (left+right)/2;
                if(arr[mid]>temp){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
            /*right+1后的元素后移*/
            for(j = i-1;j >= right+1;j--)
            {
                arr[j+1] = arr[j];
            }
            /*将元素插入到指定位置*/
            arr[j+1] = temp;
        }
    }
    public static void main(String[] args) {
        int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48
        insertionSort(arr);
    }
}

总结

直接插入排序的特性总结:

1. 元素集合越接近有序,直接插入排序算法的时间效率越高

2. 时间复杂度:最环情况:O(N²)。最好情况:O(N)

3. 空间复杂度:O(1)

4. 稳定性:稳定

5. 适用场景:待排序序列的元素个数不多时,且元素基本偏向有序。

2)希尔排序

希尔排序法又称缩小增量法,该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序法的基本思想是:首先取一个整数n(小于序列元素总数)作为间隔,

把待排序数字中所有数分成几个组,所有间隔相同的数分在同一组内,并对每一组内的数进行排序。缩小间隔n,重复上述分组和排序的工作。当达到n=1 时,所有记录统一在一组内排好序。其实从上面的希尔排序的思想中也能看出希尔排序的实现步骤:

  1. 选n,划分逻辑分组,组内进行直接插入排序。
  2. 不断缩小n,继续组内进行插入排序。
  3. 直到n=1,在包含所有元素的序列内进行直接插入排序。

其中缩小间隔gap 的取法有多种。最初 Shell 提出取 gap =n/2,gop =gap/2,直到 gap =1。后来 Knuth 提出取 gap =gap/3 +1。还有人提出都为好有人提 gap 互质为好。无论哪一种主张都没有得到证明。


de5ac63890ee4ac9aa457a2ca72c3efd.png

import java.util.Arrays;
public class 希尔排序 {
    public static void shellSort(int[] arr){
        /*初始化划分增量*/
        int n = arr.length;
        int temp;
        /*每次减小增量,直到n = 1*/
        while (n > 1){
            /*增量的取法之一:除2向下取整*/
            n = n/2;
            /*对每个按gap划分后的逻辑分组,进行直接插入排序*/
            for (int i = n; i < arr.length; ++i) {
                if (arr[i-n] > arr[i]) {
                    temp = arr[i];
                    int j = i-n;
                    while (j >= 0 && arr[j] > temp) {
                        arr[j+n] = arr[j];
                        j -= n;
                    }
                    arr[j+n] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr={1,8,6,29,10,14,37,48};//排序结果为1,6,8,10,14,29,37,48
        shellSort(arr);
    }
}

希尔排序优化(二分)

由于希尔排序是基于插入排序的,所以在插入排序中也可运用直接插入排序中的优化方式,所有也可以以二分折中的方式来优化希尔排序。

package 插入排序;
import java.util.Arrays;
public class 希尔排序二分 {
    public static void shellSort(int[] arr) {
        int j, left, mid, right, temp;
        int n = arr.length;
        while (n > 1) {
            n /= 2;
            for (int i = n; i < arr.length; i++) {
                left = 0;
                right = i - 1;
                temp = arr[i];
                while (left <= right) {
                    mid = (left + right) / 2;
                    if (arr[mid] > temp) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                for (j = i - n; j >= right + 1; j-=n) {
                    arr[j + n] = arr[j];
                }
                arr[j + n] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {1, 8, 6, 29, 10, 14, 37, 48};//排序结果为1,6,8,10,14,29,37,48
        shellSort(arr);
    }
}

总结

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些书中给出的希尔排序的时间复杂度都不固定。时间复杂度:平均情况:(nlogn)~  o(n²) 。最好情况:o(n¹˙³)。最环情况: o(n²) 。
  4. 空间复杂度:0(1)
  5. 稳定性:不稳定
  6. 适用场景:待排序序列元素较少时。

2、归并排序

1945年,约翰·冯·诺依曼(John von Neumann)发明了归并排序。归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

归并排序有两个基本的操作,一个是,也就是把原数组划分成两个子数组的过程。另一个是,它将两个有序数组合并成一个更大的有序数组。

基本思路:将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:




image.png

动画展示:




网络异常,图片无法展示
|

import java.util.Arrays;
public class 归并排序 {
    static void merge(int[] arr, int[] result, int start, int end) {
        if (start >= end)
            return;
        int len = end - start, mid = (len >> 1) + start;
        int start1 = start;
        int start2 = mid + 1;
        /*通过递归不断分成小块,然后再进行排序*/
        merge(arr, result, start1, mid);
        merge(arr, result, start2, end);
        int k = start;
        /*进行比较排序*/
        while (start1 <= mid && start2 <= end)
            result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
        /*防止某段期间的数组整体大于另一段数组,所有接着将剩余的数拷贝到result数组中*/
        while (start1 <= mid)
            result[k++] = arr[start1++];
        while (start2 <= end)
            result[k++] = arr[start2++];
        /*重新拷贝到原数组*/
        for (k = start; k <= end; k++)
            arr[k] = result[k];
    }
    public static void mergesort(int[] arr) {
        int[] result = new int[arr.length];
        merge(arr, result, 0, arr.length - 1);
    }
    public static void main(String[] args) {
        int[] arr = {1, 8, 6, 29, 10, 14, 37, 48};//排序结果为1,6,8,10,14,29,37,48
        mergesort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

总结

1. 归并的缺点在于需要O(N)的空间复杂度,但是其速度仅次于快速排序

2. 时间复杂度:O(N*logN)

3. 空间复杂度:O(N)

4. 稳定性:稳定

5.适用场景:待排序序列中元素较多,并且要求较快的排序速度时。

归并排序解决海量数据的排序问题

外部排序:排序过程需要在磁盘等外部存储进行的排序

前提:内存只有 1G,需要排序的数据有 100G

因为内存中因为无法把所有数据全部放下,所以需要外部排序,而归并排序是最常用的外部排序


1. 先把文件切分成 200 份,每个 512 M


2. 分别对 512 M 排序,因为内存已经可以放的下,所以任意排序方式都可以


3. 进行 2路归并,同时对 200 份有序文件做归并过程,最终结果就有序了


目录
相关文章
|
存储 Python
海明距离(Hamming Distance)
海明距离(Hamming Distance)是用来衡量两个二进制数之间差异程度的指标,它表示两个二进制数之间最多有多少个比特的差异。海明距离可以用于衡量数据传输或存储中的错误率,以及检测噪声干扰。 海明距离的计算方法是:对于两个 n 位二进制数,将它们进行逐位比较,如果对应位上的数字不同,则计算距离时增加 1。然后将所有位上的距离加在一起,得到海明距离。
2595 1
|
4月前
|
存储 安全 Java
Java 基础知识面试题汇总 最全面的 Java 基础面试题整理
本文全面解析Java基础知识面试题,涵盖Java基础概念、面向对象编程、异常处理、集合框架等核心内容。通过实际应用场景,提供技术方案与应用实例,如JDK与JRE区别、==与equals()差异、String类特性、final与static关键字用法、多继承替代方案及接口与抽象类对比。帮助开发者夯实基础,高效备考,提升实战能力。附带完整代码示例,可供下载学习。
595 3
|
10月前
|
Python
使用pycharm 开发streamlit的项目启动
要在 PyCharm 中配置 Streamlit 环境并调试应用,请按以下步骤操作:1. 确保 PyCharm 配置了 Python 解释器并安装 Streamlit 包(File -&gt; Settings -&gt; Project -&gt; Python Interpreter)。2. 配置调试运行设置(Run -&gt; Edit Configurations,添加 Python 配置并命名)。3. 选择新配置并点击调试按钮启动应用。
950 23
|
10月前
|
存储 人工智能 自然语言处理
ChatMCP:基于 MCP 协议开发的 AI 聊天客户端,支持多语言和自动化安装 MCP 服务器
ChatMCP 是一款基于模型上下文协议(MCP)的 AI 聊天客户端,支持多语言和自动化安装。它能够与多种大型语言模型(LLM)如 OpenAI、Claude 和 OLLama 等进行交互,具备自动化安装 MCP 服务器、SSE 传输支持、自动选择服务器、聊天记录管理等功能。
2386 16
ChatMCP:基于 MCP 协议开发的 AI 聊天客户端,支持多语言和自动化安装 MCP 服务器
|
存储 JavaScript 前端开发
【MySQL】MySQL9.0发布,有点小失望
本文介绍了MySQL 9.0新版本的更新情况及其主要特性,包括JavaScript存储过程、VECTOR类型支持、内联和隐式外键约束等。作者详细讲解了如何在官网上查找新特性,并提供了两种下载方法:官网下载和Docker镜像。此外,文章还探讨了老版本是否需要升级至MySQL 9.0的问题,最终认为新特性并不足以成为升级的必要理由。适合对MySQL新版本感兴趣的读者参考。
2330 1
【MySQL】MySQL9.0发布,有点小失望
|
机器学习/深度学习 人工智能 关系型数据库
安全多方计算之七:门限密码系统
安全多方计算之七:门限密码系统
|
SQL 关系型数据库 MySQL
数据库系统概论 ---- 第三章 -- 关系数据库标准语言SQL(3.5-3.7)(一)
数据库系统概论 ---- 第三章 -- 关系数据库标准语言SQL(3.5-3.7)
|
存储 安全 Linux
【操作系统篇】第三篇——进程(概念,组成,状态与转换,控制以及通信)
【操作系统篇】第三篇——进程(概念,组成,状态与转换,控制以及通信)
【操作系统篇】第三篇——进程(概念,组成,状态与转换,控制以及通信)
|
数据采集 机器学习/深度学习 数据挖掘
机器学习数据预处理——归一化(Normalization)和标准化(standardlization)
昨天进行一场答辩,被评委老师问起来归一化的概念,一时间紧张没有想起来,后来复盘回忆,感觉还是自己的理解不够深刻,才导致关键时刻掉链子,没有想起。所以特此整理一下,以供加深印象。
2759 0

热门文章

最新文章