八大排序(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

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ

springboot security验证码的登录实例

《springbootsecurity验证码的登录实例》:本文主要介绍springbootsecurity验证码的登录实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录前言代码示例引入依赖定义验证码生成器定义获取验证码及认证接口测试获取验证码登录总结前言在spring

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s