Loading...
墨滴

程序小猿

2021/03/22  阅读:35  主题:蔷薇紫

面试必考两大排序算法

最近金三银四,想必一部分读者正在准备跳槽或者春招,那今天,小猿就带来面试中必考的两道排序算法:快排和归并,虽然不难,但没自己亲手写过的读者,不让现在就试试看咯!

快速排序

衍生题:215. 数组中的第K个最大元素

快速排序的思想很简单,就是确定一个锚点元素,将数组中所有小于锚点元素的放在一边,大于锚点元素的放在另一边,递归进行,直到排序结束。代码与注释如下:

public int[] quickSort(int[] nums) {
    quickSort(nums, 0, nums.length-1);
    return nums;
}
public void quickSort(int[] nums, int start, int end) {
    if(start>=end)
        return;
    int i=start, j=end;
    //设置锚点元素
    int flag = nums[start];
    while(i<j){
        //注意下面两个循环不能搞反,会存在锚点元素不能交换的问题
        while(i<j && nums[j]>=flag)
            j--;
        while(i<j && nums[i]<=flag)
            i++;
        //交换元素    
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;

    }
    //交换锚点元素至临界位置
    nums[start] = nums[j];
    nums[j] = flag;
    //递归调用
    quickSort(nums, start, i-1);
    quickSort(nums, i+1, end);
}

归并排序

衍生题:23. 合并K个升序链表

与快速排序以值为临界点不同,归并排序以位置为临界点,确定中间的元素为锚点元素,将锚点元素两边的数组分别排序后,做合并操作,然后递归进行,直到排序完成。代码及注释如下:

public int[] mergeSort(int[] nums) {
    mergeSort(nums, 0, nums.length-1);
    return nums;
}
public void mergeSort(int[] nums, int start, int end){
    if(start>=end)
        return;
    //选择锚点元素
    int mid = (start + end)/2;
    //递归调用
    mergeSort(nums, start, mid);
    mergeSort(nums, mid+1, end);
    //做合并操作
    merge(nums, start, end);
}
public void merge(int[] nums, int start, int end){
    int[] temp = new int[end-start+1];
    int mid = (start+end)/2;
    int i=start, j=mid+1;
    int k=0;
    //合并两个有序数组
    while(i<=mid && j<=end){
        if(nums[i]<nums[j])
            temp[k++]=nums[i++];
        if(nums[j]<=nums[i])
            temp[k++]=nums[j++];
    }
    //把左边剩余的数移入数组
    while(i<=mid)
        temp[k++]=nums[i++];
    //把右边剩余的数移入数组
    while(j<=end)
        temp[k++]=nums[j++];
    //赋值给原数组
    for(int n=0;n<temp.length;n++){
        nums[n+start]=temp[n];
    }
}

快排和归并是最为常见的两大排序算法,其基本原理相信各位读者都有了解,但想要把这两个算法100%的用代码一遍过,确实没那么容易,大家都去试一试吧!最后再用自己编写的测试用例尝试一下:

class Solution {
    public int[] mergeSort(int[] nums) {
        mergeSort(nums, 0, nums.length-1);
        return nums;
    }
    public void mergeSort(int[] nums, int start, int end){
        if(start>=end)
            return;
        int mid = (start + end)/2;
        mergeSort(nums, start, mid);
        mergeSort(nums, mid+1, end);
        merge(nums, start, end);
    }
    public void merge(int[] nums, int start, int end){
        int[] temp = new int[end-start+1];
        int mid = (start+end)/2;
        int i=start, j=mid+1;
        int k=0;
        while(i<=mid && j<=end){
            if(nums[i]<nums[j])
                temp[k++]=nums[i++];
            if(nums[j]<=nums[i])
                temp[k++]=nums[j++];
        }
        while(i<=mid)
            temp[k++]=nums[i++];
        while(j<=end)
            temp[k++]=nums[j++];
        for(int n=0;n<temp.length;n++){
            nums[n+start]=temp[n];
        }
    }


    public int[] quickSort(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums, int start, int end) {
        if(start>=end)
            return;
        int i=start, j=end;
        int flag = nums[start];
        while(i<j){
            while(i<j && nums[j]>=flag)
                j--;
            while(i<j && nums[i]<=flag)
                i++;

            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;

        }
        nums[start] = nums[j];
        nums[j] = flag;

        quickSort(nums, start, i-1);
        quickSort(nums, i+1, end);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] num = {5,9,1,2,5,6,7,0,3,4};
        int[] ans = s.mergeSort(num);
        System.out.print("归并排序结果:");
        for(int i: ans){
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println();
        ans = s.quickSort(num);
        System.out.print("快速排序结果:");
        for(int i: ans){
            System.out.print(i);
            System.out.print(" ");
        }

        System.out.println();
        System.out.println();

        int[] num2 = {1,1,0};
        ans = s.mergeSort(num2);
        System.out.print("归并排序结果:");
        for(int i: ans){
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println();
        ans = s.quickSort(num2);
        System.out.print("快速排序结果:");
        for(int i: ans){
            System.out.print(i);
            System.out.print(" ");
        }

        System.out.println();
        System.out.println();

        int[] num3 = {0,0,1};
        ans = s.mergeSort(num3);
        System.out.print("归并排序结果:");
        for(int i: ans){
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println();

        ans = s.quickSort(num3);
        System.out.print("快速排序结果:");
        for(int i: ans){
            System.out.print(i);
            System.out.print(" ");
        }
    }
}

微信关注我,带你拿大厂offer!

程序小猿

2021/03/22  阅读:35  主题:蔷薇紫

作者介绍

程序小猿