翠峦网站建设,页面设计感想,自己做网站给自己淘宝引流,泰安手机网站建设报价数据排序 一#xff1a;故事背景二#xff1a;直接插入排序2.1 概念2.2 画图表示2.3 代码实现2.4 总结提升 三#xff1a;希尔排序3.1 概念3.2 画图表示3.3 代码实现3.4 总结提升 四#xff1a;直接选择排序4.1 概念4.2 画图表示4.3 代码实现4.4 总结提升 五#xff1a;堆… 数据排序 一故事背景二直接插入排序2.1 概念2.2 画图表示2.3 代码实现2.4 总结提升 三希尔排序3.1 概念3.2 画图表示3.3 代码实现3.4 总结提升 四直接选择排序4.1 概念4.2 画图表示4.3 代码实现4.4 总结提升 五堆排序5.1 概念5.1.1 堆5.1.2 堆排序 5.2 画图表示5.3 代码实现5.4 总结提升 六表格比较七总结提升 一故事背景
最近在准备5月底的软件工程师的考试这个考试最困难的就是算法部分了。接下来的文章我将会总结 排序与算法希望通过此系列文章的总结能让我们不但把握住考试的试题更可以学会分析算法写出优秀的算法优化我们的代码。
二直接插入排序
2.1 概念
在插入第 i 个记录时R1R2…Ri-1 都已经排好序。这时候将第 i 个记录依次与 Ri-1 … R2R1 进行比较找到合适的位置插入插入位置及之后的记录依次向后移动
2.2 画图表示
只看概念描述可能不是很好理解让我们来画图理解一下这个算法。
首先给出一组待排序的数字 根据上述概念我们必须从第二个开始进行排序因为第一个数据之前没有数据对第一个数据比价是没有意义的。
通过观察规律和结合概念描述我们可以看出。整个顺序是前面的部分逐渐有序的。那个数据需要排序那么它之前的数据一定是有序的。例如数字4排序前它前面的数字为 1,3是有序的 数字2排序前它前面的数字为 1,3,4是有序的根据以上规律依次类推就可以将数据进行从小到大排序
2.3 代码实现
上文给出了对应算法的图相信通过此图大家对直接插入算法有了一定的了解那让我们来看看如何用代码去实现直接插入算法吧
算法代码 public static void insertionSort(int[] nums) {//首先记录数组的长度int len nums.length;//从数组的第二个元素开始for (int i 1; i len; i) {//依次取出一个元素存储在current变量中Integer current nums[i];//定义一个指针初始化当前元素的前一个位置int j i - 1;//重复上述操作直到找到一个位置j使得 nums[j] current或者 j 已经到达数组的起始位置。while (j 0 nums[j] current) {nums[j 1] nums[j];j--;}nums[j 1] current;}}执行代码
public class Main {public static void main(String[] args) {int[] nums {1,4, 3, 2,6,5,8,7,9};System.out.println(排序前Arrays.toString(nums));Sort1.insertionSort(nums);System.out.println(排序后Arrays.toString(nums));}
}运行结果
上述代码中核心点有两个
一个是循环的边界。 外层for循环的边界是从第二个元素开始到最后一个循环结束。 内层的while循环的边界是到第一个数据并且找到的数据必须比当前操作的数据大。一个是数据的交换。 数据交换主要体现在内层的while循环中如果符合条件则将比当前 j指针标记的数向后移动一个。最后找到符合条件的位置时将当前操作的数 current 放到指定位置。
2.4 总结提升
上述给出了直接插入排序的算法分析与实例。直接插入排序算法在最好情况下数据完全有序时间复杂度为O(n),最坏的情况下数据无序为O(n²)。此算法属于比较简单的算法。希望大家通过我的博客能够理解此算法。
三希尔排序
3.1 概念
希尔排序又称“缩小增量排序”他是对“直接插入排序的改进”。希尔排序的思想是先将整个待排记录分割成若干个子序列然后分别进行直接插入排序待整个序列中的记录基本有序时再对全体进行一次直接插入排序。
3.2 画图表示
希尔排序的核心点是** 分隔子序列 **将待排数组分割成子序列分别进行排序。具体的分隔数没有特别要求一般初始值是待排数列的一半然后依次减半直至最后间隔为1为止。 上图中给出了一个待排数组的变化。
待排数组长度为8所以子序列间隔分别为 4 2 1间隔为4时一共有4组数据将这四组数据进行直接插入排序保证这四组数据有序。间隔为2时一共有2组数据将这两组数据进行直接插入排序保证这两组数据有序。间隔为1时整体进行直接插入排序但是这时数据已经基本有序需要移动的数据很少。
3.3 代码实现
下文给出** 希尔排序** 的具体实现 public static void shellSort(int[] arr) {//交换的次数int num 0;int n arr.length;// 初始化增量gap为数组长度的一半for (int gap n / 2; gap 0; gap / 2) {System.out.println(gap值 gap);// 对于每个增量gap进行一次插入排序for (int i gap; i n; i) {//temp表示当前操作的元素int temp arr[i];//j是一个指针表示当前操作的元素int j i;// 对于每个元素向前比较gap个距离的元素。如果前面的元素大于当前元素才需要交换while (j gap arr[j - gap] temp) {//后面元素挪到前面arr[j] arr[j - gap];//当前操作元素变为前gap个j - gap;}//将本次需要操作元素放到移动的位置arr[j] temp;num;System.out.println(gap Arrays.toString(arr));}}System.out.println(一共交换了 num 次);}3.4 总结提升
希尔排序是一种不稳定的排序算法。其时间复杂度约为On¹·³在排序过程中需要一个元素的辅助空间用于元素值交换空间爱你复杂的为O1。 相对于直接插入排序而言希尔排序的时间复杂度更低效率更高对于大规模数据排序更加适用。
四直接选择排序
4.1 概念
直接选择排序是一种简单排序算法它的基本思想是在待排的数据中选取最小值与当前值进行交换直至交换完毕。
4.2 画图表示 4.3 代码实现
/*** BelongsProject: algorithm* BelongsPackage: org.example* Author:hlzs1* Description: 直接选择排序* CreateTime: 2023-04-28 10:44* Version: 1.0*/
public class Sort3 {public static void SelectionSort(int[] arr) {int length arr.length;for (int i 0; i length-1 ; i) {//从当然开始筛选int minIndex i;for (int j i1; j length; j) {if(arr[minIndex] arr[j]){minIndex j;}}//交换数值int current arr[i];arr[i] arr[minIndex];arr[minIndex] current;}}}
4.4 总结提升
直接选择排序的时间复杂度为 O(n^2)其中 n 是待排序数组的长度。具体来说它的时间复杂度由两个嵌套循环决定。直接选择排序的时间复杂度为 O(n^2)其中 n 是待排序数组的长度。具体来说它的时间复杂度由两个嵌套循环决定。
五堆排序
5.1 概念
在计算机科学中堆Heap是一种特殊的树形数据结构它通常是一个近似完全二叉树其中父节点的值总是大于或小于它的子节点。具体而言堆被分为两种类型最大堆Max Heap和最小堆Min Heap。在最大堆中每个节点的值都大于或等于其子节点的值。因此最大堆的根节点是堆中的最大元素。在最小堆中每个节点的值都小于或等于其子节点的值。因此最小堆的根节点是堆中的最小元素。
5.1.1 堆
5.1.2 堆排序
对一组待排序元素首先按照堆的定义排成一个序列建立初始堆之后输出堆顶最大元素对于大顶堆而言然后将剩余的元素在调整成新堆从而得到次大元素如此反复直到全部元素有序为止。
5.2 画图表示 5.3 代码实现
public static void heapSort(int[] arr) {//判断如果arr为空或者只有一个数据则不需要进行排序if (arr null || arr.length 2) {return;}//构建大根堆for (int i 0; i arr.length; i) {heapInsert(arr, i);}//将堆顶元素依次放到数组最后并重新调整堆结构int size arr.length;swap(arr, 0, --size);while (size 0) {heapify(arr, 0, size);swap(arr, 0, --size);}}//构建大根堆public static void heapInsert(int[] arr, int index) {//如果while (arr[index] arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index (index - 1) / 2;}}//调整大根堆public static void heapify(int[] arr, int index, int size) {int left index * 2 1;while (left size) {int largest left 1 size arr[left 1] arr[left] ? left 1 : left;largest arr[largest] arr[index] ? largest : index;if (largest index) {break;}swap(arr, largest, index);index largest;left index * 2 1;}}//交换数组中的两个元素public 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[] arr {4, 6, 2, 9, 1, 8, 5, 3, 7};heapSort(arr);System.out.println(Arrays.toString(arr));}5.4 总结提升
堆排序是一种不稳定的排序与直接插入排序很像每次都是筛选出一个最值但是不同的是堆排序利用了树的结构进行了排序。
六表格比较
算法名 \ 比较项时间复杂度空间复杂度稳定性直接插入排序O(n) ~ O(n²)O(1)稳定希尔排序约为On¹·³O(1)不稳定直接选择排序O(n²)O(1)稳定堆排序O(nlogn)O(1)不稳定
七总结提升
本文给出了直接插入排序、希尔排序、直接选择排序、堆排序的。概念、图、和代码。希望大家通过此篇文章能理解什么是算法各个算法的不同作用这对我们以后看源码自己编写代码有很大的好处可以很好的训练我们的思维。 本篇为上篇接下来的文章我会继续输出关于数据排序的另外四种算法有兴趣的朋友请持续关注我~
