必须掌握的八种排序(7-8)--归并排序,基数排序

7、归并排序

(1)基本排序:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

(2)理解图: 盗张图,这张图很好理解递归分解

下面的图理解合并

(3)、实现代码

import java.util.Arrays;
/**
 * 归并排序是建立在归并操作上的一种有效的排序算法。
 * 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
 * 归并排序是一种稳定的排
 * 步骤:
    1、Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。
    2、Conquer: 对这两个子序列分别采用归并排序。
    3、Combine: 将两个排序好的子序列合并成一个最终的排序序列。
 * @author Administrator
 *
 */
public class mergineSort {
    int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25,
            53, 51 };

    public mergineSort() {
        sort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++)
            System.out.println(a[i]);
    }
    /**
     * 
     * @param data 待排序数组
     * @param left 数组起始位置
     * @param right 数组结束位置
     */
    public void sort(int[] data, int left, int right) {
        if (left < right) {//表明可以继续拆分
            // 找出中间索引
            int center = (left + right) / 2;
            // 对左边数组进行递归
            sort(data, left, center);
            // 对右边数组进行递归
            sort(data, center + 1, right);
            // 合并
            merge(data, left, center, right);

        }
    }
    /**
     * 
     * @param data排序完的原数组
     * @param left 起始位置
     * @param center 中间位置
     * @param right  结束位置
     */
    public void merge(int[] data, int left, int center, int right) {
        int[] tmpArr = new int[data.length];//中间临时数组
        int mid = center + 1;
        // temp记录中间数组的索引 -->就是合并这两个数组的大数组的索引
        int temp = left;
        while (left <= center && mid <= right) {
            // 从两个数组中取出最小的放入中间数组
            if (data[left] <= data[mid]) {
                tmpArr[temp] = data[left];
                left++;
                temp++;
            } else {
                tmpArr[temp] = data[mid];
                mid++;
                temp++;
            }
        }
        // 剩余部分依次放入中间数组(见上面的合并图解)
        while (mid <= right) {
            tmpArr[temp] = data[mid];
            mid++;
            temp++;

        }
        while (left <= center) {
            tmpArr[temp] = data[left];
            left++;
            temp++;
        }
        // 将中间数组中的内容复制回原数组
        for(int i=0;i<=right;i++){
            data[i]=tmpArr[i];
        }

    }

}

8、基数排序

(1)基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

(2)理解图

(3)实现代码

/**
 * 基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。
 * 由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,
 * 所以基数排序也不是只能使用于整数。
 * 步驟:
 *   1、将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。
     2、从最低位开始,依次进行一次排序。
     3、这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
 * @author Administrator
 *
 */
public class RadixSort {

    public static int[] radixSortAsc(int[] arr) {
        // 从低位往高位循环
        for (int d = 1; d <= getMax(arr); d++) {
            // 临时数组,用来存放排序过程中的数据
            int[] tmpArray = new int[arr.length];
            // 位记数器,从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个...是9的有多少个数
            int[] count = new int[10];
            // 开始统计0有多少个,并存储在第0位,再统计1有多少个,并存储在第1位..依次统计到9有多少个
            // { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 10 };
            for (int i = 0; i < arr.length; i++) {
                count[digit(arr[i], d)] += 1;// 统计该位上有多少个数字 比如第一位上0有多少个
            }
            /*
             * 比如某次经过上面统计后结果为:[0, 2, 3, 3, 0, 0, 0, 0, 0, 0]则经过下面计算后 结果为: [0, 2,
             * 5, 8, 8, 8, 8, 8, 8, 8]但实质上只有如下[0, 2, 5, 8, 0, 0, 0, 0, 0, 0]中
             * 非零数才用到,因为其他位不存在,它们分别表示如下:2表示比较位为1的元素可以存放在索引为1、0的
             * 位置,5表示比较位为2的元素可以存放在4、3、2三个(5-2=3)位置,8表示比较位为3的元素可以存放在
             * 7、6、5三个(8-5=3)位置
             */
            for (int i = 1; i < 10; i++) {
                count[i] += count[i - 1];
            }

            /*
             * 注,这里只能从数组后往前循环,因为排序时还需保持以前的已排序好的 顺序,不应该打
             * 乱原来已排好的序,如果从前往后处理,则会把原来在前面会摆到后面去,因为在处理某个
             * 元素的位置时,位记数器是从大到到小(count[digit(arr[i], d)]--)的方式来处
             * 理的,即先存放索引大的元素,再存放索引小的元素,所以需从最后一个元素开始处理。
             * 如有这样的一个序列[212,213,312],如果按照从第一个元素开始循环的话,经过第一轮
             * 后(个位)排序后,得到这样一个序列[312,212,213],第一次好像没什么问题,但问题会
             * 从第二轮开始出现,第二轮排序后,会得到[213,212,312],这样个位为3的元素本应该
             * 放在最后,但经过第二轮后却排在了前面了,所以出现了问题
             */
            for (int i = arr.length - 1; i >= 0; i--) {// 只能从最后一个元素往前处理
                // for (int i = 0; i < arr.length; i++) {//不能从第一个元素开始循环
                tmpArray[count[digit(arr[i], d)] - 1] = arr[i];
                count[digit(arr[i], d)]--;
            }
            //System.arraycopy(tmpArray, 0, arr, 0, tmpArray.length);
            for(int i=0;i<arr.length;i++){
                arr[i]=tmpArray[i];
            }
        }
        return arr;
    }
    //求出最大数的位数的函数
    public static int getMax(int[] array) {
        // 取出最大数然后求出最大的位数
        int max = array[0];
        for (int j = 1; j < array.length; j++) {
            if (array[j] > max) {
                max = array[j];
            }
        }
        int time = 0;
        // 判断位数;
        while (max > 0) {
            max /= 10;
            time++;
        }
        return time;
        // return String.valueOf(max).length();也可以根据字符串长度返回
    }

    /**
     * 取数xxx上的第d位数字
     * 
     * @param x
     *            数字
     * @param d
     *            第几位,从低位到高位
     * @return
     */
    public static int digit(int num, int d) {

        int pow = 1;
        while (--d > 0) {
            pow *= 10;
        }
        return num / pow % 10;
    }

    public static void main(String[] args) {
        int[] data = { 73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 10 };

        System.out.println(radixSortAsc(data));
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-8-字符串转整数 (atoi)

在找到第一个非空字符之前,需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号,选取该符号,并将其与后面尽可能多的连续的数字组合起来,这部分字符即为整数...

9920
来自专栏塔奇克马敲代码

第3章 字符串、向量和数组

19960
来自专栏Python爱好者

Java基础笔记05

17180
来自专栏Python数据科学

十大经典排序算法(Python代码实现)

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

33110
来自专栏目标检测和深度学习

常用排序算法总结(2)

14140
来自专栏noteless

[八]基础数据类型之Double详解

这些属性,看过浮点数简介的话,可以很清晰的理解,再次说明下,但凡本人的系列文章,全部都是有顺序的

1.1K10
来自专栏灯塔大数据

码农必看:8大排序算法图文详解

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 ...

45690
来自专栏Jack的Android之旅

疯狂java笔记之常用的内部排序

在计算机程序开发过程中,经常需要一组数据元素(或记录)按某个关键字进行排序,排序完成的序列可用于快速查找相关记录。

7310
来自专栏北京马哥教育

8大排序算法图文讲解

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 ...

63170
来自专栏老九学堂

嘀 , 嘀嘀 ... 常用排序算法再总结

  这篇文章中再和小伙伴们来探讨一下常用的非比较排序算法:计数排序,基数排序,桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。

13230

扫码关注云+社区

领取腾讯云代金券