算法学习面试精选程序员

阿里面试官：你连个排序算法都讲不明白？出门右拐吧！

2021-01-26  本文已影响0人  前程有光

排序算法一表总览

其他注意事项：

private static void swap(int nums, int i, int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

各排序算法说明及其实现

快速排序

public static void quickSort(int[] nums, int l, int r){
    if(l >= r) return;
    int i = l - 1, j = r + 1;  //先定位到边界两侧
    int key = nums[l];
    while(i < j){
        while(nums[++i] < key);  //先移动再与关键字判断
        while(nums[--j] > key);  //先移动在与关键字判断
        if(i < j)
            swap(nums, i, j);   //交换两侧值
    }
    quickSort(nums, l, j);
    quickSort(nums, j + 1, r);
}

堆排序

public static void heapSort(int[] nums){
    for (int i = (nums.length >>> 1) - 1; i >= 0; i--){  //建堆
        siftDown(nums, i, nums.length);
    }
    for(int i = nums.length - 1; i > 0; i--){    //排序
        swap(nums, 0, i);
        siftDown(nums, 0, i);
    }
}

private static void siftDown(int[] heap, int i, int len){
    int curNum = heap[i];
    int half = len >>> 1;
    while (i < half){    //直到到没有子结点
        int lcIdx = (i << 1) + 1;  //左子结点索引
        int rcIdx = lcIdx + 1;   //右子结点索引
        int temp = heap[lcIdx];   //选取左子结点作为临时值
        if(rcIdx < len && temp < heap[rcIdx]){
            temp = heap[lcIdx = rcIdx];
        }
        if (curNum >= temp)
            break;
        heap[i] = temp;
        i = lcIdx;   //下一层检测
    }
    heap[i] = curNum;
}

归并排序

public void mergeSort(int nums, int l, int r){
    if(l >= r) return;
    int mid = (l + r) >> 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]) 
            temp[k++] = nums[i++];
        else 
            temp[k++] = nums[j++];
    }
    //temp是外部开好的数组
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= r) temp[k++] = nums[j++];

    for (i = l, j = 0; i <= r; i++, j++) 
        nums[i] = temp[j];
}

选择排序

public static void selectSort(int nums){
    for(int i = 0; i < nums.length; i++){
        int idx = i;
        for(int j = i; j < nums.length; j++){
            if(nums[j] < nums[i])
                idx = j;
        }
        swap(nums, i, idx);
    }
}

插入排序

public static void insertSort(int nums){
    for(int i = 1; i < nums.length; i++){
        int temp = nums[i];
        for(int j = i; j > 0 && nums[j - 1] > temp; j--){
            nums[j] = nums[j - 1];
        }
        nums[j] = temp;
    }
}


public static void insertSort(int nums){
    for(int i = 1; i < nums.length; i++){
        int temp = nums[i];
        int l = 0, r = i - 1;
        while(l <= r){
            int mid = (l + r)/2;
            if(nums[mid] > temp) r = mid - 1;
            else l = mid + 1;
        }
        for(int j = i; j > low; j--){
            nums[j] = nums[j - 1];
        }
        nums[j] = temp;
    }
}

希尔排序

public static void shellSort(int[] nums){
    int gap = nums.length;
    while(true){
        gap /= 2;
        for(int i = 0; i < gap; i++){
            temp = nums[i];
            for(int j = i; j > 0 && temp > nums[j]; j -= gap){
                nums[j] = nums[j - gap];
            }
            nums[i] = temp;
        }
        if(gap == 1) break;
    }
}

冒泡排序

public static void bubbleSort(int nums){
    for(int i = 1; i < nums.length; i++){
        boolean changed = false;
        for(int j = 0; j < nums.length - i;j++){
            if(nums[j] > nums[j + 1]){
                swap(nums, j, j + 1);
                changed = true;
            }
        }
        if(changed == false) break;
    }
}


public static void bubbleSort(int nums){
    int l = 0, r = nums.length - 1, shift = 1;
    while(l < r){
        boolean changed = false;
        for(int i = l; i < r; i++){
            if(nums[i] > nums[i + 1]){
                swap(nums, i, i + 1);
                shift = i;
            }
        }
        r = shift;
        for(int i = r - 1; i >= l; i--){
            if(nums[i] > nums[i + 1]){
                swap(nums, i, i + 1);
                shift = i + 1;
            }
        }
        l = shift;
    }
}

计数排序

public static void countingSort(int nums){
    int[] counter = new int[65535];
    //此处的counter数组需要随情况变化
    for(int i = 0; i < nums.length; i++){
        counter[nums[i]]++;
    }
    int idx = 0;
    for(int i = 0; i < counter.length; i++){
        while(counter[i] > 0) 
            nums[idx++] = counter[i];
    }
}

排序算法的应用举例

刷题需要掌握的几种算法

leetcode排序算法题举例

class Solution {
    public void sortColors(int[] nums) {
        int[] counter = new int[3];
        for(int i = 0; i < nums.length; i++){
            counter[nums[i]]++;
        }
        int idx = 0;
        for(int i = 0; i < 3; i++){
            while(counter[i] > 0){
                nums[idx++] = i;
                counter[i]--;
            }
        }
    } 
}


class Solution {
    public String rankTeams(String[] votes) {
        int len = votes[0].length();
        int[][] map = new int[26][len + 1]; // 多1用于存放团队信息
        for(int i = 0; i < 26; i++) map[i][len] = i;

        for(int i = 0; i < votes.length; i++){  //投票统计
            String s = votes[i];
            for(int j = 0; j < len; j++){
                map[s.charAt(j) - 'A'][j]++;
            }
        }
        Arrays.sort(map, (a, b) ->{    //投票结果排序
            for(int i = 0; i < len; i++){
                if(a[i] < b[i]) return 1;
                if(a[i] > b[i]) return -1;
            }
            return 0;
        });
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; i++){    //获取结果对应团队
            sb.append((char)('A' + map[i][len]));
        }
        return sb.toString();
    }
}


class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int n = position.length, res = 0;
        double[][] cars = new double[n][2];
        //分别记录开始位置和到达时间
        for(int i = 0; i < n; i++){
            cars[i][0] = position[i];
            cars[i][1] = (double)(target - position[i])/speed[i];
        }
        //开始位置排序
        Arrays.sort(cars, (a, b) -> Double.compare(a[0], b[0]));
        double cur = 0;
        for(int i = n - 1; i >= 0 ; i--){
            //能否追上前车
            if(cars[i][1] > cur){
                cur = cars[i][1];
                res++;
            }
        }
        return res;
    }
}

小结

上一篇 下一篇

猜你喜欢

热点阅读