排序-剑指offer

2022-03-02

字数统计: 2.9k字 | 阅读时长: 15分

常用排序算法

冒泡排序选择排序快速排序归并排序堆排序插入排序

计数排序桶排序希尔排序

名称	时间复杂度	空间复杂度	稳定性	备注
冒泡	O(n²)	O(1)	稳定
选择	O(n²)	O(1)	不稳定	5 8 5 2 9 最小元素交换的时候
快速排序	O(nlogn)	O(logn) 递归	不稳定	5 3 3 4 3 8 9 10 11 ，基准元素交换的时候
归并排序	O(nlogn)	O(n)	稳定
堆排序	O(nlogn)	O(1) 堆是完全二叉树，直接可以用数组存储	不稳定	尾元素移动到顶部的时候

冒泡

选择

快排

归并

堆

快速排序

非递归-栈

import java.util.*;
public class QuickSortNoRecursion {
    private int partition(int[] array, int startIndex, int endIndex) {
        int pivot = startIndex;
        int mark = startIndex;
        for (int i=startIndex+1; i<=endIndex; i++) {
            if (array[i] < array[pivot]) {
                mark++;
                int temp = array[mark];
                array[mark] = array[i];
                array[i] = temp;
            }
        }
        int temp = array[pivot];
        array[pivot] = array[mark];
        array[mark] = temp;
        return mark;
    }
    private void quickSort(int[] array, int startIndex, int endIndex) {
        Deque<Map<String, Integer>> deque = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        map.put("startIndex", startIndex);
        map.put("endIndex", endIndex);
        deque.addFirst(map);
        while (!deque.isEmpty()) {
            // 取参数
            Map<String, Integer> parameter = deque.removeFirst();
            int paramStart, paramEnd, paramPivot;
            paramStart = parameter.get("startIndex");
            paramEnd = parameter.get("endIndex");
            // 分割
            paramPivot = this.partition(array, paramStart, paramEnd);
            // 基准左边开始结束参数入栈
            if (paramStart < paramPivot-1) {
                Map<String, Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex", paramStart);
                leftParam.put("endIndex", paramPivot-1);
                deque.addFirst(leftParam);
            }
            // 基准右边开始结束参数入栈
            if (paramPivot+1 < paramEnd) {
                Map<String, Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex", paramPivot+1);
                rightParam.put("endIndex", paramEnd);
                deque.addFirst(rightParam);
            }
        }
    }
    public static void main(String[] args) {
        QuickSortNoRecursion quickSortNoRecursion = new QuickSortNoRecursion();
        int[] array = {5, 4, 3, 8, 7, 6, 2, 1};
        quickSortNoRecursion.quickSort(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

非递归-队列
发现栈与队列效果都一样，因为通过partition，数组已经被分割成了互不干扰的小块，小块的处理顺序不影响最终的排序结果，上述利用栈，每次都处理右侧的小块，而利用队列，逐级处理，先处理本层的左右小块，在处理下层更小的小块

import java.util.*;
public class QuickSortNoRecursion {
    private int partition(int[] array, int startIndex, int endIndex) {
        int pivot = startIndex;
        int mark = startIndex;
        for (int i=startIndex+1; i<=endIndex; i++) {
            if (array[i] < array[pivot]) {
                mark++;
                this.swap(array, mark, i);
            }
        }
        this.swap(array, pivot, mark);
        return mark;
    }
    private void swap(int[] array, int src, int des) {
        int temp = array[src];
        array[src] = array[des];
        array[des] = temp;
    }
    private void quickSort(int[] array, int startIndex, int endIndex) {
        Queue<Map<String, Integer>> queue = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        map.put("startIndex", startIndex);
        map.put("endIndex", endIndex);
        queue.add(map);
        while (!queue.isEmpty()) {
            Map<String, Integer> parameter = queue.remove();
            int paramStart, paramEnd, paramPivot;
            paramStart = parameter.get("startIndex");
            paramEnd = parameter.get("endIndex");
            paramPivot = this.partition(array, paramStart, paramEnd);
            if (paramStart < paramPivot-1) {
                Map<String, Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex", paramStart);
                leftParam.put("endIndex", paramPivot-1);
                queue.add(leftParam);
            }
            if (paramPivot+1 < paramEnd) {
                Map<String, Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex", paramPivot+1);
                rightParam.put("endIndex", paramEnd);
                queue.add(rightParam);
            }
        }
    }
    public static void main(String[] args) {
        QuickSortNoRecursion quickSortNoRecursion = new QuickSortNoRecursion();
        int[] array = {5, 4, 3, 8, 7, 6, 2, 1};
        quickSortNoRecursion.quickSort(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

递归

import java.util.*;
public class QuickSortRecursion {
    private int partition(int[] array, int startIndex, int endIndex) {
        int pivot = startIndex;
        int mark = startIndex;
        for (int i=startIndex+1; i<=endIndex; i++) {
            if (array[i] < array[pivot]) {
                mark++;
                this.swap(array, mark, i);
            }
        }
        this.swap(array, pivot, mark);
        return mark;
    }
    private void swap(int[] array, int src, int des) {
        int temp = array[src];
        array[src] = array[des];
        array[des] = temp;
    }
    private void quickSort(int[] array, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int pivotIndex = this.partition(array, startIndex, endIndex);
        quickSort(array, startIndex, pivotIndex-1);
        quickSort(array, pivotIndex+1, endIndex);
    }
    public static void main(String[] args) {
        QuickSortRecursion quickSortRecursion = new QuickSortRecursion();
        int[] array = {5, 4, 3, 8, 7, 6, 2, 1};
        quickSortRecursion.quickSort(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

选择排序

public class SelectSort {
    public static void main(String[] args) {
        SelectSort selectSort = new SelectSort();
        int[] array = {4, 3, 2, 1, 5, 6, 7};
        selectSort.selectSort(array);
        System.out.println(Arrays.toString(array));
    }
    private void swap(int[] array, int src, int des) {
        int temp = array[src];
        array[src] = array[des];
        array[des] = temp;
    }
    private void selectSort(int[] array) {
        // array.length-1
        for (int i=0; i<array.length-1; i++) {
            int minIndex = i;
            for (int j=i+1; j<array.length; j++) {
                if (array[j] < array[minIndex]) {
                    // 记录最小值的索引下标
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                this.swap(array, i, minIndex);
            }
        }
    }
}

归并排序

原数组排序

import java.util.Arrays;
public class MergeSort {
    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] array = {1, 2, 3, 6, 5, 4};
        mergeSort.sort(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }
    // sort函数使指定闭区间内的数组变成有序的， sort先将其切割成小区间，
    // 实现排序功能的是靠merge函数
    private void sort(int[] array, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        int middleIndex = startIndex + (endIndex - startIndex) / 2;
        sort(array, startIndex, middleIndex);
        sort(array, middleIndex+1, endIndex);
        merge(array, startIndex, middleIndex, endIndex);
    }
    private void merge(int[] array, int startIndex, int middleIndex, int endIndex) {
        int[] temp = new int[endIndex-startIndex+1];
        int leftIndex = startIndex;
        int rightIndex = middleIndex+1;
        int mergeIndex = 0;
        while (leftIndex<=middleIndex && rightIndex<=endIndex) {
            if (array[leftIndex] < array[rightIndex]) {
                temp[mergeIndex++] = array[leftIndex++];
            } else {
                temp[mergeIndex++] = array[rightIndex++];
            }
        }
        while (leftIndex <= middleIndex) {
            temp[mergeIndex++] = array[leftIndex++];
        }
        while (rightIndex <= endIndex) {
            temp[mergeIndex++] = array[rightIndex++];
        }
        for (int i=0; i<temp.length; i++) {
            array[i+startIndex] = temp[i];
        }
    }
}

返回新数组
空间复杂度递归的深度是 logn 在合并的时候需要创建数组存放合并后的数组两个数组在合并后，没用引用指向它们，内存被释放，而合并在一起的新数组占用内存，在最后一次合并的时候占用的空间最大O(n)

时间复杂度 O(nlogn) 一共需要合并logn次，每一层，所有成对的小块合并，需要n次比较

import java.util.Arrays;
public class MergeSortNewArray {
    public static void main(String[] args) {
        int[] array = {3, 2, 5, 4};
        MergeSortNewArray mergeSortNewArray = new MergeSortNewArray();
        int[] newArray = mergeSortNewArray.sort(array, 0, array.length-1);
        System.out.println(Arrays.toString(newArray));
    }
    private int[] sort(int[] array, int startIndex, int endIndex) {
        if (startIndex == endIndex) {
            return Arrays.copyOfRange(array, startIndex, endIndex+1);
        }
        // endIndex为size-1，长度为偶数时，middle指向左半边的最后一个
        // 长度为奇数时，middle指向中间
        int middle = startIndex + (endIndex - startIndex) / 2;
        // sort函数的意义是对给定索引区间内的数组进行排序，返回新数组
        // 当索引区间长度是1时直接复制一份新的，当区间长度超过1时
        // 需要靠merge函数返回新数组
        int[] left = sort(array, startIndex, middle);
        int[] right = sort(array, middle+1, endIndex);
        return this.merge(left, right);
    }
    // merge函数作用是把两个排序的小数组，合并成大数组
    private int[] merge(int[] left, int[] right) {
        int[] temp = new int[left.length+right.length];
        int leftIndex = 0, rightIndex = 0, tempIndex = 0;
        while (leftIndex<left.length && rightIndex<right.length) {
            if (left[leftIndex] < right[rightIndex]) {
                temp[tempIndex++] = left[leftIndex++];
            } else {
                temp[tempIndex++] = right[rightIndex++];
            }
        }
        while (leftIndex < left.length) {
            temp[tempIndex++] = left[leftIndex++];
        }
        while (rightIndex < right.length) {
            temp[tempIndex++] = right[rightIndex++];
        }
        return temp;
    }
}

冒泡

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    int length = input.length;
    for (int i=0; i<length-1; i++) {
        for (int j=0; j<length-1-i; j++) {
            if (input[j] > input[j+1]) {
                int temp = input[j];
                input[j] = input[j+1];
                input[j+1] = temp;
            }
        }
    }
    ArrayList<Integer> result = new ArrayList<>();
    for (int i=0; i<k; i++) {
        result.add(input[i]);
    }
    return result;
}

刷题

数组中重复的数字

https://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524?tpId=13&tqId=1375279&ru=%2Fpractice%2F046a55e6cd274cffb88fc32dba695668&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

利用集合
重排数组
从头开始遍历数组，如果当前数组的值和索引值不一致，把当前值交换到和索引值一致的位置，然后再判断当前值和索引值是否一致，不一致继续交换，一个萝卜一个坑，萝卜移动到相应的坑中，当发现坑中有相同的萝卜的时候，这个萝卜就是重复的。

public int duplicate (int[] numbers) {
    // write code here
    int length = numbers.length;
    if (length <= 1) {
        return -1;
    }
    int i=0;
    while (i < length) {
        if (numbers[i] == i) {
            i++;
            continue;
        } else {
            // 当前萝卜和它要去的坑中的萝卜相同
            if (numbers[i] == numbers[numbers[i]]) {
                return numbers[i];
            } else {
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
    }
    return -1;
}

数组中的逆序对

https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5?tpId=13&tqId=23260&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

暴力法

public int InversePairs(int [] array) {
    int mod = 1000000007;
    int result = 0;
    for (int i=0; i<array.length; i++) {
        for (int j=i+1; j<array.length; j++) {
            if (array[i] > array[j]) {
                result += 1;
            }
        }
    }
    return result % mod;
}

最小k个数

冒泡

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    int length = input.length;
    for (int i=0; i<length-1; i++) {
        for (int j=0; j<length-1-i; j++) {
            if (input[j] > input[j+1]) {
                int temp = input[j];
                input[j] = input[j+1];
                input[j+1] = temp;
            }
        }
    }
    ArrayList<Integer> result = new ArrayList<>();
    for (int i=0; i<k; i++) {
        result.add(input[i]);
    }
    return result;
}

选择

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    int length = input.length;
    for (int i=0; i<k; i++) {
        int minIndex = i;
        for (int j=i+1; j<length; j++) {
            if (input[j] < input[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            int temp = input[i];
            input[i] = input[minIndex];
            input[minIndex] = temp;
        }
    }
    ArrayList<Integer> result = new ArrayList<>();
    for (int i=0; i<k; i++) {
        result.add(input[i]);
    }
    return result;
}

快排

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    if (k == 0) {
        return new ArrayList<Integer>();
    }
    this.quickSort(input, 0, input.length-1, k);
    ArrayList<Integer> result = new ArrayList<>();
    for (int i=0; i<k; i++) {
        result.add(input[i]);
    }
    return result;
}

private void quickSort(int[] array, int startIndex, int endIndex, int k) {
    int pivotIndex = this.partition(array, startIndex, endIndex);
    if (k-1 < pivotIndex) {
        quickSort(array, startIndex, pivotIndex-1, k);
    } else if (k-1 > pivotIndex) {
        quickSort(array, pivotIndex+1, endIndex, k);
    } else {
        return;
    }
}

private void swap(int[] array, int src, int des) {
    int temp = array[src];
    array[src] = array[des];
    array[des] = temp;
}

private int partition(int[] array, int startIndex, int endIndex) {
    int mark = startIndex;
    int pivot = startIndex;
    for (int i=startIndex+1; i<=endIndex; i++) {
        if (array[i] < array[pivot]) {
            mark++;
            this.swap(array, mark, i);
        }
    }
    this.swap(array, pivot, mark);
    return mark;
}

归并

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
    if (input.length == 0) {
        return new ArrayList<Integer>();
    }
    this.sort(input, 0, input.length-1);
    ArrayList<Integer> result = new ArrayList<>();
    for (int i=0; i<k; i++) {
        result.add(input[i]);
    }
    return result;
}

private void sort(int[] array, int startIndex, int endIndex) {
    if (startIndex == endIndex) {
        return;
    }
    int middleIndex = startIndex + (endIndex - startIndex) / 2;
    sort(array, startIndex, middleIndex);
    sort(array, middleIndex+1, endIndex);
    merge(array, startIndex, endIndex, middleIndex);
    
}

private void merge(int[] array, int startIndex, int endIndex, int middleIndex) {
    int[] mergeArray = new int[endIndex-startIndex+1];
    int leftIndex = startIndex;
    int rightIndex = middleIndex+1;
    int mergeIndex = 0;
    while (leftIndex<=middleIndex && rightIndex<=endIndex) {
        if (array[leftIndex] < array[rightIndex]) {
            mergeArray[mergeIndex++] = array[leftIndex++];
        } else {
            mergeArray[mergeIndex++] = array[rightIndex++];
        }
    }
    while (leftIndex <= middleIndex) {
        mergeArray[mergeIndex++] = array[leftIndex++];
    }
    while (rightIndex <= endIndex) {
        mergeArray[mergeIndex++] = array[rightIndex++];
    }
    for (int i=0; i<mergeArray.length; i++) {
        array[startIndex+i] = mergeArray[i];
    }
}

数据流中的中位数

新加入的数插入到比第一个比它大的数前面

private List<Integer> list = new ArrayList<>();
public void Insert(Integer num) {
    if (list.size() == 0) {
        list.add(num);
    } else {
        int i;
        for (i=0; i<list.size(); i++) {
            if (num < list.get(i)) {
                break;
            }
        }
        list.add(i, num);
    }
    System.out.print(list.get(0));
}

public Double GetMedian() {
    if (list.size()%2 == 0) {
        int left = (list.size()-1) / 2;
        int right = left + 1;
        return (list.get(left) + list.get(right)) / 2.0;
    } else {
        int middle = (list.size() - 1) / 2;
        return (double)list.get(middle);
    }
}