插入、希尔、归并、快速排序(java实现)

这篇具有很好参考价值的文章主要介绍了插入、希尔、归并、快速排序(java实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

插入排序

希尔排序

归并排序

快速排序


插入排序

排序原理:

1.把所有元素分为两组,第一组是有序已经排好的,第二组是乱序未排序。

2.将未排序一组的第一个元素作为插入元素,倒序与有序组比较。

3.在有序组中找到比插入元素小或者大的元素,将插入元素放入该位置,后面元素向后移动一位。

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

稳定性:当A与B相等,排序前A若在B前,排序后A仍然在B前,就说明该排序是稳定的。

插入排序:稳定

插入、希尔、归并、快速排序(java实现),数据结构,数据结构,排序算法,算法

//比较两元素大小方法
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
 //数组中 交换元素位置
    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 insertSort(Comparable[] a){
        for (int i = 1; i < a.length-1; i++) {
            for (int j = i+1; j >0; j--) {
                if (greater(a[j-1],a[j])){
                    exch(a,j-1,j);
                }else break;
            }
        }
    }

希尔排序

排序原理:

1.选择一个增长量h,按照h将数据分组。

2.每组进行插入排序。

3.减少增长量h直到h=1,重复步骤2

稳定性:不稳定

插入、希尔、归并、快速排序(java实现),数据结构,数据结构,排序算法,算法

     public static void shellSort(Comparable[] a){
        int h = 1;
        //确定h
        while (h<a.length/2){
            h = 2*h+1;
        }
        // 希尔排序
        while (h>=1){
            for (int i = h; i < a.length; i=i+h) {
                for (int j = i; j >= h; j=j-h) {
                    if (greater(a[j-h],a[j])){
                        exch(a,j-h,j);
                    }else break;
                }
            }
            h=h/2;
        }
    }

归并排序

排序原理:

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

组的元素个数是1为止。

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

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

时间复杂度:O(nlogn)

稳定性: 稳定

插入、希尔、归并、快速排序(java实现),数据结构,数据结构,排序算法,算法

import java.util.Arrays;

public class Merge {
    //归并需要的辅助数组
    private static Comparable[] assist;

    //判断v是否比w小
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    //交换元素
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    //对数组a排序
    public static void sort(Comparable[] a){
        //    1.初始化辅助数组assist
        assist= new Comparable[a.length];
        //    定义lo变量和hi变量。分别记录数组中最小的索引和最大的索引
        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;
        }
    //  对lo和hi之间的数据进行分为两组
        int mid = lo+(hi-lo)/2;
    //    分别排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);
    //两组归并
        merge(a,lo,mid,hi);
    }

    //归并
    private static void merge(Comparable[] a,int lo,int mid,int hi){
    //    定义三个指针
        int i = lo;
        int p1 = lo;
        int p2 = mid+1;
    //    遍历移动p1指针和p2指针,比较对应 索引处的值,找出小的,放到辅助数组对应分索引处
       while (p1<=mid&&p2<=hi){
           if (less(a[p1],a[p2])){
               assist[i++] = a[p1++];
           }else {
               assist[i++] = a[p2++];
           }
       }
    //遍历,如果p1的指针没有走完,将p1剩余遍历到辅助数组中
        while (p1<=mid){
            assist[i++] = a[p1++];
        }
    //遍历,如果p2的指针没有走完,将p2剩余遍历到辅助数组中
        while (p2<=hi){
            assist[i++] = a[p2++];
        }
    //    把辅助数组中的元素复制到原数组中
        for (int index = lo;index<=hi;index++){
            a[index] = assist[index];
        }
    }

    public static void main(String[] args) {
        Integer[] a={7,8,4,5,6,1,3,9,2};
        Merge.sort(a);
        System.out.println(Arrays.toString(a));
    //    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

}

快速排序

排序原理:
1.首先设定一个分界值,通过该分界值将数组分成左右两部分;

2.将大于或等于分界值的数据放到到数组右边,小于分界值的数据放到数组的左边。此时左边部分

中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值;

3.然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分

数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处

理。
4.重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧

部分的顺序。当左侧和右侧两个部分的数据排完序后,整个数组的排序也就完成了。 

时间复杂度:

平均情况:O(nlogn),最坏情况:O(n^2) 

稳定性:不稳定 

插入、希尔、归并、快速排序(java实现),数据结构,数据结构,排序算法,算法文章来源地址https://www.toymoban.com/news/detail-644583.html

import java.util.Arrays;

public class Quick {
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    //对数组内的元素进行排序
    public static void sort(Comparable[] a){
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }
    //对数组a中从索引hi之间的元素进行排序
    public static void sort(Comparable[] a,int lo,int hi){
        if (lo>=hi)return;
        int partition = partition(a,lo,hi);
        sort(a,lo,partition-1);
        sort(a,partition+1,hi);
    }

    private static int partition(Comparable[] a,int lo,int hi){
        //确定分界值
        Comparable key = a[lo];
        //定义两个指针,分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left = lo;
        int right = hi+1;
        //切分 扫描
        while (true){
            //先从右边向左扫描,移动right指针,找到比分界值小的,停止
            while (less(key,a[--right])){
                if (right==lo){
                    break;
                }
            }
            //从左边向右扫描,移动light指针,找到比分界值大的,停止
            while (less(a[++left],key)){
                if (left==hi){
                    break;
                }
            }
            //right<right时交换
            if (left>=right){
                break;
            }else {
                exch(a,left,right);
            }
        }
        //交换分界值
        exch(a,lo,right);
        return right;
    }

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

}

到了这里,关于插入、希尔、归并、快速排序(java实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包