背景

通過對(duì)常見排序的規(guī)則了解涣易，按照自己理解實(shí)現(xiàn)。其實(shí)部分代碼可再簡(jiǎn)化缨硝，為了更好的體現(xiàn)自己的實(shí)現(xiàn)步驟就沒簡(jiǎn)化击罪，這樣有利于之后回顧思路乌妒。

常見排序

• 冒泡排序
• 選擇排序
• 快速排序
• 歸并排序
• 堆排序

import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

/**
 * @author XiaoJia
 * @since 2020/5/3 21:21
 */
public class SimpleSortTest {
    int[] numbers;

    @Before
    public void before() {
        numbers = new int[]{0, 8, 7, 6, 5, 3, 4, 9, 2, 1};
    }

    @After
    public void after() {
        Assert.assertEquals(Arrays.toString(numbers), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
    }

    /**
     * 冒泡排序
     * <p>
     * 規(guī)則：按照升序（或降序）每次從第一個(gè)元素開始選出最大（或最小）的數(shù)
     * <p>
     * 時(shí)間復(fù)雜度：(n-1)+(n-2)+...+1 = n(n-1) / 2 看做 n^2
     */
    @Test
    public void bubbleSort() {
        // 每次獲取最大數(shù)的填充位置 i
        for (int i = numbers.length - 1; i > 0; i--) {
            // 正在比較的數(shù)外邓，通過交換位置保持比較結(jié)果
            for (int j = 0; j < i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    int temp = numbers[j + 1];
                    numbers[j + 1] = numbers[j];
                    numbers[j] = temp;
                }
            }
        }
    }

    /**
     * 選擇排序
     * <p>
     * 規(guī)則：依次為每個(gè)位置選擇最小的數(shù)組（相對(duì)冒泡排序無需不必要的數(shù)據(jù)位置交換）
     * <p>
     * 時(shí)間復(fù)雜度：(n-1)+(n-2)+...+1 = n(n-1) / 2 看做 n^2
     */
    @Test
    public void selectSort() {
        // 每次存放選擇結(jié)果的位置 - i
        for (int i = 0; i < numbers.length - 1; i++) {
            // 存放臨時(shí)比較的最大值與下標(biāo)
            int temp = numbers[i];
            int tempIndex = i;
            // 比較兩個(gè)數(shù)得較小值
            for (int j = i + 1; j < numbers.length; j++) {
                if (temp > numbers[j]) {
                    temp = numbers[j];
                    tempIndex = j;
                }
            }
            numbers[tempIndex] = numbers[i];
            numbers[i] = temp;
        }
    }

    /**
     * 快速排序
     * <p>
     * 規(guī)則：將數(shù)據(jù)拆分左右兩個(gè)集合撤蚊，左邊集合所有元素必須都小于右邊集合。如果集合元素大于1則按相同規(guī)則繼續(xù)拆分
     * <p>
     * 時(shí)間復(fù)雜度：
     * 1. 最壞情況：每次拆分左邊集合都只有一個(gè)元素损话，則時(shí)間復(fù)雜度與冒泡一樣 n(n-1) / 2
     * 2. 最好情況：每次拆分左右集合元素相仿侦啸，則經(jīng)過 log2(n) 次則拆分完成，每次拆分都會(huì)進(jìn)行 n-1 次比較
     * 故 時(shí)間復(fù)雜度為 (n-1)log2(n) 看做 nlog2(n)
     */
    @Test
    public void quickSort() {
        // 選擇第一個(gè)元素作為拆分元素丧枪，小于該元素則與其交互位置
        quickSplit(0, numbers.length - 1);
    }

    /**
     * 歸并排序
     * <p>
     * 規(guī)則：分為兩個(gè)步驟
     * 步驟一：拆分?jǐn)?shù)據(jù)光涂，每次將數(shù)據(jù)均分兩個(gè)集合，直到集合元素個(gè)數(shù)為1
     * 步驟二：合并數(shù)據(jù)拧烦，依次從元素小的集合合并成較大的有序集合忘闻，直到所有集合都被合并
     * <p>
     * 時(shí)間復(fù)雜度：數(shù)據(jù)拆分次數(shù)為log2(n)，最壞情況是每個(gè)元素歸并時(shí)都需要比較一次恋博，
     * 故 時(shí)間復(fù)雜度為 (n-1)log2(n)
     */
    @Test
    public void mergeSort() {
        int[] result = new int[numbers.length];
        mergeSplitAndMerge(result, 0, numbers.length - 1);
    }

    /**
     * 堆通常是一個(gè)可以被看做一棵樹的數(shù)組對(duì)象齐佳。堆總是滿足下列性質(zhì)：
     * 1、堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值债沮；
     * 2炼吴、堆總是一棵完全二叉樹。
     * <p>
     * 堆排序
     * <p>
     * 規(guī)則：先將無序集合調(diào)整為符合堆規(guī)范的集合疫衩，再將堆頂元素作為已排好序的數(shù)填充到指定位置（從最后位置到第一個(gè)位置依次填充）
     * 最大堆：父節(jié)點(diǎn)總大于或等于左右節(jié)點(diǎn)
     * 最小堆：父節(jié)點(diǎn)總小于或等于左右節(jié)點(diǎn)
     * <p>
     * 時(shí)間復(fù)雜度：log2(n) + log2(n-1) + ... + log2(1) = log2(n) * n / 2 看做 nlog2(n)
     */
    @Test
    public void headSort() {
        // 從最后一個(gè)非葉子節(jié)點(diǎn)從下往上硅蹦、從右往左依次獲取最大的父節(jié)點(diǎn)（最后一個(gè)元素的父節(jié)點(diǎn)為最后一個(gè)非葉子節(jié)點(diǎn)）
        for (int i = numbers.length / 2 - 1; i >= 0; i--) {
            adjustNode(i, numbers[i], numbers.length);
        }

        // 依次將通過堆獲取的最大值保存到當(dāng)次排序值的末尾，然后從上往下、從左往右依次獲取最大的父節(jié)點(diǎn)
        for (int i = numbers.length - 1; i > 0; i--) {
            int temp = numbers[0];
            numbers[0] = numbers[i];
            numbers[i] = temp;
            adjustNode(0, numbers[0], i);
        }
    }

    private void quickSplit(int begin, int end) {
        if (begin >= end) {
            return;
        }

        // 記錄當(dāng)前拆分標(biāo)準(zhǔn)的位置
        int compare = numbers[begin];
        // 記錄開始切分的位置
        int splitIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (compare > numbers[i]) {
                splitIndex++;
                // 判斷是否交互位置
                if (splitIndex != i) {
                    int temp = numbers[i];
                    numbers[i] = numbers[splitIndex];
                    numbers[splitIndex] = temp;
                }
            }
        }

        // 拆分標(biāo)準(zhǔn)的位置與最后一個(gè)小于拆分標(biāo)準(zhǔn)的調(diào)換位置
        if (splitIndex != begin) {
            int temp = numbers[splitIndex];
            numbers[splitIndex] = numbers[begin];
            numbers[begin] = temp;
        }

        quickSplit(begin, splitIndex - 1);
        quickSplit(splitIndex + 1, end);
    }

    private void mergeSplitAndMerge(int[] temp, int begin, int end) {
        if (begin >= end) {
            return;
        }

        // 拆分并合并子數(shù)據(jù)
        int splitIndex = begin + (end - begin + 1) / 2 - 1;
        mergeSplitAndMerge(temp, begin, splitIndex);
        mergeSplitAndMerge(temp, splitIndex + 1, end);

        // 合并數(shù)據(jù)
        int firstIndex = begin;
        int secondIndex = splitIndex + 1;
        for (int i = begin; i <= end; i++) {
            if (numbers[firstIndex] < numbers[secondIndex]) {
                temp[i] = numbers[firstIndex];
                firstIndex++;
            } else {
                temp[i] = numbers[secondIndex];
                secondIndex++;
            }

            // 任何一個(gè)集合全部已排序則將另一個(gè)集合的未排序元素直接拷貝到目標(biāo)集合中
            if (firstIndex > splitIndex) {
                System.arraycopy(numbers, secondIndex, temp, i + 1, end - i);
                break;
            } else if (secondIndex > end) {
                System.arraycopy(numbers, firstIndex, temp, i + 1, end - i);
                break;
            }
        }

        System.arraycopy(temp, begin, numbers, begin, end - begin + 1);
    }

    private void adjustNode(int index, int value, int length) {
        int temp = index;
        while (true) {
            int leftIndex = 2 * (temp + 1) - 1;
            int rightIndex = 2 * (temp + 1);
            // 左右節(jié)點(diǎn)的較大值
            int maxIndex;
            if (leftIndex > length - 1) {
                break;
            } else if (rightIndex > length - 1) {
                maxIndex = leftIndex;
            } else {
                maxIndex = numbers[leftIndex] > numbers[rightIndex] ? leftIndex : rightIndex;
            }
            // 與父節(jié)點(diǎn)的比較童芹，如果父節(jié)點(diǎn)小于子節(jié)點(diǎn)則需要已子節(jié)點(diǎn)作為父節(jié)點(diǎn)再次更新
            if (numbers[maxIndex] > value) {
                numbers[temp] = numbers[maxIndex];
                numbers[maxIndex] = value;
                temp = maxIndex;
            } else {
                break;
            }
        }
    }
}