杭州网站设计建设,河池市住房和城乡建设局网站,深圳有哪几个区,广州发际体育用品有限公司快速排序和归并排序是两种速度较快的排序方式#xff0c;是最应该掌握的两种排序算法#xff0c; #xff08;一#xff09;快速排序#xff08;不稳定的#xff09;
基本思想#xff1a;分治
平均时间复杂度#xff1a;O(nlogn) / 最慢O(n^2) / 最快O(n)
步骤…
快速排序和归并排序是两种速度较快的排序方式是最应该掌握的两种排序算法 一快速排序不稳定的
基本思想分治
平均时间复杂度O(nlogn) / 最慢O(n^2) / 最快O(n)
步骤 1.确定分界点 2.调整区间分界点右的元素全都小于等于分界点、左边全都大于等于分界点 3.递归的处理左右两段
模板
public static int[] quickSort(int[] arr,int l,int r){if(lr){return arr;}int k arr[lr 1],il-1,jr1;while(ij){while(arr[i]k);while(arr[--j]k);if(ij){int temp arr[i];arr[i]arr[j];arr[j]temp;}}quickSort(arr,l,j);quickSort(arr,j1,r);
return arr;}
//TODO: 至少默写3-5遍当前写了1遍public static void main(String[] args) {int[] arr01 {0,1};int[] arr02 {1,2};int[] arr03 {45, 78, 12, 67, 34, 90, 23, 56, 10};
Scanner in new Scanner(System.in);int n in.nextInt();int[] arr04 new int[n];for(int i0;in;i) {int num in.nextInt();arr04[i] num;}int[] res quickSort(arr04, 0, n-1);System.out.println(Arrays.toString(res));}
注意点 注意i和j的初始值为int il-1,jr1 分界点karr[lr 1]; 右移一位相当于除以二右移2位是除以4 二归并排序稳定的
基本思想分治、从整个数组的中间开始划分
时间复杂度稳定的O(nlogn)
步骤 确定分界点mid lr 1; 递归排序左边和右边 归并把两个有序数组合并为一个有序数组
模板
import java.util.*;public class Main{public static void mergeSort(int[] arr,int l,int r){//1.递归终止条件if(rl)return;//2.划分int mid lr1;mergeSort(arr,l,mid);mergeSort(arr,mid1,r);//3.归并int tem[] new int[r-l1];int k0,il,jmid1;while(imid jr){if(arr[i]arr[j]) tem[k] arr[i];else tem[k] arr[j];}while(imid) tem[k] arr[i];while(jr) tem[k] arr[j];//将临时数组中已经排好序的数据放到原数组这里重复利用了之前定义过的i和jfor(il,j0;ir;i,j){arr[i]tem[j];}}public static void main(String[] args){Scanner in new Scanner(System.in);int n in.nextInt();int[] arr new int[n];for(int i0;in;i){int num in.nextInt();arr[i] num;}mergeSort(arr,0,n-1);for(int i0; in;i){System.out.print(arr[i] );}}
}
