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

本文主要是介绍【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

这篇关于【Java数据结构与算法】第八章快速排序、归并排序和基数排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

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

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯

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

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯

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