[数据结构与算法]2021-07-25

使用java实现常见的排序算法

冒泡排序(Bubble Sort)

?冒泡排序关键在于比较相邻位置的数据，将逆序并且相邻的数据交换位置，每一次比较最大值都会往上浮，该种排序空间复杂度为O(1)，时间复杂度为O($n^2$)。

public class BubbleSortImpl implements Sort {
    @Override
    public void sort(int[] nums) {
        for (int index = 0; index < nums.length; index++) {
            for (int secondIndex = 0; secondIndex < nums.length - 1 - index; secondIndex++) {
                if (nums[secondIndex] > nums[secondIndex + 1]) {
                    swap(nums, secondIndex, secondIndex + 1);
                }
                // 排序过程
                System.out.println(secondIndex + ":" + Arrays.toString(nums));
            }
        }
    }
}

选择排序(Choose Sort)

?选择排序关键在于通过遍历找到最小值，每次遍历标记最小值位置，然后将其和起始点交换，反向思考也可以优先找出最大值，该种排序空间复杂度为O(1)，时间复杂度为O($n^2$)。

public class ChooseSortImpl implements Sort {
    @Override
    public void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                swap(nums, i, minIndex);
            }
            // 排序过程
            System.out.println(i + "-" + minIndex + ":" + Arrays.toString(nums));
        }
    }
}

最大堆排序(Heap Sort)

?最大堆是一种完全二叉树结构，其关键在于构建一颗父节点不小于子节点的最大堆，每次构建最大堆之后最大值处于根节点的位置，将该值交换到最大堆的末端节点，重新构建最大堆，直到根节点为止，堆排序的空间复杂度为O(1)，时间复杂度为O($nlogn$)

public class HeapSortImpl implements Sort {
    @Override
    public void sort(int[] nums) {
        // 初始化最大堆
        for (int i = (nums.length >> 1) - 1; i >= 0; i--) {
            adjustHeap(nums, i, nums.length);
            System.out.println(Arrays.toString(nums));
        }

        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, 0, i);
            adjustHeap(nums, 0, i);
        }
    }

    /**
     * @param nums 数组
     * @param now  当前节点
     * @return void
     * @description 从第一个非叶子节点开始构建
     * @author shtao
     * @date 18:43 2021/7/25
     **/
    private void adjustHeap(int[] nums, int now, int last) {
        int swap = nums[now];
        for (int i = (now << 1) + 1; i < last; i = (i << 1) + 1) {
            if (i + 1 < last && nums[i] < nums[i + 1]) {
                i++;
            }
            if (nums[i] > swap) {
                nums[now] = nums[i];
                now = i;
            } else {
                break;
            }
        }
        nums[now] = swap;
    }
}

快排（Quick Sort）

?快排的思想在于选择一个值x，将比该值小的数挪到x的左边，将比x大的数挪到x右边，再采用相同的方法对x左右两边进行重排序。快排序的空间复杂度为O(1)，时间复杂度为O($nlogn$)

public class QuickSortImpl implements Sort {
    @Override
    public void sort(int[] nums) {
        int left = 0;
        quickSort(nums, left, nums.length - 1);
    }

    /**
     * @description 快排
     * @author shtao
     * @date 21:10 2021/7/25
     * @param nums 数组
     * @param left 左边界
     * @param right 右边界
     * @return void
     **/
    private void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int beginIndex = left;
        int rightIndex = right;
        int swapNum = nums[left];
        while (beginIndex < rightIndex) {
            while (beginIndex < rightIndex && nums[rightIndex] >= swapNum) {
                rightIndex--;
            }
            nums[beginIndex] = nums[rightIndex];
            while (beginIndex < rightIndex && nums[beginIndex] <= swapNum) {
                beginIndex++;
            }
            nums[rightIndex] = nums[beginIndex];
        }
        nums[beginIndex] = swapNum;
        System.out.println(Arrays.toString(nums));
        quickSort(nums, left, beginIndex - 1);
        quickSort(nums, rightIndex + 1, right);
    }
}

归并排序（Merge Sort）

?归并排序的关键在于分冶-归并，首先将数组分冶为单个元素，然后将这些元素作为有序数组合并，最后归并完成后数组变得有序。归并排序的空间复杂度为O(n)，时间复杂度为O($nlogn$)

public class MergeSortImpl implements Sort {
    @Override
    public void sort(int[] nums) {
        sort(nums, 0, nums.length - 1, new int[nums.length]);
    }

    /**
     * @param nums       数组
     * @param beginIndex 起点
     * @param endIndex   终点
     * @param temp       交换数组
     * @return void
     * @description 归并过程，分->合
     * @author shtao
     * @date 20:50 2021/7/25
     **/
    private void sort(int[] nums, int beginIndex, int endIndex, int[] temp) {
        if (beginIndex < endIndex) {
            int mid = (beginIndex + endIndex) >> 1;
            sort(nums, beginIndex, mid, temp);
            sort(nums, mid + 1, endIndex, temp);
            merge(nums, beginIndex, mid, endIndex, temp);
        }
    }

    /**
     * 合并两个有序数组
     *
     * @param nums       数组
     * @param beginIndex 起始点
     * @param endIndex   结束点
     * @param temp       交换用的数组
     * @return void
     * @author shtao
     * @date 20:48 2021/7/25
     **/
    private void merge(int[] nums, int beginIndex, int mid, int endIndex, int[] temp) {
        int tempIndex = 0;
        int i = beginIndex;
        int j = mid + 1;
        while (i <= mid && j <= endIndex) {
            if (nums[i] < nums[j]) {
                temp[tempIndex++] = nums[i++];
            } else {
                temp[tempIndex++] = nums[j++];
            }
        }
        while (i <= mid) {
            temp[tempIndex++] = nums[i++];
        }
        while (j <= endIndex) {
            temp[tempIndex++] = nums[j++];
        }
        tempIndex = 0;
        while (beginIndex <= endIndex) {
            nums[beginIndex++] = temp[tempIndex++];
        }
    }
}

附录

接口类

public interface Sort {
    /**
     * @param nums 数组
     * @return void
     * @description 排序
     * @author shtao
     * @date 14:16 2021/7/25
     **/
    void sort(int[] nums);

    /**
     * 交换位置
     *
     * @param nums   数组
     * @param index1 index1
     * @param index2 index2
     **/
    default void swap(int[] nums, int index1, int index2) {
        int swap = nums[index2];
        nums[index2] = nums[index1];
        nums[index1] = swap;
    }
}