42区 网站开发指南,佛山网站关键词,网站建设广告词,最近军事新闻热点大事件2022冒泡排序 时间复杂度为 O(n^2) 原理 比较相邻的元素. 如果第一个比第二个大,就交换他们两个.依次比较每一对相邻的元素—结果 : 最后的元素是这组数中最大的重复上述步骤 , 除了最后一个[]因为最后一个已经是排好序的了(这组数中最大的那个)]持续对越来越少的元素进行如上…冒泡排序 时间复杂度为 O(n^2) 原理 比较相邻的元素. 如果第一个比第二个大,就交换他们两个.依次比较每一对相邻的元素—结果 : 最后的元素是这组数中最大的重复上述步骤 , 除了最后一个[]因为最后一个已经是排好序的了(这组数中最大的那个)]持续对越来越少的元素进行如上步骤 , 直到没有任何一对数字需要比较 核心代码
public static void bubbleSort(int[] arr) {for(int i0;iarr.length-1;i) {for(int j0;jarr.length-i-1;j) { //每次都少排最后一个if(arr[j]arr[j1]) { //把大的往后放int t arr[j];arr[j] arr[j1];arr[j1] t;}}}}快速排序
归并排序和快速排序都是基于“分而治之”的算法思想
public static int[] qSort(int arr[],int start,int end){int pivot arr[start]; //一般定义arr数组的首元素为key值int i start; int j end;while(ij){//从左往右找,直到找到一个大于等于key值的while(ij arr[i]pivot){i; } //从右往左找直到找到一个小于等于key值的while(ij arr[j]pivot){j—-; } if(ij arr[i]arr[j]){ //如果两值相等那么令左侧指针继续向后移i; }else{ //如果两值不同就交换两值int t arr[i];arr[i] arr[j];arr[j] t; }}if(i-1start) arrqSort(arr,start,i-1); //递归将小于key值的那些排序。并将这部分排完序的数组原数组的一部分赋值给原数组if(j1end) arrqSort(arr,j1,end); //递归将大于key值的那些排序。同上return arr;
}归并排序
时间复杂度 O(nlogn)速度仅次于快速排序 归并 就是先将带排序的数组不断拆分指导拆分到只剩一个元素的时候这时我们再把他们合并为两个有序的数组得到长度更长的有序数组。然后按照这样的思路一层一层的合并直到整个数组有序。怎么合并 要借助一个和原数组等长的新数组这也是个典型的 以空间换时间的 做法
// import java.util.Arrays;public class Main{public static void main(String[] args){int[] arr {1,4,3,7,14,6,10};// System.out.println(Arrays.toString(arr));sortArray(arr);for(int i0;iarr.length;i){System.out.print(arr[i] );}}//归并排序的入口public static int[] sortArray(int[] arr){//定义一个辅助数组tempint[] temp new int[arr.length];//进行归并排序mergeSort(arr,0,arr.length-1,temp);//返回排好序的原数组return arr;}//归并排序//实现归并的分public static void mergeSort(int[] arr,int left,int right,int[] temp){//如果只有一个元素就不需要继续划分只有一个元素的区间本来就是有序的// if(left right) return;//当left right 说明该区间是由一组数组成需要继续划分if(left right){int mid (leftright)/2; //这段区间的中值用来划分左右区域mergeSort(arr, left, mid, temp); //递归划分左半区mergeSort(arr, mid1, right, temp); //递归划分右半区//合并已经排序的部分左半区和右半区从只有一个元素的区间开始merge(arr,left,mid,right,temp);}}
//实现归并的合
//arr是原数组left是左半区的起始位置mid是左半区的结束位置right是右半区的结束位置temp是辅助数组public static void merge(int[] arr,int left,int mid,int right,int[] temp){int i left; //左半区的起始位置int j mid1; //右半区的起始位置int k left; //辅助数组的位置索引//合并//在左半区的位置索引范围内和右半区的位置索引范围内比较左右半区对应索引位置得的数值的大小小的先放入temp数组中while(imid jright){//用三元运算符 更简洁 和下面的if else语句一个意思temp[k] arr[i] arr[j] ? arr[i] : arr[j];/*if(arr[i]arr[j]) //左半区剩余第一个元素更小temp[k] arr[i]; //意思是先让temp[h] arr[i]再让kielse //右半区剩余第一个元素更小temp[k] arr[j];*/}//合并剩余元素当其中一个半区的位置索引结束时另一个半区可能还有剩余有序的元素--》直接合并到temp数组中即可//合并左半区剩余元素while(i mid)temp[k] arr[i];while(j right)temp[k] arr[j];//temp数组 复制回 arr数组// for(int q0;qtemp.length;q){// arr[q] temp[q];// }while(left right){arr[left] temp[left];left;}}
}
