【Java数据结构与算法】第八章 快速排序、归并排序和基数排序

第八章 快速排序、归并排序和基数排序
文章目录
第八章 快速排序、归并排序和基数排序
一、快速排序
1.基本介绍
2.代码实现
二、归并排序
1.基本介绍
2.代码实现
三、基数排序
1.基本介绍
2.代码实现
一、快速排序
1.基本介绍
快速排序（Quick Sort）是在冒泡排序基础上的递归分治法，其基本原理：选择一个关键值作为基准值。比基准值小的都在左边序列， 比基准值大的都在右边

当一个等于基准元素的元素在基准元素的右边时，由于小于等于基准元素的元素都要移动到基准元素左边，所以该元素和基准元素的相对位置就改变了，因此快速排序是一种不稳定的排序算法

算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

2.代码实现
package com.sisyphus.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**

• @Description: 快速排序$

• @Param: $

• @return: $

• @Author: Sisyphus

• @Date: 7/17$
  */
  public class QuickSort {
  public static void main(String[] args) {
  //int[] arr = {-9, 78, 0, 23, -567, 70, -1, 900, 4561};
  //quickSort(arr,0,arr.length -1);
  //System.out.println(Arrays.toString(arr));

   //创建一个 80000 个随机数的数组
   int[] arr = new int[80000];
   for (int i = 0; i < 80000; i++) {
       arr[i] = (int)(Math.random() * 8000000);//生成一个 [0,8000000] 的随机数
   }
  
   Date date1 = new Date();
   SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
   String data1Str = simpleDateFormat.format(date1);
   System.out.println("排序前的时间是：" + data1Str);
  
   quickSort(arr,0,arr.length - 1);
  
   Date date2 = new Date();
   String data2Str = simpleDateFormat.format(date2);
   System.out.println("排序后的时间是：" + data2Str);
  

  }

  /**
  *

  • @param arr 待处理的数组

  • @param left 最左边的下标

  • @param right 最右边的下标
    */
    public static void quickSort(int[] arr,int left, int right){
    int l =left;
    int r = right;
    int pivot = arr[(left + right) / 2];
    int temp = 0;//用于交换
    //while 循环的目的是让比 pivot 小的值放到左边，比 pivot 大的值放到右边
    while(l < r){
    //在 pivot 左边一直找，找到一个大于等于 pivot 的值才退出
    while (arr[l] < pivot){
    l += 1;
    }
    //在 pivot 右边一直找，找到一个小于等于 pivot 的值才退出
    while(arr[r] > pivot){
    r -= 1;
    }
    //如果 l >= r 说明 pivot 左右两边的值已经按照左边全是小于等于 pivot，右边全是大于等于 pivot 的规定排列好了
    if(l >= r){
    break;
    }
    //交换
    temp = arr[l];
    arr[l] = arr[r];
    arr[r] = temp;

     //如果交换完后，发现 arr[l] == pivot
     if (arr[l] == pivot){
         r -= 1;
     }
     //如果交换完后，发现 arr[r] == pivot
     if (arr[r] == pivot){
         l += 1;
     }
    

    }

    //如果 l == r,必须 l++,r–，否则会出现栈溢出
    if (l == r){
    l++;
    r–;
    }
    //向左递归
    if (left < r){
    quickSort(arr,left,r);
    }

    //向右递归
    if (right > l){
    quickSort(arr,l,right);
    }
    }
    }

二、归并排序
1.基本介绍
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序

在交换过程中，2 个元素如果大小相等也没有任何操作交换，这不会破坏稳定性。合并过程中我们可以令相同的元素本来在前的还保持在前，这样就保证了相对顺序没有改变，因此归并排序也是稳定的排序算法

算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤 3 直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

2.代码实现
package com.sisyphus.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**

• @Description: 归并排序$

• @Param: $

• @return: $

• @Author: Sisyphus

• @Date: 7/17$
  */
  public class MergeSort {
  public static void main(String[] args) {
  //int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
  //System.out.println(“归并排序后” + Arrays.toString(arr));

   //创建一个 80000 个随机数的数组
   int[] arr = new int[80000];
   for (int i = 0; i < 80000; i++) {
       arr[i] = (int)(Math.random() * 8000000);//生成一个 [0,8000000] 的随机数
   }
  
   Date date1 = new Date();
   SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
   String data1Str = simpleDateFormat.format(date1);
   System.out.println("排序前的时间是：" + data1Str);
  
   int temp[] = new int[arr.length];//归并排序需要一个额外空间
   mergeSort(arr, 0, arr.length - 1, temp);
  
   Date date2 = new Date();
   String data2Str = simpleDateFormat.format(date2);
   System.out.println("排序后的时间是：" + data2Str);
  

  }

  //分 + 合的方法
  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++;
    i++;
    }else{//反之，将右边的当前元素拷贝到 temp 数组
    temp[t] = arr[j];
    t++;
    j++;
    }
    }

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

    //（三）
    //将 temp 数组的元素拷贝到 arr
    //注意：并不是每次都拷贝所有数据
    t = 0;
    int tempLeft = left;//
    //第一次合并时 tempLeft = 0，right = 1 第二次合并时 tempLeft = 2，right = 3 第三次合并时 tempLeft = 0，right = 3
    //最后一次 tempLeft = 0，right = 7
    //System.out.println(“tempLeft=”+tempLeft+" right="+right);
    while(tempLeft <= right){
    arr[tempLeft] = temp[t];
    t++;
    tempLeft++;
    }
    }
    }

三、基数排序
1.基本介绍
基数排序（Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数

基数排序基于分别排序，分别收集，因此是稳定的排序算法

算法步骤

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
从最低位开始，依次进行一次排序
从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
计数排序、桶排序和基数排序都利用了桶的概念，但对桶的使用方法上有明显差异：

桶排序：每个桶存储一定范围的数值
计数排序：每个桶只存储单一键值
基数排序：根据键值的每位数字来分配桶

2.代码实现
package com.sisyphus.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**

• @Description: 基数排序$

• @Param: $

• @return: $

• @Author: Sisyphus

• @Date: 7/17$
  */
  public class RadixSort {
  public static void main(String[] args) {
  //int[] arr = {53, 3, 542, 748, 14, 214};

   //创建一个 80000 个随机数的数组
   int[] arr = new int[80000];
   for (int i = 0; i < 80000; i++) {
       arr[i] = (int)(Math.random() * 8000000);//生成一个 [0,8000000] 的随机数
   }
  
   Date date1 = new Date();
   SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
   String data1Str = simpleDateFormat.format(date1);
   System.out.println("排序前的时间是：" + data1Str);
  
   radixSort(arr);
  
   Date date2 = new Date();
   String data2Str = simpleDateFormat.format(date2);
   System.out.println("排序后的时间是：" + data2Str);
  

  }

  public static void radixSort(int[] arr){

   //1.得到数组中最大的位数
   int max = arr[0];//假设第一个数就是最大数
   for (int i = 1; i < arr.length; i++) {
       if (arr[i] > max){
           max = arr[i];
       }
   }
   //得到最大数是几位数
   int maxLength = (max + "").length();
  
   //定义一个二维数组，表示 10 个桶，每个桶就是一个一维数组
   //说明
   //1.二维数组包含 10 个一维数组
   //2.为了防止在放入数据的时候溢出，设置每个一维数组的大小为 arr.length
   //3.由此可见，基数排序是一种以空间换时间的算法
   int[][] bucket = new int[10][arr.length];
  
   //为了记录每个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
   //可以这样理解
   //比如：bucketElementCounts[0]，记录的就是 bucket[0] 桶的放入数据的个数
   int[] bucketElementCounts = new int[10];
  
   for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
       //针对每个元素的对应位进行排序处理（第一次是个位，第二次是十位……）
       for (int j = 0; j < arr.length; j++) {
           //取出每个元素的个位的值
           int digitOfElement = arr[j] / n % 10;
           //放入到对应的桶中
           bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
           bucketElementCounts[digitOfElement]++;
       }
       //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来的数组）
       int index = 0;
       //遍历每一个桶，并将桶中的数据放入到原数组
       for (int k = 0; k < bucketElementCounts.length; k++) {
           //只有桶中有数据时，我们才放入到原数组
           if (bucketElementCounts[k] != 0){
               //循环该桶即第 k 个桶（即第 k 个一维数组），放入
               for (int l = 0; l < bucketElementCounts[k]; l++) {
                   //取出元素放入到 arr
                   arr[index++] = bucket[k][l];
               }
           }
           //第 i+1 轮处理后，需要将每个 bucketElementCounts[k] 置零
           bucketElementCounts[k] = 0;
       }
       //System.out.println("第" + (i+1) + "轮");
       //System.out.println(Arrays.toString(arr));
   }
  

  }
  }

————————————————
版权声明：本文为CSDN博主「313YPHU3」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_45593575/article/details/118880356