常见排序算法之插入排序和选择排序
2021/6/2 22:21:18
本文主要是介绍常见排序算法之插入排序和选择排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
插入排序
1.直接插入排序
结合生活中的例子,插入排序令联想到捏扑克牌的过程,假设只有一个人捏牌,未经排序的所有扑克牌是没有排序的序列,每张扑克牌是序列中的一个数。每次从未经排序的扑克牌中取出一张牌和已经排好序列的扑克牌比较(只看牌的字面数字:从左至右的顺序是由小到大),将这张牌插入到排好序列中比自己大并且是序列中的最小的牌后面。再将排好序列中比自己大的元素整体后移。
代码实现
public static void insertSort(int[] arr){ int bound = 1; for(;bound < arr.length;bound++){//第一层for,n个元素需要n- 1躺扫描 int insertVal = arr[bound];//插入的数字,默认arr[0]为已排序元素,保存这个插入的值 int index = bound - 1;//决定了相邻关系 // for(;index >= 0;index --){ // //每一趟将一个元素插入到它前面的子序列中 // if(insertVal < arr[index]){ // arr[index + 1] = arr[index]; // }else{ // break; // } // } // arr[index + 1] = insertVal;//这里的index一定是插入值insertVal的前一个索引 while(index >= 0 && arr[index] > insertVal){ arr[index + 1] = arr[index]; index--; } arr[index + 1] = insertVal; } }
希尔排序算法是取直接插入排序算法之长、避其短的一种算法。由直接插入排序算法可知。数据序列越接近有序,n较小,时间效率就越高。
将数据序列按下标的一定增量进行分组,对每组使用插入排序算法排序,随着增量逐渐减少至1时,整个文件被分为一组,算法终止。
//希尔排序 public static void shellSort(int[] arr){ int gap = arr.length/2; while(gap >= 1){ ShellInsertSort(arr,gap); gap /= 2; } } public static void ShellInsertSort(int[] arr, int gap) { int bound = gap; for(;bound < arr.length;bound ++){ int insertVal = arr[bound]; int index = bound - gap; for(;index >= 0;index-- ){ if(insertVal < arr[index]){ arr[index + gap] = arr[index]; }else{ break; } } arr[index + gap] = insertVal; } }
选择排序
1.直接选择排序
public static void SelectInsert(int[] arr){ int bound = 0 ; for(;bound < arr.length;bound ++){ for(int index = bound + 1;index <arr.length;bound ++){ if(arr[index] < arr[bound]){//找到最小元素 int temp = arr[index]; arr[index] = arr[bound]; arr[bound] = temp; } } } }
这篇关于常见排序算法之插入排序和选择排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-08如何在敏捷项目中实现高效测试?
- 2024-07-08用户故事一定要有 “So that...” 吗?
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt