新手初学Java常见排序算法

目录
  • 1、冒泡排序
  • 2、选择排序
  • 3、简单插入排序
  • 4、希尔排序
  • 5、归并排序
  • 6、快速排序
  • 总结

1、冒泡排序

排序原理:相邻两个元素比较,如果前者比后者大,则交换两个元素。每执行一次,都会确定一个最大值,其位置就固定了,下一次就不需要再参与排序了。

时间复杂度:O(n^2)

稳定性:稳定

具体实现:

public class Bubble {
    /**
     * 对数组a中的元素进行排序
     */
    public static void sort(Comparable[] 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);
                }
            }
        }*/
        for (int i=0; i<a.length-1; i++){
            for (int j=0; j<a.length-i-1; j++){
                if (greater(a[j],a[j+1])){
                    exch(a, j,j+1);
                }
            }
        }
    }
    /**
     * 比较u元素是否大于v元素
     */
    private static boolean greater(Comparable u, Comparable v){
        return u.compareTo(v) > 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;
    }
	/**
     * 测试
     */
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

优化:可以加一个标志位,当冒泡一次也没有执行的时候,就说明已经排好了,就不需要再冒泡了。

2、选择排序

排序原理:从数组中找出最小值的下标,然后将最小值交换到前边。每执行一次前边就会有一个最小值位置固定,之后就不再需要参与查找最小值了。

时间复杂度:O(n^2)

稳定性:不稳定

具体实现:

public class Selelction {
    /**
     * 将数组排序
     * @param a 待排序的数组
     */
    public static void sort(Comparable[] a){
        for (int i=0; i<a.length-1; i++){
            //找出最小的值
            int minIndex = i;
            //注意这里不需要减一
            for (int j=i+1; j<a.length; j++){
                //Comparable数组 不能直接用下标比较大小
                if (greater(a[minIndex],a[j])){
                    minIndex = j;
                }
            }
            //交换
            if (minIndex != i){
                exch(a, minIndex, i);
            }
        }
    }
    /**
     * 比较第一个参数是否大于第二个参数
     * @param a
     * @param b
     * @return 第一个参数是否大于第二个参数
     */
    private static boolean greater(Comparable a, Comparable b){
        return a.compareTo(b) > 0;
    }
    /**
     * 交换数组的两个元素
     * @param a 数组
     * @param i 数组下标
     * @param j 数组下标
     */
    private  static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    /**
     * 测试方法
     * @param args
     */
    public static void main(String[] args) {
        Integer[] array = {1,6,7,3,2,5,7,8,4,0,5,3,7};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

3、简单插入排序

排序原理:将数组分成两组,左边一组是已排序的,右边一组是未排序的,然后拿未排序的第一个与左边的从后往前比较,如果比前边的小就交换,直到前边的值比它小或者等于它。

时间复杂度:O(n^2)

稳定性:稳定

具体实现:

public class Insertion {
    /**
     * 对数组a中的元素进行排序
     */
    public static void sort(Comparable[] a){
        for (int i = 1; i < a.length; i++) {
            for (int j = i; j > 0; j--){
                if (greater(a[j-1],a[j])){
                    exch(a, j-1, j);
                }else {
                    break;
                }
            }
        }
    }
    /**
     * 比较u元素是否大于v元素
     */
    private static boolean greater(Comparable u, Comparable v){
        return u.compareTo(v) > 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;
    }
    /**
     * 测试
     */
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

优化思路:将要插入的数先保存起来,然后交换的代码就可以改成覆盖,就相当于后移,等找到合适位置再把之前保存的值放进去。

4、希尔排序

排序原理:是插入排序的优化版,插入排序在比较时只能一个一个比较,而希尔排序中加了一个增长量,可以跨元素比较,相对减少了比较交换的次数。

时间复杂度:O(n^1.3)

稳定性:不稳定

具体实现:

public class Shell {
    /**
     * 将数组排序
     * @param a 待排序的数组
     * @return 排好序的数组
     */
    public static void sort(Comparable[] a){
        //1.确定增长量h的值
        int h=1;
        while(h < a.length/2){
            h = h*2+1;
        }
        //2.进行排序
        while(h>=1){
            //找到待排序的第一个值
            for (int i=h; i<a.length; i++){
                for (int j=i; j>=h; j-=h){
                    if (greater(a[j-h],a[j])){
                        exch(a, j, j-h);
                    }else{
                        break;
                    }
                }
            }
            //h减小
            h/=2;
        }
    }
    /**
     * 比较u元素是否大于v元素
     */
    private static boolean greater(Comparable u, Comparable v){
        return u.compareTo(v) > 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;
    }
    //测试数据
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8, 6, 7};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

5、归并排序

排序原理:使用了递归的思想,先把数组从中间递归分解,接着先排序左边的子数组,然后再排序右边的子数组,最后合并为一个数组。核心方法是merge方法。

时间复杂度:O(nlogn)

稳定性:稳定

具体实现:

public class Merge {
    /**
     * 辅助数组
     */
    private static Comparable[] access;
    /**
     * 对数组a进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        //1.初始化辅助数组
        access = new Comparable[a.length];
        //2.定义两个下标值
        int lo = 0;
        int hi = a.length -1;
        //3.调用分组排序函数
        sort(a, lo, hi);
    }
    /**
     * 对数组a中的lo到hi进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi){
        //保护
        if (hi <= lo){
            return;
        }
        //1.得到mid
        int mid = lo + (hi-lo)/2;
        //2.对左数组分组排序
        sort(a, lo, mid);
        //3.对右数组分组排序
        sort(a, mid+1, hi);
        //4.将两个数组合并
        merge(a, lo, mid, hi);
    }
    /**
     * 将两个数组进行排序合并
     * @param a
     * @param lo
     * @param mid
     * @param hi
     */
    private static void merge(Comparable[] a, int lo, int mid, int hi){
        //1.定义三个指针
        int i=lo;
        int p1=lo;
        int p2=mid+1;
        //2.分别遍历两个子数组,直到有一个数组遍历完毕
        while (p1 <= mid && p2 <= hi){
            if (less(a[p1], a[p2])){
                access[i++] = a[p1++];
            }else{
                access[i++] = a[p2++];
            }
        }
        //3。将剩下的一个数组的剩余值放到辅助数组中
        while(p1 <= mid){
            access[i++] = a[p1++];
        }
        while(p2 <= hi){
            access[i++] = a[p2++];
        }
        //4。将辅助数组中的值覆盖到原数组中
        for (int index=lo; index<=hi; index++){
            a[index] = access[index];
        }
    }
    /**
     * 比较第一个下标的值是不是小于第二个下标的值
     * @param u
     * @param v
     * @return
     */
    private static boolean less(Comparable u, Comparable v){
        return u.compareTo(v) <= 0;
    }
    /**
     * 测试
     */
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

6、快速排序

排序原理:把数组的第一个值设置为中间值,比中间值小的放到左边,比中间值大的放到右边。然后再对左边的做相同的操作,最后是对右边的做相同的操作。核心方法是partition方法,将小的数移到左边,大的数移到右边,最后返回中间值的下标。

时间复杂度:O(nlogn)

稳定性:不稳定

具体实现:

public class Quick {
    /**
     * 对数组a进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        int lo = 0;
        int hi = a.length-1;
        sort(a, lo, hi);
    }
    /**
     * 对数组a中的lo到hi进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi){
        //保护
        if (hi <= lo){
            return;
        }
        //获取中间值
        int mid = partition(a, lo, hi);
        //对左子数组进行排序
        sort(a, lo, mid-1);
        //对右子数组进行排序
        sort(a, mid+1, hi);
    }

    /**
     * 将比子数组中第一个值小的数放到其左边,大于的放到右边,最后返回中间值的下标
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    private static int partition(Comparable[] a, int lo, int hi){
        //1.定义两个指针
        int p1= lo;
        int p2 = hi+1;
        while (true){
            //2.先移动右指针,找到第一个小于标准值的数
            while(less(a[lo],a[--p2])){
                if (p2 == lo){
                    break;
                }
            }
            //3.移动左指针,找到第一个大于标准值的数
            while(less(a[++p1],a[lo])){
                if (p1 == hi){
                    break;
                }
            }
            if (p1 >= p2){
                //5.退出循环
                break;
            }else {
                //4.交换两个值
                exch(a, p1, p2);
            }
        }
        //6.最后把子数组的第一个值和右指针所指的值交换,最后返回其下标
        exch(a, lo, p2);
        return p2;
    }
    /**
     * 比较第一个下标的值是不是小于第二个下标的值
     * @param u
     * @param v
     * @return
     */
    private static boolean less(Comparable u, Comparable v){
        return u.compareTo(v) < 0;
    }
    /**
     * 交换数组中两个下标的值
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    /**
     * 测试
     */
    public static void main(String[] args) {
        Integer[] a = {8, 5, 7, 4, 3, 2, 6, 8};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

总结

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

(0)

相关推荐

  • Java实现几种常见排序算法代码

    稳定度(稳定性)一个排序算法是稳定的,就是当有两个相等记录的关键字R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前. 排序算法分类 常见的有插入(插入排序/希尔排序).交换(冒泡排序/快速排序).选择(选择排序).合并(归并排序)等. 一.插入排序 插入排序(Insertion Sort),它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),

  • java排序算法图文详解

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

  • Java 7大常见排序方法实例详解

    直接插入排序 <code class="language-java hljs ">import java.util.HashMap; public class InsertSort { private static int contrastCount = 0;//对比次数 private static int swapCount = 0;//交换次数 public static void main(String[] args) { System.out.println(&q

  • 优化常见的java排序算法

    目录 冒泡排序 原始的写法 优化一 优化二 选择排序 方法一 方法二 堆排序 建大堆来实现堆排 建小堆来实现堆排 插入排序 实现 优化一 优化二 归并排序 递归实现归并排序 优化 来看O(n)的排序 当然除了基于比较的排序.还有基于非比较的排序. 总结 冒泡排序 冒泡排序的思想: 每次让当前的元素和它的下一个元素比较大小.如果前一个的元素大于后一个元素的话,交换两个元素. 这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素. 那么下次扫描的长度比上次少一个.因为数组的最后一个

  • Java实现常见排序算法的优化

    冒泡排序 冒泡排序的思想: 每次让当前的元素和它的下一个元素比较大小.如果前一个的元素大于后一个元素的话,交换两个元素. 这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素. 那么下次扫描的长度比上次少一个.因为数组的最后一个元素已经是最大的了.即最后一个元素已经有序了. 优化一: 优化的思路就是每一次扫描遍历一次数组.如果某次的扫描之后没有发生数组元素的交换的话.那么说明数组的元素已经是有序的了, 就可以直接跳出循环.没有继续扫描的必要了. 优化二:如果数组的尾部已经局部有

  • 新手初学Java常见排序算法

    目录 1.冒泡排序 2.选择排序 3.简单插入排序 4.希尔排序 5.归并排序 6.快速排序 总结 1.冒泡排序 排序原理:相邻两个元素比较,如果前者比后者大,则交换两个元素.每执行一次,都会确定一个最大值,其位置就固定了,下一次就不需要再参与排序了. 时间复杂度:O(n^2) 稳定性:稳定 具体实现: public class Bubble { /** * 对数组a中的元素进行排序 */ public static void sort(Comparable[] a){ //每冒泡一次,参与冒泡

  • Java 常见排序算法代码分享

    目录 1. 冒泡排序 2. 选择排序 3. 插入排序 4. 快速排序 5. 归并排序 6. 希尔排序 6.1 希尔-冒泡排序(慢) 6.2 希尔-插入排序(快) 7. 堆排序 8. 计数排序 9. 桶排序 10. 基数排序 11. 使用集合或 API 11.1 优先队列 11.2 Java API 汇总: 1. 冒泡排序 每轮循环确定最值: public void bubbleSort(int[] nums){     int temp;     boolean isSort = false;

  • Java数据结构之常见排序算法(上)

    目录 认识排序 常见排序的分类 直接插入排序 希尔排序(缩小增量排序) 选择排序 堆排序 认识排序 在学校中,如果我们要参加运动会,或者军训的时候,会按照身高从矮到高进行站队,比如上课老师手上拿的考勤表,通常是按照学号从低到高进行排序的.再比如编程语言排行榜,也是在排序. 生活中有相当多的排序场景,由此可知,排序还是很重要的, 本章就会介绍常见的一些排序算法. 所谓排序呢,就拿我们上面的举例来说,会按照某个或某些关键字的大小,递增或者递减排列起来的操作,这就是排序,这里面也涉及到排序的稳定性,举

  • C语言常见排序算法之交换排序(冒泡排序,快速排序)

    目录 前言 1.交换排序——冒泡排序 1.1 算法思想 1.2 动图演示 1.3 冒泡最好的情况 2. 交换排序——快速排序 2.1 快速排序——挖坑法 快排的缺点 三数取中法 2.3 快速排序——左右指针法 2.4 前后指针法 前言 本期为大家带来的是常见排序算法中的交换排序,主要有冒泡排序,快速排序,快排分享了三种算法:挖坑法,左右指针法,前后指针法,以及两种优化方式:解决快排最坏情况的“三数取中”,避免递归次数过多的"小区间优化", 基本思想:所谓交换,就是根据序列中两个记录键值

  • java数据结构排序算法之树形选择排序详解

    本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进

  • Java TreeMap排序算法实例

    本文实例讲述了Java TreeMap排序算法.分享给大家供大家参考,具体如下: TreeMap 和 HashMap 用法大致相同,但实际需求中,我们需要把一些数据进行排序: 以前在项目中,从数据库查询出来的数据放在List中,顺序都还是对的,但放在HashMap中,顺序就完全乱了. 为了处理排序的问题: 1. 对于一些简单的排序,如:数字,英文字母等 TreeMap hm = new TreeMap<String, String>(new Comparator() { public int

  • Java常用排序算法及性能测试集合

    现在再回过头理解,结合自己的体会, 选用最佳的方式描述这些算法,以方便理解它们的工作原理和程序设计技巧.本文适合做java面试准备的材料阅读. 先附上一个测试报告: Array length: 20000bubbleSort : 766 msbubbleSortAdvanced : 662 msbubbleSortAdvanced2 : 647 msselectSort : 252 msinsertSort : 218 msinsertSortAdvanced : 127 msinsertSor

  • Javascript中的常见排序算法

    具体代码及比较如下所示: 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">  <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

随机推荐