java排序算法图文详解

目录
  • 一、直接插入排序
  • 二、 希尔排序
  • 三、冒泡排序
  • 四、快速排序
  • 五、选择排序(Selection Sort)
  • 六、堆排序
    • 一、堆排序的基本思想是:
    • 二、代码示例
  • 七、归并排序
  • 总结

一、直接插入排序

基本思想:

将一个记录插入到已排序的有序表中,使插入后的表仍然有序

对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序

package Sort;
//插入排序
public class InsertSort {
    public static void main(String[] args) {
        int [] arr={49,38,65,97,76,13,27,49};
        sort(arr);
       print(arr);
    }
    private static void sort(int [] arr) {
        for (int i = 1; i < arr.length; i++) {
           for(int j=i;j>0;j--){
               if(arr[j]<arr[j-1]){
                  swap(arr,j,j-1);
               }
           }
        }
    }
    private static void swap(int [] arr,int i,int j){
        int temp=0;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    private static void print(int [] arr) {
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

13 27 38 49 49 65 76 97

Process finished with exit code 0

二、 希尔排序

希尔排序又称“缩小增量排序”(Diminishing Increment Sort))属于插入排序类。

基本思想:

先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”,待整个序列中的记录”基本有序“时,再对全体记录进行一次直接插入排序。

package Sort;
//希尔排序是插入排序的改良
public class ShellSort {
    public static void main(String[] args) {
        int [] arr={16,25,12,30,47,11,23,36,9,18,31};
        sort(arr);
        print(arr);
    }
    private static void sort(int [] arr) {
        //gap设置优化
        int h=1;
        while(h<arr.length/3){
            h=h*3+1;
        }
       for(int gap=h;gap>0;gap=(gap-1)/3) {//gap:希尔排序的间距
           for (int i = gap; i < arr.length; i++) {
               for (int j = i; j >gap-1; j-=gap) {
                   if (arr[j] < arr[j - gap]) {
                       swap(arr, j, j - gap);
                   }
               }
           }
       }
    }
    private static void swap(int [] arr,int i,int j){
        int temp=0;
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    private static void print(int [] arr) {
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

9 11 12 16 18 23 25 30 31 36 47

Process finished with exit code 0

三、冒泡排序

冒泡排序

四、快速排序

对冒泡排序的一种改进

基本思想:

通过一趟排序将待排序记录分割成独立的两部分,其中一部分的关键字均比另一部分的关键字小,则可分别对这两部分记录继续分别进行排序,以达到整个序列有序。

package Sort;
import java.util.Arrays;
//快速排序
public class QuickSort {
    public static void main(String[] args) {
        int[] arr={49,38,65,97,76,13,27,49};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    private static void sort(int [] arr,int start,int end) {
       if(start<end){
           //把数组的第0个数作为标准数
           int stared=arr[start];
           //记录要排序的下标
           int low=start;
           int height=end;
           //循环找出比标准数大和比标准数小的数
           while(low<height){
               //右边数字比标准数大
               while(low<height&&stared<=arr[height]){
                   height--;
               }
               //用右边的数字替换左边的数字
               arr[low]=arr[height];
               //左边数字比标准数小
               while(low<height&&stared>=arr[low]){
                   low++;
               }
               //用左边的数字替换右边的数字
               arr[height]=arr[low];
           }
           arr[low]=stared;
           sort(arr,start,low);
           sort(arr,low+1,height);
       }
    }
    }

[13, 27, 38, 49, 76, 97, 65, 49]

Process finished with exit code 0

五、选择排序(Selection Sort)

选择排序

六、堆排序

      堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。

每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

1、大顶堆举例说明:

我们对堆中的结点按层进行编号,映射到数组中就是下面这个样子:

大顶堆特点:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点,i从0开始编号

2、小顶堆举例说明

小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点,i从0开始编号

一般升序采用大顶堆,降序采用小顶堆

堆排序基本思想

一、堆排序的基本思想是:

将待排序序列构造成一个大顶堆

此时,整个序列的最大值就是堆顶的根节点。

将其与末尾元素进行交换,此时末尾就为最大值。

然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。

二、代码示例

package Sort;
import java.util.Arrays;
/**构造大顶堆
 * 1、原顺序二叉树     非叶子节点在数组中的索引i=1时;arr[i]=6    i=0时
 *     4                   i的右节点值比它大,交换得 :              9
 *    /\                         4                                  /\
 *   6  8                       /\                                 6  8
 *  /\                         9  8                               /\
 * 5 9                        /\                                 5 4
 *                           5 6
 */

public class HeapSort {
    public static void main(String[] args) {
        int [] arr={4,6,8,5,9};
        heapSort(arr);
    }
    //编写一个堆排序的方法
    public static void heapSort(int[] arr){
        int temp=0;
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
        }
        //将堆顶元素与末尾元素进行交换,此时末尾就为最大值,将最大值全放在数组最后
        //重新调整结构,使其满足堆定义,继续交换堆顶元素与当前末尾元素,反复执行调整交换步骤,使整个序列达到有序
        for(int j=arr.length-1;j>0;j--) {
            //交换
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        System.out.println("数组"+Arrays.toString(arr));
    }
    //将数组调整为一个大顶堆
    /**
     * 功能:完成将以i对应的非叶子节点的树调整成大顶堆
     * 举例:int[]arr={4,6,8,5,9};=>i=1=>adjustHeap=>得到{4,9,8,5,6}
     * 如果再次调整adjustHeap传入i=0,{4,9,8,5,6}=>得到{9,6,8,5,4}
     * @param arr  表示要调整的数组
     * @param i   表示非叶子节点在数组中的索引
     * @param length  表示对多少个元素进行调整,length在逐渐减少
     */
    public static void adjustHeap(int[]arr,int i,int length){
         int temp=arr[i];//先取出当前元素的值,保存在临时变量中
        //开始调整
        //k=i*2+1;k是i节点的左子节点
        for(int k=i*2+1;k<length;k=k*2+1){
              if(k+1<length&&arr[k]<arr[k+1]){//说明左子节点的值小于右子节点的值
                 k++;//k指向右子节点
              }
              if(arr[k]>temp){//如果子节点大于父节点
                  arr[i]=arr[k];//把较大的值赋给当前节点
                  i=k;//!!!i指向k,继续循环比较
              }else{
                  break;
              }
        }
        //当for循环结束后,已经将以i为父结点的最大值放在了堆顶上(局部)
          arr[i]=temp;//将temp的值放在调整后的位置
    }
}

堆排序结果:

数组[4, 5, 6, 8, 9]

七、归并排序

定义:

又一类不同的排序方法,将两个或两个以上的有序表合并成一个新的有序表。

需要辅助空间:O(n)

整个归并需要 [log2n]

时间复杂度:O(nlog2n)

缺点:归并排序占用附加存储较多, 需要另外一个与原待排序对象数组同样大小的辅助数组。

优点:归并排序是一个稳定的排序方法

思路可以推广到“多路归并”

常用于外部排序

package Sort;
//归并排序
public class MergeSort {
    public static void main(String[] args) {
        int [] arr={4,5,7,8,1,2,3,6};
        sort(arr);
        print(arr);
    }
    private static void sort(int [] arr) {
        int mid=arr.length/2;
        int[]temp=new int[arr.length];
        int i=0;//标记左边数组
        int j=mid+1;//标记右边数组起始点
        int k=0;
        while(i<=mid&&j<arr.length){
            if(arr[i]<=arr[j]){
               temp[k]=arr[i];
               i++;
               k++;
            }else{
                temp[k]=arr[j];
                j++;
                k++;
            }
        }
        while(i<=mid){temp[k++]=arr[i++];}//将左边剩余的,复制到数组
        while(j<arr.length){temp[k++]=arr[j++];}//将右边剩余的,复制到数组
    }

    private static void print(int [] arr) {
        for (int i = 0; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}

1 2 3 4 5 6 7 8

Process finished with exit code 0

总结

本篇文章就到这里了,希望可以给你带来一些帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • Java数据结构与算法入门实例详解

    第一部分:Java数据结构 要理解Java数据结构,必须能清楚何为数据结构? 数据结构: Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构. 而一个数据结构的设计过程分成抽象层.数据结构层和实现层. 数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构. 一.Java数据结构之:线性数据结构 线性数据结构:常见的

  • 详解Java实现分治算法

    目录 一.前言 二.分治算法介绍 三.分治算法经典问题 3.1.二分搜索 3.2.快速排序 3.3.归并排序(逆序数) 3.4.最大子序列和 3.5.最近点对 四.结语 一.前言 在学习分治算法之前,问你一个问题,相信大家小时候都有存钱罐的经历,父母亲人如果给钱都会往自己的宝藏中存钱,我们每隔一段时间都会清点清点钱.但是一堆钱让你处理起来你可能觉得很复杂,因为数据相对于大脑有点庞大了,并且很容易算错,你可能会将它先分成几个小份算,然后再叠加起来计算总和就获得这堆钱的总数了 当然如果你觉得各个部分

  • 详解Java如何实现FP-Growth算法

    FP-Growth算法的Java实现 这篇文章重点讲一下实现.需要两次扫描来构建FP树 第一次扫描 第一次扫描,过滤掉所有不满足最小支持度的项:对于满足最小支持度的项,按照全局支持度降序排序. 按照这个需求,可能的难点为如何按照全局支持度对每个事务中的item排序. 我的实现思路 扫描原数据集将其保存在二维列表sourceData中 维护一个Table,使其保存每个item的全局支持度TotalSup 在Table中过滤掉低于阈值minSup的项 将Table转换为List,并使其按照Total

  • java数组算法例题代码详解(冒泡排序,选择排序,找最大值、最小值,添加、删除元素等)

    数组算法例题 1.数组逆序 第一个和最后一个互换,第二个和倒数第二个互换,就相当于把数组想下图一样,进行对折互换,如果数组个数为奇数,则中间保持不变其余元素互换即可 import java.util.Arrays; class Demo12 { public static void main (String[] args) { int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; System.out.println(Arrays.toString(arr));

  • 详解Java双轴快速排序算法

    目录 一.前言 二.回顾单轴快排 三.双轴快排分析 3.1.总体情况分析 3.2.k交换过程 3.3.收尾工作 四.双轴快排代码 一.前言 首选,双轴快排也是一种快排的优化方案,在JDK的Arrays.sort()中被主要使用.所以,掌握快排已经不能够满足我们的需求,我们还要学会双轴快排的原理和实现才行. 二.回顾单轴快排 单轴快排也就是我们常说的普通快速排序,对于快速排序我想大家应该都很熟悉:基于递归和分治的,时间复杂度最坏而O(n2),最好和平均情况为O(nlogn). 而快排的具体思路也很

  • java排序算法图文详解

    目录 一.直接插入排序 二. 希尔排序 三.冒泡排序 四.快速排序 五.选择排序(Selection Sort) 六.堆排序 一.堆排序的基本思想是: 二.代码示例 七.归并排序 总结 一.直接插入排序 基本思想: 将一个记录插入到已排序的有序表中,使插入后的表仍然有序 对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序 package Sort; //插入排序 public class InsertSort { public static void main(Str

  • Java DFA算法案例详解

    1.背景 项目中需要对敏感词做一个过滤,首先有几个方案可以选择: 直接将敏感词组织成String后,利用indexOf方法来查询. 传统的敏感词入库后SQL查询. 利用Lucene建立分词索引来查询. 利用DFA算法来进行. 首先,项目收集到的敏感词有几千条,使用a方案肯定不行.其次,为了方便以后的扩展性尽量减少对数据库的依赖,所以放弃b方案.然后Lucene本身作为本地索引,敏感词增加后需要触发更新索引,并且这里本着轻量原则不想引入更多的库,所以放弃c方案.于是我们选定d方案为研究目标. 2.

  • 通俗易懂的C++前缀和与差分算法图文详解

    目录 1.前缀和 2.前缀和算法有什么好处? 3.二维前缀和 4.差分 5.一维差分 6.二维差分 1.前缀和 前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和,而差分可以看成前缀和的逆运算.合理的使用前缀和与差分,可以将某些复杂的问题简单化. 2.前缀和算法有什么好处? 先来了解这样一个问题: 输入一个长度为n的整数序列.接下来再输入m个询问,每个询问输入一对l, r.对于每个询问,输出原序列中从第l个数到第r个数的和. 我们很容易想出暴力解法,遍历区间求和. 代码如下: in

  • Python 十大经典排序算法实现详解

    目录 关于时间复杂度 关于稳定性 名词解释 1.冒泡排序 (1)算法步骤 (2)动图演示 (3)Python代码 2.选择排序 (1)算法步骤 (2)动图演示 (3)Python代码 3.插入排序 (1)算法步骤 (2)动图演示 (3)Python代码 4.希尔排序 (1)算法步骤 (2)Python代码 5.归并排序 (1)算法步骤 (2)动图演示 (3)Python代码 6.快速排序 (1)算法步骤 (2)动图演示 (3)Python代码 7.堆排序 (1)算法步骤 (2)动图演示 (3)P

  • vue2从数据变化到视图变化之diff算法图文详解

    目录 引言 1.isUndef(oldStartVnode) 2.isUndef(oldEndVnode) 3.sameVnode(oldStartVnode, newStartVnode) 4.sameVnode(oldEndVnode, newEndVnode) 5.sameVnode(oldStartVnode, newEndVnode) 6.sameVnode(oldEndVnode, newStartVnode) 7.如果以上都不满足 小结 引言 vue数据的渲染会引入视图的重新渲染.

  • Java @Accessors注解图文详解

    目录 前言 1. @Accessors 源码 2. @Accessors 属性说明 2.1 fluent 属性 2.2 chain 属性 2.3 prefix 属性 总结 前言 在你的工作中,有时候可能会看到 @Accessors(chain = true)  这样的注解,他是 lombok 插件包中的一个注解,那么它是什么意思呢? 1. @Accessors 源码 我们打开 @Accessors 的源码可以看到: (1)该注解主要作用是:当属性字段在生成 getter 和 setter 方法时

  • C++选择排序算法实例详解

    本文实例为大家分享了C++选择排序算法的具体代码,供大家参考,具体内容如下 基本思想 每一趟从无序区中选出最小的元素,顺序放在有序区的最后,直到全部元素排序完毕. 由于选择排序每一趟总是从无序区中选出全局最小(或最大)的元素,所以适用于从大量元速度中选择一部分排序元素.例如,从10000个元素中选出最小的前10位元素. 直接选择排序 1.排序思路 从第i趟开始,从当前无序区arr[i-n-1]中选出最小元素arr[k],将它与有序区的最后一个元素,也就是无序区的第一个元素交换.每趟排序后,有序区

  • java实现快速排序图文详解

    目录 高快省的排序算法 排序算法显神威 总结 高快省的排序算法 有没有既不浪费空间又可以快一点的排序算法呢?那就是"快速排序"啦!光听这个名字是不是就觉得很高端呢. 假设我们现在对"6 1 2 7 9 3 4 5 10 8"这个10个数进行排序.首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了).为了方便,就让第一个数6作为基准数吧.接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放

  • linux安装mysql数据库以及配置Java项目的图文详解

    一.安装mysql数据库 ①下载并解压上传到/opt/soft目录(soft目录是自己创建的) ②解压:tar -xvf mysql-5.7.27-1.el7.x86_64.rpm-bundle.tar ③清空linux自带的数据库 1.查看是否有旧版本的数据库: rpm -qa |grep mysql rpm -qa | grep mariadb 2. 卸载已有的数据库:(卸载会把这个包的依赖包也一起卸载) yum -y remove mariadb-libs.x86_64 ④安装mysql社

  • 高斯混合模型与EM算法图文详解

    目录 一.前言 二.高斯混合模型(GMM) 三.最大似然估计 总结而言: 四.EM算法 五.EM算法的简单理解方式 六.EM算法推导 总结而言 总结 一.前言 高斯混合模型(Gaussian Mixture Model)简称GMM,是一种业界广泛使用的聚类算法.它是多个高斯分布函数的线性组合,理论上GMM可以拟合出任意类型的分布,通常用于解决同一集合下的数据包含多种不同的分布的情况.高斯混合模型使用了期望最大(Expectation Maximization, 简称EM)算法进行训练,故此我们在

随机推荐