建设网站公司哪好,我的网站模板下载,兰州网站设计哪个平台好,装修网站怎么做文章目录 #x1f412;个人主页#x1f3c5;算法思维框架#x1f4d6;前言#xff1a; #x1f380;冒泡排序 时间复杂度O(n^2)#x1f387;1. 算法步骤思想#x1f387;2.动画实现#x1f387; 3.代码实现#x1f387;4.代码优化#xff08;添加标志量#xff09; … 文章目录 个人主页算法思维框架前言 冒泡排序 时间复杂度O(n^2)1. 算法步骤思想2.动画实现 3.代码实现4.代码优化添加标志量 快速排序 时间复杂度O(n*logn)1. 算法步骤思想2、动画演示3.代码实现 个人主页 算法思维框架 前言
本篇博客主要以介绍十大排序算法中的冒泡排序、快速排序有详细的图解、动画演示、良好的代码注释帮助加深对这些算法的理解进行查漏补缺~
冒泡排序 时间复杂度O(n^2)
冒泡排序Bubble Sort 是一种简单直观的排序算法。它重复地走访要排序的数列一次 比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直 到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元 素会经交换慢慢浮到数列的头部。
1. 算法步骤思想 1比较相邻的元素。如果第一个比第二个大就交换他们两个。 2对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元 素会是最大的数。 3重复12步骤除了最后一个元素。 对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 2.动画实现 3.代码实现
public void sort(int[] arr){if(arrnull||arr.length2){return;}//思路【冒泡排序】借助双循环进行两两交换将最大的“气泡”排到数组末尾for (int i 0; i arr.length-1; i) {//排n-1趟for (int j 1; j arr.length-i; j) {//比较n-1-i次,因为下标是从1开始取的if(arr[j-1]arr[j]){//两两交换int temparr[j-1];arr[j-1]arr[j];arr[j]temp;}}}}4.代码优化添加标志量 //对冒泡排序的一点小优化添加标志量来记录数组是否是有序的public void sort1(int[] arr){if(arrnull||arr.length2){return;}//思路借助双循环进行两两交换将最大的“气泡”排到数组末尾同时添加一个标志量判断数组是否已经排好序了for (int i 0; i arr.length-1; i) {//排n-1趟boolean flagtrue;for (int j 1; j arr.length-i; j) {//比较n-1-i次,因为下标是从1开始取的if(arr[j-1]arr[j]){//两两交换int temparr[j-1];arr[j-1]arr[j];arr[j]temp;flagfalse;//证明还没有排好序}}if(flag){//flag为true代表排好序了return;}}}添加标志量后最快的情况是遍历一遍数组时发现元素没有交换直接就是有序的此时只需要遍历一遍数组即可
快速排序 时间复杂度O(n*logn)
快速排序的最坏运行情况是 0(n^2) 比如说顺序数列的快排。但它的平期望时间是 O(nlogn)且 (nlogn)记号中隐合的常数因子很小比复杂度稳定等于 0(nlogn)的归并排序要小很多所以对绝大多数顺序性较弱的随机数列而言快速排序总是优于归并排序。它是对冒泡排序的改进快速排序过程其实对应着二叉树的前序遍历
1. 算法步骤思想 从数列中挑出一个元素称为 “基准”pivot 中心点 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准 的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位 置。这个称为分区partition操作 递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序 2、动画演示
快速排序的动画演示 相关博客 (42条消息) 快速排序过程图解_曹利荣的博客-CSDN博客_快速排序图解 (42条消息) 史上最详细图解快速排序_文文的博客的博客-CSDN博客_快速排序图解
3.代码实现 public void sort(int[] arr){if(arrnull||arr.length2){return;}sortDG(arr,0,arr.length-1);}private void sortDG(int[] arr,int left,int right){if(leftright){//【注意】return;}//思路先以left为基准点寄存创建left、right索引先与right进行比较// 如果基准arr[right],覆盖left,基准再与left进行比较...直到leftright,填入基准//如果基准arr[right],right--,直到满足上述条件划分左右区间接着进行快速排序int ileft;int jright;int rootValarr[left];//默认以左边为基准while (ij){while (rootValarr[j]ij){j--;}if(ij){//【需要判断i是否小于j】arr[i]arr[j];}while (rootValarr[i]ij){i;}if(ij){//【需要判断i是否小于j】arr[j--]arr[i];}}//插入基准点arr[i]rootVal;sortDG(arr,0,i-1);//ij且这个位置是待插入的基准点下标sortDG(arr,i1,right);}
