第八章 快速排序、归并排序和基数排序
文章目录
第八章 快速排序、归并排序和基数排序
一、快速排序
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