八大排序(Java实现)+ 桶排序

2024-05-27 03:04
文章标签 java 实现 排序 八大

本文主要是介绍八大排序(Java实现)+ 桶排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

准备工作

排序规则

按照自然序排序(从左往右,从小到大)

工具类

public class SortUtil {/*** 交换 arr[a] 与 arr[b]* @param arr 数组* @param a index a* @param b index b*/public static void swap(int[] arr, int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}
}

测试类

public class EightSortMethod {public static void main(String[] args) {int[] arr;// 1. 冒泡排序(Bubble Sort): 通过相邻元素的比较和交换来将较大的元素逐渐从后面移动到数组的末尾,较小的元素逐渐从前面移动到数组的开头。arr = new int[]{1, 5, 8, 2, 6, 0, 16, 88, 29, 91, 777};System.out.println(Arrays.toString(BubbleSort.sort(arr)));// 2. 选择排序(Selection Sort): 每次从未排序的部分选择最小(或最大)的元素,然后将其与未排序部分的第一个元素交换,直到所有元素排序完成。arr = new int[]{1, 5, 8, 2, 6, 0, 16, 88, 29, 91, 777};System.out.println(Arrays.toString(SelectionSort.sort(arr)));// 3. 插入排序(Insertion Sort): 将数组分成已排序和未排序两部分,每次从未排序部分取出一个元素插入到已排序部分的适当位置,直到所有元素都插入完毕。arr = new int[]{1, 5, 8, 2, 6, 0, 16, 88, 29, 91, 777};System.out.println(Arrays.toString(InsertionSort.sort(arr)));// 4. 希尔排序(Shell Sort): 是插入排序的一种改进版本,它通过将数组分成多个子序列来排序,每个子序列使用插入排序进行排序,不断缩小子序列的间隔直到为1。arr = new int[]{1, 5, 8, 2, 6, 0, 16, 88, 29, 91, 777};System.out.println(Arrays.toString(ShellSort.sort(arr)));// 5. 归并排序(Merge Sort): 采用分治法的思想,将数组递归地分成两个子数组,然后将两个有序子数组合并为一个有序数组,直到整个数组有序。arr = new int[]{1, 5, 8, 2, 6, 0, 16, 88, 29, 91, 777};System.out.println(Arrays.toString(MergeSort.sort(arr)));// 6. 快速排序(Quick Sort): 也是采用分治法的思想,通过选取一个基准元素,将数组分成两个子数组,左边的子数组小于等于基准元素,右边的子数组大于基准元素,然后递归地对两个子数组进行排序。arr = new int[]{1, 5, 8, 2, 6, 0, 16, 88, 29, 91, 777};System.out.println(Arrays.toString(QuickSort.sort(arr)));// 7. 堆排序(Heap Sort): 利用堆这种数据结构来实现的一种排序算法,通过构建最大堆(或最小堆)来实现排序。arr = new int[]{1, 5, 8, 2, 6, 0, 16, 88, 29, 91, 777};System.out.println(Arrays.toString(HeapSort.sort(arr)));// 8. 计数排序(Counting Sort): 非比较排序算法,适用于一定范围内的整数排序,它通过统计每个元素的个数来实现排序。arr = new int[]{1, 5, 8, 2, 6, 0, 16, 88, 29, 91, 777};System.out.println(Arrays.toString(CountingSort.sort(arr)));}
}

1. 冒泡排序(Bubble Sort)

通过相邻元素的比较和交换来将较大的元素逐渐从后面移动到数组的末尾,较小的元素逐渐从前面移动到数组的开头。

public class BubbleSort {public static int[] sort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {for (int j = 0; j < n - 1 - i; j++) {if (arr[j] > arr[j + 1]) SortUtil.swap(arr, j, j + 1);}}return arr;}
}

2. 选择排序(Selection Sort)

每次从未排序的部分选择最小(或最大)的元素,然后将其与未排序部分的第一个元素交换,直到所有元素排序完成。

public class SelectionSort {public static int[] sort(int[] arr) {int n = arr.length;for (int i = 0; i < n; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) minIndex = j;}SortUtil.swap(arr, i, minIndex);}return arr;}
}

3. 插入排序(Insertion Sort)

将数组分成已排序和未排序两部分,每次从未排序部分取出一个元素插入到已排序部分的适当位置,直到所有元素都插入完毕。

public class InsertionSort {public static int[] sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int x = arr[i];int end = i-1;while (end >= 0 && arr[end] > x) {arr[end + 1] = arr[end];end--;}arr[end+1] = x;}return arr;}
}

4. 希尔排序(Shell Sort)

是插入排序的一种改进版本,它通过将数组分成多个子序列来排序,每个子序列使用插入排序进行排序,不断缩小子序列的间隔直到为1。

public class ShellSort {public static int[] sort(int[] arr) {int n = arr.length;for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int x = arr[i];int end = i - gap;while (end >= 0 && arr[end] > x) {arr[end + gap] = arr[end];end -= gap;}arr[end + gap] = x;}}return arr;}
}

5. 归并排序(Merge Sort)

采用分治法的思想,将数组递归地分成两个子数组,然后将两个有序子数组合并为一个有序数组,直到整个数组有序。

public class MergeSort {public static int[] sort(int[] arr) {mergeSort(arr, 0, arr.length - 1);return arr;}private static void mergeSort(int[] arr, int l, int r) {if (l >= r) return;int m = l + (r - l) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);merge(arr, l, m, r);}private static void merge(int[] arr, int l, int m, int r) {int leftLen = m - l + 1;int rightLen = r - m;int[] left = new int[leftLen];int[] right = new int[rightLen];for (int i = 0; i < leftLen; i++) left[i] = arr[l + i];for (int i = 0; i < rightLen; i++) right[i] = arr[m + 1 + i];int lIndex = 0, rIndex = 0, mergeIndex = l;while (lIndex < leftLen && rIndex < rightLen) {arr[mergeIndex++] = left[lIndex] < right[rIndex] ? left[lIndex++] : right[rIndex++];}while (lIndex < leftLen) {arr[mergeIndex++] = left[lIndex++];}while (rIndex < rightLen) {arr[mergeIndex++] = right[rIndex++];}}
}

6. 快速排序(Quick Sort)

也是采用分治法的思想,通过选取一个基准元素,将数组分成两个子数组,左边的子数组小于等于基准元素,右边的子数组大于基准元素,然后递归地对两个子数组进行排序。

public class QuickSort {public static int[] sort(int[] arr) {quickSort(arr, 0, arr.length - 1);return arr;}private static void quickSort(int[] arr, int l, int r) {if (l >= r) return;int pivot = partition(arr, l, r);quickSort(arr, l, pivot - 1);quickSort(arr, pivot + 1, r);}private static int partition(int[] arr, int l, int r) {int pivot = l;while (l < r) {while (l < r && arr[r] >= arr[pivot]) r--;while (l < r && arr[l] <= arr[pivot]) l++;SortUtil.swap(arr, l, r);}SortUtil.swap(arr, l, pivot);return l;}
}

7. 堆排序(Heap Sort)

利用堆这种数据结构来实现的一种排序算法,通过构建最大堆(或最小堆)来实现排序。

public class HeapSort {public static int[] sort(int[] arr) {int n = arr.length;// 建立大根堆for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);// 删除法调整成小根堆for (int i = n - 1; i > 0; i--) {SortUtil.swap(arr, i, 0);// 注意第二个参数是 i 不是 nheapify(arr, i, 0);}return arr;}private static void heapify(int[] arr, int n, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] > arr[largest]) largest = left;if (right < n && arr[right] > arr[largest]) largest = right;if (largest != i) {SortUtil.swap(arr, i, largest);heapify(arr, n, largest);}}}

8. 计数排序(Counting Sort)

非比较排序算法,适用于一定范围内的整数排序,它通过统计每个元素的个数来实现排序。

public class CountingSort {public static int[] sort(int[] arr) {int max = Arrays.stream(arr).max().getAsInt();int min = Arrays.stream(arr).min().getAsInt();int range = max - min + 1;int[] count = new int[range];for (int i : arr) count[i - min]++;int j = 0;for (int i = 0; i < range; i++) {while (count[i]-- > 0) arr[j++] = i + min;}return arr;}
}

9. 桶排序(Bucket Sort)

计数排序的改进

public class BucketSort {public static int[] sort(int[] arr) {// Step 1: 确定桶的数量和范围int maxValue = Arrays.stream(arr).max().getAsInt();int minValue = Arrays.stream(arr).min().getAsInt();int range = (maxValue - minValue) / arr.length + 1; // 桶的范围int bucketSize = (maxValue - minValue) / range + 1; // 桶的数量// Step 2: 创建桶并分配元素List<List<Integer>> buckets = new ArrayList<>();for (int i = 0; i < bucketSize; i++) buckets.add(new ArrayList<>());for (int num : arr) {int bucketIndex = (num - minValue) / range;buckets.get(bucketIndex).add(num);}// Step 3: 对每个桶中的元素进行排序(这里使用了Java内置的排序方法)for (List<Integer> bucket : buckets) Collections.sort(bucket);// Step 4: 合并各个桶中的元素int index = 0;for (List<Integer> bucket : buckets) {for (int num : bucket) {arr[index++] = num;}}return arr;}
}

这篇关于八大排序(Java实现)+ 桶排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1006344

相关文章

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Spring 请求之传递 JSON 数据的操作方法

《Spring请求之传递JSON数据的操作方法》JSON就是一种数据格式,有自己的格式和语法,使用文本表示一个对象或数组的信息,因此JSON本质是字符串,主要负责在不同的语言中数据传递和交换,这... 目录jsON 概念JSON 语法JSON 的语法JSON 的两种结构JSON 字符串和 Java 对象互转