天津平台网站建设设计,网站首页横版图怎么做,第一个制作网页的公司,推广策划公司⭐ 作者#xff1a;小胡_不糊涂 #x1f331; 作者主页#xff1a;小胡_不糊涂的个人主页 #x1f4c0; 收录专栏#xff1a;浅谈数据结构 #x1f496; 持续更文#xff0c;关注博主少走弯路#xff0c;谢谢大家支持 #x1f496; 冒泡、快速排序 1. 冒泡排序2. 快速… ⭐ 作者小胡_不糊涂 作者主页小胡_不糊涂的个人主页 收录专栏浅谈数据结构 持续更文关注博主少走弯路谢谢大家支持 冒泡、快速排序 1. 冒泡排序2. 快速排序 1. 冒泡排序 交换排序基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。 代码实现 /**冒泡排序*1.时间复杂度O(N^2)*2.空间复杂度O(1)*3.稳定性稳定* param array*/public static void bubbleSort(int[] array){//i:记录躺数//jarray.length-i-1: -1 为了防止越界for(int i0;iarray.length;i){for(int j0;jarray.length-i-1;j){if(array[j1]array[j]){int tmparray[j1];array[j1]array[j];array[j]tmp;}}}}
2. 快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其**基本思想为**任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 代码实现
/*** 快速排序-》* 时间复杂度* 最好的情况下O(N*logN)* 最坏情况下O(N^2) 逆序/有序* 空间复杂度* 最好的情况下O(logN)* 最坏情况下O(N) 逆序/有序* 稳定性不稳定* param array*/
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right)
{if(right - left 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div partion(array, left, right);// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div1, right)// 递归排[left, div)QuickSort(array, left, div);// 递归排[div1, right)QuickSort(array, div1, right);
}
private static void swap(int[] array,int i,int j) {int tmp array[i];array[i] array[j];array[j] tmp;
}上述为快速排序递归实现的主框架发现与二叉树前序遍历规则非常像在写递归框架时可想想二叉树前序遍历规则即可快速写出来后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有 1. Hosre版
/*** param array* param left* param right* return*/public static int partion(int[] array,int left,int right){int ileft;int privotarray[left];//基准元素while(leftright){//大于privot的放在右边小于的放在左边while(leftrightarray[right]privot){right--;}while(leftright array[left]privot){left;}swap(array,right,left);//rightprivotleft}swap(array,i,left);//将基准元素放回return left;}2. 挖坑法 先将一个数据存放在临时变量key中形成一个空缺位。一般选取第一个元素。 /*** 挖坑法* param array* param left* param right* return*/public static int partion(int[] array,int left,int right){int privotarray[left];while(leftright){//从右边开始while(leftrightarray[right]privot){right--;}array[left]array[right];while(leftrightarray[left]privot){left;}array[right]array[left];}array[left]privot;//将基准元素填入空位return left;}3. 前后指针法 初始时设置两个指针。prev指向序列开头cur指针指向prev的后一个位置 /*** 前后指针法* param array* param left* param right* return*/public static int partion(int[] array,int left,int right){int prevleft;int curleft1;while(curright){while(array[cur]array[left] array[cur]!array[prev]){swap(array,prev,cur);}cur;}swap(array,prev,left);return prev;}以上3种方式每次划分之后的前后顺序有可能是不一样的
