java 算法 6种排序小结

目录
  • 冒泡排序
  • 选择排序
  • 插入排序
  • 希尔排序
  • 归并排序
  • 快速排序

冒泡排序

package 冒泡排序;

import java.util.Arrays;

public class Bubble {

    /**
     * 对数组a中的元素进行排序
     * @param a
     */
    public static int[] sort(int[] a){
        for (int i=a.length-1;i>0;i--){
            for (int j=0;j<i;j++){
                if(greater(a[j],a[j+1])){
                    exch(a,j,j+1);
                }
            }
        }
        return a;
    }

    /**
     * 比较v元素是否大于w元素
     * @param v
     * @param w
     * @return
     */
    private static Boolean greater(int v,int w){
        if (v>=w){
            return true;
        }
        return false;
    }

    /**
     * 数据元素i和j交换位置
     * @param a
     * @param i
     * @param j
     */
    private static void exch(int[] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    public static void main(String[] args) {
        int[] a={4,5,6,3,2,1};
        int[] sort = Bubble.sort(a);
        System.out.println(Arrays.toString(sort));
    }
}

选择排序

package cn.itcast.algorithm.sort;

/**
 * 选择排序
 */
public class Selection {
    /*
       对数组a中的元素进行排序
    */
    public static void sort(Comparable[] a){
        for(int i=0;i<=a.length-2;i++){
            //定义一个变量,记录最小元素所在的索引,默认为参与选择排序的第一个元素所在的位置
            int minIndex = i;
            for(int j=i+1;j<a.length;j++){
                //需要比较最小索引minIndex处的值和j索引处的值;
                if (greater(a[minIndex],a[j])){
                    minIndex=j;
                }
            }

            //交换最小元素所在索引minIndex处的值和索引i处的值
            exch(a,i,minIndex);
        }
    }

    /*
        比较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 temp;
        temp = a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}

插入排序


package 插入排序;

import java.util.Arrays;

public class Insertion {

    public static void sort(int[] a){
        for (int i=1;i<a.length;i++){
            //当前元素为a[i],依次和i前面的元素比较,找到一个小于a[i]的元素
            for (int j=i;j>0;j--){
                if (greater(a[j-1],a[j])){
                    exch(a,j-1,j);
                }else {
                    break;
                }
            }
        }
    }

    /**
     * 比较v元素是否大于w元素
     * @param v
     * @param w
     * @return
     */
    private static Boolean greater(int v,int w){
        if (v>=w){
            return true;
        }
        return false;
    }

    /**
     * 数据元素i和j交换位置
     * @param a
     * @param i
     * @param j
     */
    private static void exch(int[] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    public static void main(String[] args) {
        int[] a={4,3,2,10,12,1,5,6};
        Insertion.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

希尔排序

package 希尔排序;

import java.util.Arrays;

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 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));
    }
}

归并排序


package 归并排序;

import java.util.Arrays;

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 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));

    }
}

快速排序



package 快速排序;

import java.util.Arrays;

public class Quick {
    public static void sort(Comparable[] a) {
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo, hi);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
//对a数组中,从lo到hi的元素进行切分
        int partition = partition(a, lo, hi);
//对左边分组中的元素进行排序
//对右边分组中的元素进行排序
        sort(a, lo, partition - 1);
        sort(a, partition + 1, hi);
    }

    public static int partition(Comparable[] a, int lo, int hi) {
        Comparable key = a[lo];//把最左边的元素当做基准值
        int left = lo;//定义一个左侧指针,初始指向最左边的元素
        int right = hi + 1;//定义一个右侧指针,初始指向左右侧的元素下一个位置
//进行切分
        while (true) {
//先从右往左扫描,找到一个比基准值小的元素
            while (less(key, a[--right])) {//循环停止,证明找到了一个比基准值小的元素
                if (right == lo) {
                    break;//已经扫描到最左边了,无需继续扫描
                }
            }
//再从左往右扫描,找一个比基准值大的元素
            while (less(a[++left], key)) {//循环停止,证明找到了一个比基准值大的元素
                if (left == hi) {
                    break;//已经扫描到了最右边了,无需继续扫描
                }
            }
            if (left >= right) {
//扫描完了所有元素,结束循环
                break;
            } else {
//交换left和right索引处的元素
                exch(a, left, right);
            }
        }
//交换最后rigth索引处和基准值所在的索引处的值
        exch(a, lo, right);
        return right;//right就是切分的界限
    }

    /*
    数组元素i和j交换位置
    */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /*
    比较v元素是否小于w元素
    */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    //测试代码
    public static void main(String[] args) throws Exception {
        Integer[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 8};
        Quick.sort(arr);
        System.out.println(Arrays.toString(arr));

    }
}

到此这篇关于java 算法 6种排序的文章就介绍到这了,更多相关java 算法排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java 排序算法之希尔算法

    目录 插入排序存在的问题 简单介绍 基本思想 代码实现 大数据量耗时测试 移动法实现希尔排序 移动法-大数据量耗时测试 算法分析 注:学习本篇的前提是要会插入排序,数据结构与算法--排序算法-插入排序 插入排序存在的问题 简单的插入排序可能存在的问题. 如数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小),过程是: 展示的是要移动 1 这个数,的过程,由于在最后,需要前面的所有数都往后移动一位 {2,3,4,5,6,6} {2,3,4,5,5,6} {2,3,4,4,5,

  • java 排序算法之快速排序

    目录 简单介绍 基本思想 思路分析 代码实现 推导实现 完整实现 大数据量耗时测试 性能分析 简单介绍 快速排序(Quicksort) 是对 冒泡排序的一种改进. 基本思想 快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值(基准值),通过该分界值将数组分成左右两部分. (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边.此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值. (3)然后,左边和右边的数据可以

  • java 排序算法之冒泡排序

    目录 基本介绍 图解冒泡排序算法的过程 代码实现 演变过程 优化 封装算法 大量数据耗时测试 基本介绍 冒泡排序(Bubble Sorting)(时间复杂度为 O(n²))的基本思想:通过对待排序序列 从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底下的旗袍一样逐渐向上冒. 优化点:因为排序过程中,个元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志判断元素是否进行过交换.从而减

  • java 排序算法之归并排序

    目录 简单介绍 基本思想 思路分析 代码实现 对代码的一些改进 大数据量耗时测试 复杂度 简单介绍 归并排序(merge sort)是利用 归并 的思想实现的排序方法,该算法采用经典的 分治(divide-and-conquer)策略 : 分(divide):将问题分成一些小的问题,然后递归求解 治(conquer):将分的阶段得到的各答案「修补」在一起 即:分而治之 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使

  • java 排序算法之选择排序

    目录 基本介绍 基本思想 思路分析 代码实现 演变过程 优化 算法函数封装 大量数据耗时测试 基本介绍 选择排序(select sorting)也属于内部排序法,是从欲排序的数据中,按指定的规则选出来某个元素,再依规定交换位置后达到排序的目的. 它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 基本思想 选择排序(select sorting)也是一种简单直

  • java 算法 6种排序小结

    目录 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 冒泡排序 package 冒泡排序; import java.util.Arrays; public class Bubble { /** * 对数组a中的元素进行排序 * @param a */ public static int[] sort(int[] a){ for (int i=a.length-1;i>0;i--){ for (int j=0;j<i;j++){ if(greater(a[j],a[j+1])){ e

  • Java实现8种排序算法的示例代码

    冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <

  • Java中七种排序算法总结分析

    目录 前言:对文章出现的一些名词进行解释 一.插入排序 1.基本思想 2.直接插入排序 3.希尔排序(缩小增量排序) 二.选择排序 1.基本思想 2.直接选择排序 3.堆排序 三.交换排序 1.基本思想 2.冒泡排序 3.快速排序(递归与非递归) 1.Hoare版 2.挖坑法 3.前后标记法(难理解) 4.快速排序优化 5.快速排序非递归 6.相关特性总结 四.归并排序(递归与非递归) 前言:对文章出现的一些名词进行解释 排序: 使一串记录,按照其中的某个或某些关键字的大小,递增或者递减排列起来

  • java 算法之希尔排序详解及实现代码

    java 算法之希尔排序 一.思想 希尔排序:使数组中任意间隔为h的元素都是有序的.在进行排序的时候,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便.用这种方式,对任意以1结尾的h序列,我们都能够将数据排序: 二.概念 h有序数组:任意间隔为h的元素都是有序的数组: 三.高效原因 对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一段:   希尔排序更高效的原因:它权衡了子数组的规模和有序性,在排序之初,各个子数组都很短:

  • java 中基本算法之希尔排序的实例详解

    java 中基本算法之希尔排序的实例详解 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法.该方法因DL.Shell于1959年提出而得名. 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差

  • Python数据结构与算法(几种排序)小结

    Python数据结构与算法(几种排序) 数据结构与算法(Python) 冒泡排序 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序算法的运作如下: 比较相邻的元素.如果第一个比第二个大(升序),就交换他们两个. 对每一对相邻元素作同样的工作,从

  • Java常用的八种排序算法与代码实现

    目录 1.直接插入排序 2.希尔排序 3.简单选择排序 4.堆排序 5.冒泡排序 6.快速排序 7.归并排序 8.基数排序 1.直接插入排序 经常碰到这样一类排序问题:把新的数据插入到已经排好的数据列中. 将第一个数和第二个数排序,然后构成一个有序序列 将第三个数插入进去,构成一个新的有序序列. 对第四个数.第五个数--直到最后一个数,重复第二步. 如何写写成代码: 首先设定插入次数,即循环次数,for(int i=1;i<length;i++),1个数的那次不用插入. 设定插入数和得到已经排好

  • Java实现4种微信抢红包算法(小结)

    目录 概述 一.剩余金额随机法 二.二倍均值法(微信红包采用此法) 三.整体随机法 四.割线法 概述 14年微信推出红包功能以后,很多公司开始上自己的红包功能,到现在为止仍然有很多红包开发的需求,实现抢红包算法也是面试常考题. 要求: 保证每个红包最少分得0.01元 保证每个红包金额概率尽量均衡 所有红包累计金额登于红包总金额 本文提供4中红包算法及Java代码实现demo,仅供参考.其中每种算法测试场景为:0.1元10个包,1元10个包,100元10个包,1000元10个包. 一.剩余金额随机

  • java中几种常见的排序算法总结

    目录 本节目标: [插入排序] [优化版] [希尔排序] [选择排序] [堆排序]  [冒泡排序] 介绍一个冒泡排序的优化方法:  [快速排序] [归并排序] [正文] [代码简介:]  [排序总结] 本节目标: :分析常见的比较排序算法基本原理及实现 :分析排序算法的性能分析 :分析Java中常用排序方法 1 排序 排序,就是使一串记录,按照其中某个或某些关键字的大小,递增或递减排列的操作. 平时的上下文中,提到排序 通常指排升序. 2 稳定性 两个相同的数据,如果经过排序后,排序算法能保证其

  • Java常用的八种排序算法及代码实现+图解

    目录 1.冒泡排序 冒泡排序法的思路 2.冒泡排序法的代码实现 3.冒泡排序法优化 4.选择排序 5.插入排序 插入排序的思路 经典的排序算法有八种,分别为: 冒泡排序 选择排序 插入排序 归并排序 希尔排序 快速排序 堆排序 基数排序 其中冒泡排序.选择排序.插入排序称为三大基本排序. 虽然这三大基本排序算法时间复杂度都是O(n2),但是其实细细讨论之下,还是有各自的特点的. 1.冒泡排序 冒泡排序法的思路 基本思路: 假设我们需要进行升序排列 进行N轮的比较,每一轮将相邻的两个元素依次比较,

随机推荐