排序复习

更多请参考:

Sorting algorithm - Wikipedia

排序算法 - 维基百科,自由的百科全书

中英文内容略有差别,其中中文没有最好情况,但是在复杂度、稳定性的比较中考虑了是用数组还是链表存储。

复杂度及稳定性

排序方式平均时间复杂度最好时间复杂度最坏时间复杂度辅助空间稳定性
冒泡排序O(n^2)O(n)O(n^2)O(1)稳定
选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定
插入排序O(n^2)O(n)O(n^2)O(1)稳定
希尔排序O(n^(4/3))O(nlogn)O(n^(3/2))O(1)不稳定
快速排序O(nlogn)O(nlogn)O(n^2)O(logn)不稳定
堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定

实现

抽象类

所有排序类继承于抽象类Sort

import java.util.Arrays;

public abstract class Sort {
    protected int[] nums;

    public Sort(int[] nums) {
        this.nums = nums;
    }

    public void printNums(int i) {
        System.out.println("第"+i+"轮循环后:"+ Arrays.toString(nums));
    }

    public abstract int[] sort(boolean isDebug);
}

其中,nums数组用于存放被排序的数;sort方法用于实现排序,其中参数isDebug用于声明是否输出每一轮的结果;

printNums方法用于打印排序中间结果。

冒泡排序

传统冒泡排序

public class BubbleSort extends Sort {
    public BubbleSort(int[] nums) {
        super(nums);
    }

    @Override
    public int[] sort(boolean isDebug) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(j, j + 1);
                }
            }
            if (isDebug) {
                printNums(i);
            }
        }
        return nums;
    }

    public void swap(int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

记忆最后更改位置的冒泡排序

public class NewBubbleSort extends Sort {
    public NewBubbleSort(int[] nums) {
        super(nums);
    }

    @Override
    public int[] sort(boolean isDebug) {
        int compareTimes = nums.length - 1;
        for (int i = 0; i < nums.length - 1; i++) {
            int lastCompare = 0;
            for (int j = 0; j < compareTimes; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(j, j + 1);
                    lastCompare = j;
                }
            }
            compareTimes = lastCompare;
            if (isDebug) {
                printNums(i);
            }
            if (lastCompare == 0) {
                break;
            }
        }
        return nums;
    }

    public void swap(int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

}

选择排序

public class SelectionSort extends Sort {
    public SelectionSort(int[] nums) {
        super(nums);
    }

    @Override
    public int[] sort(boolean isDebug) {
        for (int i = 0; i < nums.length - 1; i++) {
            int minNumber = nums[i];
            int placeOfMinNumber = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < minNumber) {
                    minNumber = nums[j];
                    placeOfMinNumber = j;
                }
            }
            swap(i, placeOfMinNumber);
            if (isDebug)
                printNums(i);
        }
        return nums;
    }

    public void swap(int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

}

插入排序

public class InsertSort extends Sort{
    public InsertSort(int[] nums) {
        super(nums);
    }

    @Override
    public int[] sort(boolean isDebug) {
        for(int i=1;i<nums.length;i++) {
            int isSorted=i-1;
            int thisNum=nums[i];
            while (isSorted>=0) {
                if(thisNum<nums[isSorted]) {
                    nums[isSorted+1]=nums[isSorted];
                    isSorted--;
                } else {
                    break;
                }
            }
            nums[isSorted+1]=thisNum;
            if(isDebug)
                printNums(i);
        }
        return nums;
    }
}

希尔排序

public class ShellSort extends Sort {
    private StepListType stepListType;

    public enum StepListType {
        //https://en.wikipedia.org/wiki/Shellsort
        SHELL,
        FRANK_LAZARUS,
        HIBBARD
    }

    public ShellSort(int[] nums, StepListType stepListType) {
        super(nums);
        this.stepListType = stepListType;
    }

    @Override
    public int[] sort(boolean isDebug) {
        int length = nums.length;
        List<Integer> stepList = generateStepList(length, this.stepListType);
        for (int step : stepList) {
            for (int i = step; i < length; i++) {
                int isSorted = i - step;
                int thisNum = nums[i];
                while (isSorted >= 0 && thisNum < nums[isSorted]) {
                    nums[isSorted + step] = nums[isSorted];
                    isSorted -= step;
                }
                nums[isSorted + step] = thisNum;
                if (isDebug) {
                    this.printNums(step, i - step);
                }
            }
        }
        return nums;
    }

    public List<Integer> generateStepList(int length, StepListType type) {
        //生成步长
        switch (type) {
            case SHELL -> {
                List<Integer> list = new ArrayList<>();
                int step = length; //必须
                while (step != 1) {
                    step = (int) Math.floor(step / 2);
                    list.add(step);
                }
                return list;
            }
            case FRANK_LAZARUS -> {
                List<Integer> list = new ArrayList<>();
                int k = 1;
                int step = length; //没啥意义,大于1就行
                while (step != 1) {
                    step = (int) (2 * Math.floor(length / Math.pow(2, k + 1)) + 1);
                    list.add(step);
                    k++;
                }
                return list;
            }
            case HIBBARD -> {
                List<Integer> list = new ArrayList<>();
                int step = 1;
                int k = 1;
                while (step < length) {
                    list.add(step);
                    k++;
                    step = (int) (Math.pow(2, k) - 1);
                }
                Collections.reverse(list);
                return list;
            }
        }
        return Collections.EMPTY_LIST;
    }

    public void printNums(int step, int i) {
        System.out.println("步长为" + step + "的第" + i + "轮循环后:" + Arrays.toString(nums));
    }
}

快速排序

import java.util.Arrays;

public class QuickSort extends Sort {
    public QuickSort(int[] nums) {
        super(nums);
    }

    public int Partition(int low, int high) {
        int pivotKey = nums[high];
        int i = low;
        for (int j = low; j < high; j++) {
            if (nums[j] < pivotKey) {
                swap(i, j);
                i++;
            }
        }
        swap(i, high);
        return i;
    }

    public void RealQuickSort(int low, int high, boolean isDebug, int recursionDepth) {
        //如果不需要打印分步之类的信息,保留low/high就行了
        if (low < high) {
            int pivotLoc = Partition(low, high);
            if (isDebug) {
                this.printNums(recursionDepth);
            }
            RealQuickSort(low, pivotLoc - 1, isDebug, recursionDepth + 1);
            RealQuickSort(pivotLoc + 1, high, isDebug, recursionDepth + 1);
        }
    }


    @Override
    public int[] sort(boolean isDebug) {
        RealQuickSort(0, nums.length - 1, isDebug, 0);
        return nums;
    }

    public void swap(int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public void printNums(int recursionDepth) {
        System.out.println("递归深度为" + recursionDepth + "时:" + Arrays.toString(nums));
    }

}

堆排序

public class HeapSort extends Sort {

    public HeapSort(int[] nums) {
        super(nums);
    }

    private void heaptify(int parent, int length) {
        int temp = nums[parent];
        int child = 2 * parent + 1; // 左孩子
        while (child < length) {
            if (child + 1 < length && nums[child] < nums[child + 1]) {
                // 选左右孩子更大那个
                child = child + 1; //右孩子更大
            }
            if (temp >= nums[child]) {
                break;
            }
            nums[parent] = nums[child];
            parent = child; //从上而下调整
            child = 2 * child + 1;
        }
        nums[parent] = temp;
    }

    public void buildHeap() {
        int length = nums.length;
        for (int i = length / 2 - 1; i >= 0; i--) {
            // 从右往左,从下往上,从最右下的非叶子节点开始
            heaptify(i, length);
        }
    }


    @Override
    public int[] sort(boolean isDebug) {
        int length = nums.length;
        buildHeap();
        for (int i = length - 1; i > 0; i--) {
            // n-1次循环
            swap(0, i); //第一个元素和未排序的最后一个交换
            heaptify(0, i);
            if (isDebug) {
                printNums(i);
            }
        }
        return nums;
    }
}

分类总结

稳定性

稳定: 冒泡排序、插入排序

不稳定: 选择排序、快速排序、希尔排序、堆排序

平均时间复杂度

O(n^2): 冒泡排序、选择排序、插入排序

O(nlogn): 快速排序、堆排序

O(n^(4/3)): 希尔排序

辅助空间

O(1): 冒泡排序、选择排序、插入排序、堆排序

O(logn): 快速排序


排序复习
https://blog.loststar.tech/posts/e45aa11e/
作者
loststar
发布于
2021年11月28日
许可协议