算法基础学习——快排与归并（附带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]+" ");
        }

    }
}