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

缺乏、安全感 2023-07-03 10:51 21阅读 0赞

### 归并排序与基数排序 ###

*  归并排序
 *  基数排序
 *  常见排序算法的总结

# 归并排序 #

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

**基本思想**

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。**分阶段可以理解为就是递归拆分子序列的过程。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 1]

**归并排序实现代码**

*  时间复杂度 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,和快排速度差不多…

--------------------

2021.06.17 归并排序简化思路

1.  归并排序主要分为**合并方法** 和 **递归分解方法**
2.  **合并方法**  
    No.1 定义参数l,r,temp,t  
    No.2 把原来数组分成两个数组后, 依次进行比较, 将较小元素放入临时数组  
    No.3 将上一步仍有剩余的数组元素直接放入临时数组  
    No.4 将素组元素拷贝到原始数组
3.  **递归分解方法**  
    No.1 求出中间下标  
    No.2 在left<right的条件下, 根据中间下标分别向左向右递归分解  
    No.3 调用上面的合并方法

/** * 合并方法 * 1. 定义参数l,r,temp,t * 2. 把原来数组分成两个数组后, 依次进行比较, 将较小元素放入临时数组 * 3. 将上一步仍有剩余的数组元素直接放入临时数组 * 4. 将素组元素拷贝到原始数组 * @param arr 排序的原始数组 * @param left 左边有序序列的初始索引 * @param mid 中间索引 * @param right 右边索引 */
        public  static void merge3(int[] arr,int left,int right,int mid){ 
            //1. 定义参数l,r,temp,t
            int l=left;//左边第一个元素
            int r = mid+1;//右边第一个元素
            int[] temp = new int[arr.length];
            int t = 0;//临时数组下标
            //2. 把原来数组分成两个数组后, 依次进行比较, 将较小元素放入临时数组
            while (l<=mid && r<=right){ 
                if (arr[l]>=arr[r]){ 
                    temp[t] = arr[r];
                    r++;
                    t++;
                }else { 
                    temp[t] = arr[l];
                    l++;
                    t++;
                }
            }
            //3. 将上一步仍有剩余的数组元素直接放入临时数组
            while (l<=mid){ 
                temp[t] = arr[l];
                l++;
                t++;
            }
            while (r <= right) { 
                temp[t] = arr[r];
                r++;
                t++;
            }
            //4. 将素组元素拷贝到原始数组
            int T;//原始数组下标
            for (t=0, T=left;T<= right;t++,T++  ){ //一定不要缺等于号!!!
                arr[T] = temp[t];
            }
        }
    
        /** * 递归分解的方法 * 1. 求出中间下标 * 2. 在left<right的条件下, 根据中间下标分别向左向右递归分解 * 3. 调用上面的合并方法 */
        public static void mergeSort3(int[] arr, int left, int right) { 
            if (left < right) { 
                int mid = (left + right) / 2;
                //向左递归分解
                mergeSort3(arr,left,mid);
                //向右递归分解
                mergeSort3(arr, mid + 1, right);
                //合并
                merge3(arr,left,right,mid);
            }
    
        }
    
        public static void main(String[] args) { 
            int arr[] = {  8, 4, 5, 7, 1, 3, 6, 2 };
            mergeSort2(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }

--------------------

# 基数排序 #

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

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

第一轮排序: 比较个位数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 2]

第二轮排序: 比较十位数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 3]

第三轮排序: 比较百位数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 4]

**上图算法的代码模拟**

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

# 常见排序算法的总结 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020020521571797.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200205215825139.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200206164640344.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200206164816835.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200206164846935.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200206203008115.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxNTU2,size_16,color_FFFFFF,t_70