排序复习

更多请参考：

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)： 快速排序