苏州招聘网站建设,ui设计公司网站,做公众号好还是网站好,做课件可赚钱的网站#x1f31f; 前言 欢迎来到我的技术小宇宙#xff01;#x1f30c; 这里不仅是我记录技术点滴的后花园#xff0c;也是我分享学习心得和项目经验的乐园。#x1f4da; 无论你是技术小白还是资深大牛#xff0c;这里总有一些内容能触动你的好奇心。#x1f50d; #x… 前言 欢迎来到我的技术小宇宙 这里不仅是我记录技术点滴的后花园也是我分享学习心得和项目经验的乐园。 无论你是技术小白还是资深大牛这里总有一些内容能触动你的好奇心。 洛可可白个人主页 个人专栏✅前端技术 ✅后端技术 个人博客洛可可白博客 代码获取bestwishes0203 封面壁纸洛可可白wallpaper 文章目录 排序算法全景从基础到高级的Java实现插入排序理解排序的核心思想什么是插入排序插入排序的Java实现程序的执行插入排序的核心思想结语 希尔排序一种高效的改进版插入排序希尔排序简介Java实现希尔排序测试希尔排序希尔排序的核心思想结语 归并排序优雅的分而治之艺术归并排序的基本概念Java实现归并排序测试归并排序归并排序的核心思想结语 快速排序分而治之的高效排序算法快速排序的基本概念Java实现快速排序快速排序的核心思想快速排序的性能结语 选择排序简单而直观的排序算法入门选择排序的工作原理Java实现选择排序选择排序的特点结语 生成测试数据和输出测试数据的类 排序算法全景从基础到高级的Java实现
排序算法是计算机科学中的一个基础概念它在数据处理和信息检索中扮演着至关重要的角色。本文将通过几个简单的Java程序带你了解几种常见的排序算法插入排序、希尔排序、归并排序、快速排序和选择排序以及一个用于生成和打印测试数据的工具类。
插入排序理解排序的核心思想
什么是插入排序
插入排序Insertion Sort算法是一种直观且易于理解的排序方法。插入排序的工作原理类似于我们整理扑克牌的方式。想象一下你手中有一堆未排序的扑克牌你将它们一张张插入到已经排序好的牌堆中。插入排序算法正是基于这样的思想它将数组分为已排序和未排序两部分然后逐个将未排序部分的元素插入到已排序部分的适当位置。
插入排序的Java实现
让我们通过一个Java程序来具体看看插入排序是如何工作的。这个程序定义了一个名为 _01_InsertionSort 的类其中包含了排序方法和一些辅助函数。
public class _01_InsertionSort {public static void sort(Comparable[] arr) {int n arr.length;for (int i 0; i n; i) {// 寻找元素arr[i]合适的插入位置for (int j i; j 0; j--) {if (arr[j].compareTo(arr[j - 1]) 0) {swap(arr, j, j - 1);} else {break;}}}}private static void swap(Object[] arr, int i, int j) {Object t arr[i];arr[i] arr[j];arr[j] t;}
}在这个类中sort 方法接受一个可比较的对象数组 arr 作为参数。方法的核心是一个双重循环外层循环遍历数组的每个元素内层循环则负责将当前元素与已排序部分的元素进行比较并在必要时进行交换。
swap 方法是一个辅助函数用于交换数组中的两个元素。这是在内层循环中当我们发现需要将一个元素插入到它之前的位置时调用的。
程序的执行
程序的 main 方法首先生成了一个包含20000个随机整数的数组然后调用 sort 方法对数组进行排序最后打印出排序后的数组。
public static void main(String[] args) {int N 20000;Integer[] arr SortTestHelper.generateRandomArray(N, 0, 100000);_01_InsertionSort.sort(arr);for (int i 0; i arr.length; i) {System.out.print(arr[i]);System.out.print( );}
}插入排序的核心思想
插入排序的核心思想是分而治之。它将排序问题分解为更小的部分然后逐个解决。这种方法在数据量较小或者数据基本有序的情况下非常有效因为它可以减少不必要的比较和交换操作。
结语
通过这个简单的Java程序我们不仅学习了插入排序算法的实现还理解了排序算法的一般思想。虽然插入排序在处理大数据集时可能不是最高效的选择但它的简单性和直观性使其成为理解排序概念的一个良好起点。随着你对算法的深入学习你将能够掌握更多高级的排序技术以应对更复杂的数据处理挑战。
希尔排序一种高效的改进版插入排序
希尔排序Shell Sort是一种对传统插入排序的改进它通过引入间隔gap的概念来提高排序的效率。
希尔排序简介
希尔排序是由Donald Shell在1959年提出的一种排序算法。它基于插入排序通过将原始数据集分割成若干个子序列来排序这些子序列的元素间隔逐渐减小最后合并为一个有序的序列。
Java实现希尔排序
让我们通过一个简单的Java程序来实现希尔排序。
public class _02_ShellSort {public static void sort(Comparable[] arr) {// 初始化间隔int gap arr.length / 2;// 当间隔大于0时执行排序while (gap 0) {// 遍历数组间隔为gapfor (int i gap; i arr.length; i) {// 临时存储当前元素Comparable tmp arr[i];// 对于每个间隔内的元素进行插入排序for (int j i; j gap tmp.compareTo(arr[j - gap]) 0; j - gap) {// 将较大的元素向后移动arr[j] arr[j - gap];}// 将当前元素放到正确的位置arr[j] tmp;}// 缩小间隔进行下一轮排序gap / 2;}}
}在这个实现中我们首先计算一个初始间隔 gap然后通过一个循环来逐渐减小这个间隔。在每次循环中我们对间隔为 gap 的元素进行插入排序。随着间隔的减小排序的粒度逐渐变细最终整个数组变得有序。
测试希尔排序
为了测试我们的希尔排序算法我们在 main 方法中生成了一个包含2000个随机整数的数组并对其进行排序。
public static void main(String[] args) {int N 2000;Integer[] arr SortTestHelper.generateRandomArray(N, 0, 10);_02_ShellSort.sort(arr);// 打印排序后的数组for (int i 0; i arr.length; i) {System.out.print(arr[i]);System.out.print( );}
}希尔排序的核心思想
希尔排序的核心在于分而治之的策略。它不是一次性对整个数组进行排序而是先对数组的子序列进行排序然后逐步缩小子序列的范围直到整个数组有序。这种方法在处理部分有序的数据时特别有效因为它可以减少不必要的比较和交换操作。
结语
通过这个Java程序我们不仅学习了希尔排序的实现还理解了其背后的算法思想。希尔排序是一种简单且高效的排序方法它在某些情况下比传统的插入排序要快得多。
归并排序优雅的分而治之艺术
归并排序Merge Sort是一种优雅且高效的排序方法。归并排序通过分而治之的策略将数据集一分为二然后递归地对这两部分进行排序最后将它们合并成一个有序的整体。
归并排序的基本概念
归并排序的核心在于“分而治之”。这个策略涉及将一个大问题分解成小问题解决这些小问题然后将它们的解决方案合并。在排序的上下文中这意味着将一个未排序的数组分成两半分别对这两半进行排序然后将它们合并成一个有序数组。
Java实现归并排序
让我们通过一个Java程序来实现归并排序。
public class _03_MergeSort {// 将arr[l...mid]和arr[mid1...r]两部分进行归并private static void merge(Comparable[] arr, int l, int mid, int r) {Comparable[] aux Arrays.copyOfRange(arr, l, r 1);// 初始化i指向左半部分的起始索引位置lj指向右半部分起始索引位置mid1int i l, j mid 1;for (int k l; k r; k) {if (i mid) { // 如果左半部分元素已经全部处理完毕arr[k] aux[j - l];j;} else if (j r) { // 如果右半部分元素已经全部处理完毕arr[k] aux[i - l];i;} else if (aux[i - l].compareTo(aux[j - l]) 0) { // 左半部分所指元素 右半部分所指元素arr[k] aux[i - l];i;} else { // 左半部分所指元素 右半部分所指元素arr[k] aux[j - l];j;}}}// 递归使用归并排序,对arr[l...r]的范围进行排序private static void sort(Comparable[] arr, int l, int r) {if (l r) {return;}int mid (l r) / 2;sort(arr, l, mid);sort(arr, mid 1, r);// 对于arr[mid] arr[mid1]的情况,不进行merge// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失if (arr[mid].compareTo(arr[mid 1]) 0)merge(arr, l, mid, r);}public static void sort(Comparable[] arr) {int n arr.length;sort(arr, 0, n - 1);}
}在这个类中merge 方法负责合并两个已经排序的子数组。sort 方法是递归的核心它将数组分成两半然后递归地调用自身来排序这两半。最后sort 方法提供了一个公共接口来开始排序过程。
测试归并排序
为了测试归并排序的性能我们在 main 方法中生成了一个包含1000个随机整数的数组并对其进行排序。
public static void main(String[] args) {int N 1000;Integer[] arr SortTestHelper.generateRandomArray(N, 0, 100000);_03_MergeSort.sort(arr);SortTestHelper.printArray(arr);
}归并排序的核心思想
归并排序的核心在于递归和合并。递归地将数组分成更小的部分直到每个部分只有一个元素或没有元素这时数组自然是有序的。然后通过合并相邻的有序子数组逐步构建更大的有序数组最终得到完全有序的原始数组。
结语
归并排序是一种非常优雅的排序算法它不仅在理论上具有优雅的数学美感而且在实际应用中也非常高效。它的时间复杂度在最好、最坏和平均情况下都是O(n log n)这使得它在处理大型数据集时特别有用。尽管归并排序需要额外的存储空间来创建辅助数组但它的稳定性和效率使其成为许多排序场景下的首选算法。
快速排序分而治之的高效排序算法
快速排序Quick Sort是一种分而治之策略的高效排序方法。快速排序以其平均时间复杂度为O(n log n)而闻名它在大多数情况下都能提供出色的性能。
快速排序的基本概念
快速排序的核心在于“分而治之”。这个策略涉及将一个大问题分解成小问题解决这些小问题然后将它们的解决方案合并。在排序的上下文中这意味着将一个未排序的数组分成两半然后递归地对这两半进行排序最后将它们合并成一个有序的整体。
Java实现快速排序
让我们通过一个Java程序来实现快速排序。
public class _04_QuickSort {// 对arr[l...r]部分进行partition操作// 返回p, 使得arr[l...p-1] arr[p] ; arr[p1...r] arr[p]private static int partition(Comparable[] arr, int l, int r){// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivotswap( arr, l , (int)(Math.random()*(r-l1))l );Comparable v arr[l];// arr[l1...j] v ; arr[j1...i) vint j l;for( int i l 1 ; i r ; i )if( arr[i].compareTo(v) 0 ){j ;swap(arr, j, i);}swap(arr, l, j);return j;}// 递归使用快速排序,对arr[l...r]的范围进行排序private static void sort(Comparable[] arr, int l, int r){if (l r) {return;}int p partition(arr, l, r);sort(arr, l, p-1 );sort(arr, p1, r);}public static void sort(Comparable[] arr){int n arr.length;sort(arr, 0, n-1);}private static void swap(Object[] arr, int i, int j) {Object t arr[i];arr[i] arr[j];arr[j] t;}// 测试 QuickSortpublic static void main(String[] args) {// Quick Sort也是一个O(nlogn)复杂度的算法// 可以在1秒之内轻松处理100万数量级的数据int N 1000000;Integer[] arr SortTestHelper.generateRandomArray(N, 0, 100000);sort(arr);SortTestHelper.printArray(arr);}
}在这个类中partition 方法负责将数组分成两部分sort 方法是递归排序的核心它将数组分成两半然后递归地对这两半进行排序。swap 方法是一个辅助函数用于交换数组中的两个元素。
快速排序的核心思想
快速排序的核心在于选择一个基准值pivot然后将数组分成两部分一部分包含所有小于基准值的元素另一部分包含所有大于基准值的元素。这个过程称为分区partitioning。分区操作完成后基准值就处于其最终排序位置。然后我们递归地对基准值左边和右边的子数组进行同样的操作直到整个数组变得有序。
快速排序的性能
快速排序的平均时间复杂度为O(n log n)这使得它在处理大型数据集时非常高效。尽管在最坏情况下快速排序的时间复杂度会下降到O(n^2)但通过随机选择基准值可以大大降低这种最坏情况发生的概率。
结语
通过学习快速排序我们不仅掌握了一种高效的排序技术还理解了分而治之这一强大的问题解决策略。这种策略在计算机科学中有着广泛的应用不仅仅是在排序算法中。快速排序的优雅和效率使其成为了许多排序场景下的首选算法。
选择排序简单而直观的排序算法入门
选择排序Selection Sort算法是一种易于理解和实现的排序方法。选择排序的核心思想是在每一轮迭代中找到最小或最大的元素并将其移动到正确的位置。
选择排序的工作原理
选择排序算法的工作原理可以概括为以下几个步骤
假设第一个元素已经是排序好的。在剩余的未排序元素中找到最小或最大的元素。将找到的最小或最大元素与当前未排序的第一个元素交换位置。重复步骤2和3直到所有元素都被排序。
Java实现选择排序
下面是一个选择排序的Java实现示例
public class _07_SelectionSort {public static void sort(int[] arr) {int n arr.length;for (int i 0; i n; i) {// 初始化最小值索引为当前位置int minIndex i;// 寻找[i, n)区间里的最小值的索引for (int j i 1; j n; j) {if (arr[j] arr[minIndex]) {minIndex j;}}// 交换当前位置和找到的最小值位置的元素swap(arr, i, minIndex);}}private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int N 20000;Integer[] arr SortTestHelper.generateRandomArray(N, 0, 100000);_07_SelectionSort.sort(arr);for (int i 0; i arr.length; i) {System.out.print(arr[i]);System.out.print( );}}
}在这个实现中sort 方法负责执行排序过程。它首先遍历数组然后在每次迭代中找到最小值的索引并将其与当前位置的元素交换。swap 方法是一个辅助函数用于交换数组中的两个元素。
选择排序的特点
选择排序的主要特点是简单。它不需要额外的存储空间除了临时变量并且实现起来非常直观。然而选择排序的效率并不是最高的它的平均和最坏情况时间复杂度都是O(n^2)这使得它在处理大型数据集时效率较低。
结语
选择排序虽然在效率上可能不如其他更高级的排序算法但它的简单性和易于理解的特点使其成为初学者学习排序算法的良好起点。
生成测试数据和输出测试数据的类
//SortTestHelper
public class SortTestHelper {// SortTestHelper不允许产生任何实例private SortTestHelper(){}// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {assert rangeL rangeR;Integer[] arr new Integer[n];for (int i 0; i n; i)arr[i] new Integer((int)(Math.random() * (rangeR - rangeL 1) rangeL));return arr;}// 打印arr数组的所有内容public static void printArray(Object arr[]) {for (int i 0; i arr.length; i){System.out.print( arr[i] );System.out.print( );}System.out.println();return;}
}感谢你的访问期待与你在技术的道路上相遇
