专栏首页Java探索之路[数据结构与算法] 排序算法之归并排序与基数排序

[数据结构与算法] 排序算法之归并排序与基数排序

归并排序与基数排序

归并排序

归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

基本思想

可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程。

合并相邻有序子序列: 再来看看治阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤

归并排序实现代码

  • 时间复杂度 O(nlogn)
    //分+合方法
	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if(left < right) {
			int mid = (left + right) / 2; //中间索引
			//向左递归进行分解
			mergeSort(arr, left, mid, temp);
			//向右递归进行分解
			mergeSort(arr, mid + 1, right, temp);
			//合并
			merge(arr, left, mid, right, temp);

		}
	}

	//合并的方法
	/**
	 *
	 * @param arr 排序的原始数组
	 * @param left 左边有序序列的初始索引
	 * @param mid 中间索引
	 * @param right 右边索引
	 * @param temp 做中转的数组
	 */
	public static void merge(int[] arr, int left, int mid, int right, int[] temp) {

		int i = left; // 初始化i, 左边有序序列的初始索引
		int j = mid + 1; //初始化j, 右边有序序列的初始索引
		int t = 0; // 指向temp数组的当前索引

		//(一)
		//先把左右两边(有序)的数据按照规则填充到temp数组
		//直到左右两边的有序序列,有一边处理完毕为止
		while (i <= mid && j <= right) {//继续
			//如果左边的有序序列的当前元素,小于等于右边有序序列的当前元素
			//即将左边的当前元素,填充到 temp数组 
			//然后 t++, i++
			if(arr[i] <= arr[j]) {
				temp[t] = arr[i];
				t += 1;
				i += 1;
			} else { //反之,将右边有序序列的当前元素,填充到temp数组
				temp[t] = arr[j];
				t += 1;
				j += 1;
			}
		}

		//(二)
		//把有剩余数据的一边的数据依次全部填充到temp
		while( i <= mid) { //左边的有序序列还有剩余的元素,就全部填充到temp
			temp[t] = arr[i];
			t += 1;
			i += 1;
		}

		while( j <= right) { //右边的有序序列还有剩余的元素,就全部填充到temp
			temp[t] = arr[j];
			t += 1;
			j += 1;
		}


		//(三)
		//将temp数组的元素拷贝到arr
		//注意,并不是每次都拷贝所有
		t = 0;
		int tempLeft = left; // 
		//第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
		//最后一次 tempLeft = 0  right = 7
		while(tempLeft <= right) {
			arr[tempLeft] = temp[t];
			t += 1;
			tempLeft += 1;
		}

	}

测试代码

public static void main(String[] args) {
		//int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 }; //

		//测试快排的执行速度
		// 创建要给80000个的随机的数组
		int[] arr = new int[8000000];
		for (int i = 0; i < 8000000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}
		System.out.println("排序前");
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是=" + date1Str);

		int temp[] = new int[arr.length]; //归并排序需要一个额外空间
		mergeSort(arr, 0, arr.length - 1, temp);

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的时间是=" + date2Str);

		//System.out.println("归并排序后=" + Arrays.toString(arr));
	}

通过测试可知, 对800w数据进行排序,用时约为2s,和快排速度差不多…

基数排序

  • 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用
  • 基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法
  • 基数排序(Radix Sort)是桶排序的扩展
  • 基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。
  • 将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

这样说明,比较难理解,下面我们看一个图文解释,理解基数排序的步骤(列如对三位数字进行排序)

第一轮排序: 比较个位数

第二轮排序: 比较十位数

第三轮排序: 比较百位数

上图算法的代码模拟

 public static void redixSort(int[] arr){
        // 第一轮排序,针对个位数进行排序

        //定义一个桶, 表示十个桶, 每个桶就是一个一位数组
        //注意:
        // 1.定义一个二维数据,包含10个数组,用来存储个位数为n的数据
        // 2.为了防止放入数据时数据溢出, 则定义每个桶的大小为arr.length
        // 3. 需要知道基数排序是经典的用时间换空间的算法
        int[][] bucket = new int[10][arr.length];

        // 定义一个数组来记录放入每个桶的元素的个数
        // 列如bucketElementCounts[0] 就是下标为0的桶(数组)中元素的个数
        int[] bucketElementCounts = new int[10];

        // 遍历数组, 将数组中的数字按照个位值放入对应的桶中
        for (int i=0;i<arr.length;i++){
            // 获取数字元素的个位数
            int digitElement = arr[i] % 10;
            // 放到每个桶,bucketElementCounts[digitElement]用来记录每个桶中元素的个数
            bucket[digitElement][bucketElementCounts[digitElement]] = arr[i];
            // 将对应的元素个数自增
            bucketElementCounts[digitElement]++;
        }

        // 定义一个辅助变量index, 用于存放第一次排序好的数字
        int index = 0;
        // 将桶中的元素放入到数组中
        for (int j=0;j<bucketElementCounts.length;j++){
           // 如果每个桶中的元素不为空bucketElementCounts[j]!=0,说明该位置有元素
            if (bucketElementCounts[j]!=0){
                // 循环到第k个桶, bucketElementCounts[k]代表第k个桶元素的个数
                for (int k=0;k<bucketElementCounts[j];k++){//bucketElementCounts[j]
                    // 将每个桶中元素按顺序重新放入数组arr
                    arr[index++] = bucket[j][k];
                }
            }
            // 在取出数据后, 将bucketElementCounts[j]置空,以便下次使用  重要!!!
            bucketElementCounts[j]=0;
        }
        System.out.println("第一轮排序结果"+Arrays.toString(arr));

        // --------------第二轮排序----------------------
        // 遍历数组, 将数组中的数字按照个位值放入对应的桶中
        for (int i=0;i<arr.length;i++){
            // 获取数字元素的个位数
            int digitElement = arr[i] /10% 10;
            // 放到每个桶,bucketElementCounts[digitElement]用来记录每个桶中元素的个数
            bucket[digitElement][bucketElementCounts[digitElement]] = arr[i];
            // 将对应的元素个数自增
            bucketElementCounts[digitElement]++;
        }

        // 定义一个辅助变量index, 用于存放第一次排序好的数字
        index = 0;
        // 将桶中的元素放入到数组中
        for (int j=0;j<bucketElementCounts.length;j++){
            // 如果每个桶中的元素不为空bucketElementCounts[j]!=0,说明该位置有元素
            if (bucketElementCounts[j]!=0){
                // 循环到第k个桶, bucketElementCounts[k]代表第k个桶元素的个数
                for (int k=0;k<bucketElementCounts[j];k++){//bucketElementCounts[j]
                    // 将每个桶中元素按顺序重新放入数组arr
                    arr[index++] = bucket[j][k];
                }
            }
            // 在取出数据后, 将bucketElementCounts[j]置空,以便下次使用  重要!!!
            bucketElementCounts[j]=0;
        }
        System.out.println("第二轮排序结果"+Arrays.toString(arr));

        //--------------------第三轮排序-----------------------
        for (int i=0;i<arr.length;i++){
            // 获取数字元素的个位数
            int digitElement = arr[i] /100 %10;
            // 放到每个桶,bucketElementCounts[digitElement]用来记录每个桶中元素的个数
            bucket[digitElement][bucketElementCounts[digitElement]] = arr[i];
            // 将对应的元素个数自增
            bucketElementCounts[digitElement]++;
        }

        // 定义一个辅助变量index, 用于存放第一次排序好的数字
        index = 0;
        // 将桶中的元素放入到数组中
        for (int j=0;j<bucketElementCounts.length;j++){
            // 如果每个桶中的元素不为空bucketElementCounts[j]!=0,说明该位置有元素
            if (bucketElementCounts[j]!=0){
                // 循环到第k个桶, bucketElementCounts[k]代表第k个桶元素的个数
                for (int k=0;k<bucketElementCounts[j];k++){//bucketElementCounts[j]
                    // 将每个桶中元素按顺序重新放入数组arr
                    arr[index++] = bucket[j][k];
                }
            }
            // 在取出数据后, 将bucketElementCounts[j]置空,以便下次使用  重要!!!
            bucketElementCounts[j]=0;
        }
        System.out.println("第三轮排序结果"+Arrays.toString(arr));

    }

基数排序算法的普适方法

  • 时间复杂度为 log以R为底B对数, B为真数0-9,R是基数个十百
 /**
     * 由三位数字推广到所有数字
     * @param arr
     */
    public static void redixSort2(int[] arr){
        //a. 根据上面的推导过程, 我们可以看到基数排序的代码
        // 得到数组中最大数的位数
        int max = arr[0];
        for (int i=0;i<arr.length;i++){
            if(arr[i]>max){
                max = arr[i];
            }
        }
        //选出最大数后,查看最大数是几位数
        int maxLength = (max + "").length();


        // 第一轮排序,针对个位数进行排序
        //定义一个桶, 表示十个桶, 每个桶就是一个一位数组
        //注意:
        // 1.定义一个二维数据,包含10个数组,用来存储个位数为n的数据
        // 2.为了防止放入数据时数据溢出, 则定义每个桶的大小为arr.length
        // 3. 需要知道基数排序是经典的用时间换空间的算法
        int[][] bucket = new int[10][arr.length];

        // 定义一个数组来记录放入每个桶的元素的个数
        // 列如bucketElementCounts[0] 就是下标为0的桶(数组)中元素的个数
        int[] bucketElementCounts = new int[10];

        // 根据循环得到的位数, 循环maxLength
        for (int m=0,n=1;m<maxLength;m++,n*=10){
            // 遍历数组, 将数组中的数字按照个位值放入对应的桶中
            for (int i=0;i<arr.length;i++){
                // 获取数字元素的对应位数的值
                int digitElement = arr[i] /n % 10;
                // 放到每个桶,bucketElementCounts[digitElement]用来记录每个桶中元素的个数
                bucket[digitElement][bucketElementCounts[digitElement]] = arr[i];
                // 将对应的元素个数自增
                bucketElementCounts[digitElement]++;
            }

            // 定义一个辅助变量index, 用于存放第一次排序好的数字
            int index = 0;
            // 将桶中的元素放入到数组中
            for (int j=0;j<bucketElementCounts.length;j++){
                // 如果每个桶中的元素不为空bucketElementCounts[j]!=0,说明该位置有元素
                if (bucketElementCounts[j]!=0){
                    // 循环到第k个桶, bucketElementCounts[k]代表第k个桶元素的个数
                    for (int k=0;k<bucketElementCounts[j];k++){//bucketElementCounts[j]
                        // 将每个桶中元素按顺序重新放入数组arr
                        arr[index++] = bucket[j][k];
                    }
                }
                // 在取出数据后, 将bucketElementCounts[j]置空,以便下次使用  重要!!!
                bucketElementCounts[j]=0;
            }
            System.out.println("第"+(m+1)+"轮排序结果"+Arrays.toString(arr));
        }

对基数排序代码的测试

  • 可以通过运行基数排序可知, 它的运算速度很快, 在运行800w条数据时, 非常的块, 速度为1s左右
  • 由于这种算法是典型的由空间换时间的算法, 在运行8000w条数据时, 需要11个数组, 每个int数字4字节, 因此需要 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G内存, 而如果电脑的内存不够是会出现OOM(内存溢出)问题
	public static void main(String[] args) {
		int arr[] = { 53, 3, 542, 748, 14, 214};
		
		// 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G 
//		int[] arr = new int[8000000];
//		for (int i = 0; i < 8000000; i++) {
//			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
//		}
		System.out.println("排序前");
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是=" + date1Str);
		
		radixSort2(arr);
		
		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的时间是=" + date2Str);
		
		System.out.println("基数排序后 " + Arrays.toString(arr));
		
	}

常见排序算法的总结

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [数据结构与算法] 排序算法之选择排序和堆排序

    选择排序(select sorting)也是一种简单的排序方法。它的基本思想是: 第一次从arr[0]~arr[n-1]中选取最小值,与arr[0]交换, ...

    时间静止不是简史
  • [数据结构与算法] 排序算法之直接插入排序与希尔排序

    插入排序(Insertion Sorting)的基本思想是: 把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含有n-...

    时间静止不是简史
  • [数据结构与算法] 查找算法

    类似的,每一子段也可以用相同的方式分割 但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]...

    时间静止不是简史
  • Java|实现冒泡排序

    冒泡排序是一种简单的常见的排序算法,算法重复的走访排序的数组,通过不断的两两比较,最终把最大数浮于上方,好比是可乐的气泡冒泡的过程,所以生动的称之为“冒泡排序”...

    算法与编程之美
  • 冒泡排序、选择排序、插入排序

    冒泡排序:每次遍历后选出最大的元素,每当选出一个下次遍历就排除之前已选的最大元素,因为每次遍历都能定位一个最大元素。

    用户6055494
  • 浙大版《C语言程序设计(第3版)》题目集 习题3-1 比较大小

    C you again 的博客
  • 常见排序算法及golang 实现

    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有...

    程序员养成日记
  • Js数组转字符串

    wePanda
  • [Go] Golang练习项目-快速排序的GO语言实现

    快速排序首先选一个基准(你也可以认为是要放到排序后数组正确位置的元素)pivot,然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有...

    陶士涵
  • Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋

扫码关注云+社区

领取腾讯云代金券