Sorting

排序算法：

归并：

原理：

归并排序：采用归并的思想，分治策略。
将数据不断的进行二分，直到二分为仅一个数。回溯，两个数进行归并之后，回溯，进行四个数据的归并。在归并时根据要求按顺序合并。依次回溯至迭代起点，归并排序就已完成。

归并的过程：就是将两组顺序的数据，根据数据的大小顺序存入连续内存空间，从而使得数据有序。

代码：

package javatest.sort;

/**
 * @description: 
 * @modifyContent:
 * @author: Maple Chan
 * @date: 2020-08-07 10:30:23
 * @version: 0.0.1
 */
public class MergeSort {
    public int[] mergeSort(int nums[]) {
        return mergeSortCore(nums, 0, nums.length - 1);
    }

    /**
     * 对数据进行二分，直到只有一个数据的时候，返回进行合并。
     * 时间复杂度nlogn,空间复杂度n
     * (空间可以想办法做到常数么？？)
     * @param nums
     * @param left
     * @param right
     * @return
     */
    public int[] mergeSortCore(int nums[], int left, int right) {
        if (left == right) {
            return new int[] { nums[left] };
        }
        int mid = (right - left) / 2 + left;

        return merge(mergeSortCore(nums, left, mid), mergeSortCore(nums, mid + 1, right));

    }

    public int[] merge(int[] nums1, int[] nums2) {
        int[] ret = new int[nums1.length + nums2.length];

        int index1 = 0;
        int index2 = 0;

        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] < nums2[index2]) {
                ret[index1 + index2] = nums1[index1];
                index1++;
            } else {
                ret[index1 + index2] = nums2[index2];
                index2++;
            }
        }
        while (index1 < nums1.length) {
            ret[index1 + index2] = nums1[index1];
            index1++;
        }
        while (index2 < nums2.length) {
            ret[index1 + index2] = nums2[index2];
            index2++;
        }
        return ret;
    }

    public static void main(String[] args) {
        /**
         * Test
         */
        int [] nums = new int[]{
            3,5,6,8,7,2
        };
        MergeSort mergeSort = new MergeSort();
        nums = mergeSort.mergeSort(nums);
    }
}

快速排序

参考：

白话经典算法系列之六快速排序快速搞定

快速排序用了递归、二分等思想进行实现。

思路：

定义左右指针。left和right。

①选取一个基数。下方代码采用选取第一个的方式，可以随机选择，选取中间的。

②left<right的条件下：从后往前，找到第一个比基数小的数（根据升降序定，这里输出升序）。填入left的位置。

③left<right的条件下：从前往后，找到第一个比基数大的数，填入right的位置

重复②③两步。

一次比较完之后（0(n)），从 left位置左侧都是比基数小的数，右侧都是比基数大的数。

上述步骤划分出左右两块，分别进行上述过程，及递归（因为二分了，时间复杂度0( n*log(n) )）。

快速排序在最坏的情况下，时间复杂度是log(n^2)，平均时间复杂度nlog(n)。

快速排序不是稳定排序，在排序过程中相对位置正确的两个数位置依旧可能被替换导致相对位置不是升序（降序）方向。

package javatest;

/**
 * @description: 快速排序实现
 * @modifyContent:
 * @author: Maple Chan
 * @date: 2020-07-28 09:22:54
 * @version: 0.0.1
 */
public class SortQuickSort {
    /**
     * 对数组进行快速排序,升序
     */
    public static void main(String[] args) {
        int[] nums = { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85, };

        SortQuickSort sort = new SortQuickSort();
        sort.quickSort(nums, 0, nums.length - 1);
    }

    public void quickSort(int[] nums, int leftSide, int rightSide) {
        // 思路，二分。
        if (leftSide >= rightSide) {
            return;
        }
        int left = leftSide;
        int right = rightSide;

        int pivot = nums[left];

        while (left < right) {

            while (left < right && nums[right] > pivot) {
                right--;
            }
            if (left < right) {
                nums[left] = nums[right];
            }

            while (left < right && nums[left] <= pivot) {
                left++;
            }
            if (left < right) {
                nums[right] = nums[left];
            }
        }
        nums[left] = pivot;

        quickSort(nums, leftSide, left - 1);
        quickSort(nums, left + 1, rightSide);
    }
}

堆排序

参考：

十大经典排序算法（动图演示）

堆排序的主要思路：

如果需要升序，则需要利用最大堆。

首先，为数据构建最大堆。
然后，从后往前遍历，将0位置与i位置进行交换
再然后，为len-1长度的数组进行堆排序，将这部分最大的交换到index=0的位置。
重复2-3，一直到每个节点遍历结束，就达到了升序的要求。

package javatest.sort;

/**
 * @description:
 * @modifyContent:
 * @author: Maple Chan
 * @date: 2020-08-23 14:13:41
 * @version: 0.0.1
 */
public class MaximumHeapTest {
    public static void main(String[] args) {
        int[] nums = { 5, 6, 9, 8, 1, 2, 3, 4, 7, 10 };
        int size = 10;

        MaxHeap heap = new MaxHeap();

        // heap.buildMaxHeap(nums);
        heap.sortMaxHeap(nums);
    }
}

class MaxHeap {

    public void buildMaxHeap(int[] nums) {
        int len = nums.length;

        for (int i = len / 2; i >= 0; i--) {
            //构建最堆的时候，需要从len/2位置开始往前遍历，这样能保证，每个子节点都小于其父节点。
            maxHeapify(nums, i, len);
        }
    }

    public void sortMaxHeap(int[] nums) {
        int len = nums.length;
        buildMaxHeap(nums);

        for (int i = len - 1; i >= 0; i--) {
            swap(nums, 0, i);
            maxHeapify(nums, 0, --len);
        }
    }

    /**
     * 从index位置至size-1位置进行大顶堆化。
     * 
     * @param nums
     * @param leftSize
     */
    public void maxHeapify(int[] nums, int index, int size) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;
        int largest = index;

        if (left < size && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < size && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != index) {
            swap(nums, largest, index);
            maxHeapify(nums, largest, size);
        }
    }

    public void maxHeapifyIterator(int[] nums, int index) {
        int left = index * 2 + 1;
        int right = index * 2 + 2;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}