算法基础学习——快排与归并（附带java模版）

快速排序和归并排序是两种速度较快的排序方式，是最应该掌握的两种排序算法，

（一）快速排序（不稳定的）

基本思想：分治

平均时间复杂度：O(nlogn) / 最慢O(n^2) / 最快O(n)

步骤：

• 1.确定分界点；

• 2.调整区间；（分界点右的元素全都小于等于分界点、左边全都大于等于分界点）

• 3.递归的处理左右两段；

模板：

public static int[] quickSort(int[] arr,int l,int r){if(l>=r){return arr;}int k = arr[l+r >> 1],i=l-1,j=r+1;while(i<j){while(arr[++i]<k);while(arr[--j]>k);if(i<j){int temp = arr[i];arr[i]=arr[j];arr[j]=temp;}}quickSort(arr,l,j);quickSort(arr,j+1,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 i=0;i<n;i++) {int num = in.nextInt();arr04[i] = num;}int[] res = quickSort(arr04, 0, n-1);System.out.println(Arrays.toString(res));}

注意点：

• 注意i和j的初始值为：int i=l-1,j=r+1

• 分界点k=arr[l+r >> 1]; 右移一位相当于除以二，右移2位是除以4；

（二）归并排序（稳定的）

基本思想：分治、从整个数组的中间开始划分

时间复杂度：稳定的O(nlogn)

步骤：

1. 确定分界点mid = l+r >> 1;

2. 递归排序左边和右边

3. 归并（把两个有序数组合并为一个有序数组）

模板：

import java.util.*;public class Main{public static void mergeSort(int[] arr,int l,int r){//1.递归终止条件if(r<=l)return;//2.划分int mid = l+r>>1;mergeSort(arr,l,mid);mergeSort(arr,mid+1,r);//3.归并int tem[] = new int[r-l+1];int k=0,i=l,j=mid+1;while(i<=mid && j<=r){if(arr[i]<arr[j]) tem[k++] = arr[i++];else tem[k++] = arr[j++];}while(i<=mid) tem[k++] = arr[i++];while(j<=r) tem[k++] = arr[j++];//将临时数组中已经排好序的数据放到原数组（这里重复利用了之前定义过的i和j）for(i=l,j=0;i<=r;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 i=0;i<n;i++){int num = in.nextInt();arr[i] = num;}mergeSort(arr,0,n-1);for(int i=0; i<n;i++){System.out.print(arr[i]+" ");}}
}