侧边栏壁纸
博主头像
CoderKui

坐中静,舍中得,事上练

  • 累计撰写 51 篇文章
  • 累计创建 69 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

QuickSort & MergeSort

CoderKui
2021-11-13 / 0 评论 / 0 点赞 / 140 阅读 / 390 字 / 正在检测是否收录...

QuickSort

  1. 确定分界点 q[l]、q[r]、q[(l + r) / 2]或随机
  2. 🌟调整区间,使得分界点左边均<=分界点,右边均>=分界点
  3. 递归处理左右两段
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] q = new int[n];
        for(int i = 0; i < n; ++i) {
            q[i] = sc.nextInt();
        }
        quickSort(q, 0, n - 1);
        for(int i = 0; i < n; ++i) {
            System.out.printf("%d ",q[i]);
        }
    }
    
    public static void quickSort(int[] q, int l, int r) {
        if(l >= r) return;
        int x = q[l + r >> 1], i = l - 1, j = r + 1;
        while(i < j) {
            do i++; while(q[i] < x);
            do j--; while(q[j] > x);
            if(i < j) {
                int tmp = q[i];
                q[i] = q[j];
                q[j] = tmp;
            }
        }
        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }
}

MergeSort

分治思想

  1. 确定分界点mid (l + r) / 2
  2. 将数组分为两块:left部分和right部分,递归排序left和right
  3. 🌟归并,合二为一
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; ++i) {
            nums[i] = sc.nextInt();
        }
        mergeSort(nums, 0, n - 1);
        for(int i = 0; i < n; ++i) {
            System.out.print(nums[i] + " ");
        }
    }
    
    public static void mergeSort(int[] nums, int l, int r) {
        if(l >= r) return;
        int mid = l + r >> 1;
        int[] tmp = new int[r - l + 1];
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r) {
            if(nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        while(i <= mid) tmp[k++] = nums[i++];
        while(j <= r) tmp[k++] = nums[j++];
        for(i = l, j = 0; i <= r; ++i, ++j) {
            nums[i] = tmp[j];
        }
    }
}
0

评论区