[臥龍鳳雛]睡眠排序和隨機排序

注意：以下排序不要用於生產環境

1. 睡眠排序

1.1 簡介

睡眠排序（Sleep Sort）是一個非常有趣且奇特的排序演演算法，第一次看到就大吃一驚。睡眠排序並不是一個實際可用於大規模資料排序的演演算法，而更像是一種程式設計趣味或者電腦科學的玩笑。原理基於多執行緒和睡眠的概念，不是傳統的比較排序演演算法。

睡眠排序的主要思想是將待排序的一組整數分配給多個執行緒，每個執行緒負責處理一個整數，它們根據整數的值來設定睡眠時間。整數越小，睡眠時間越短，整數越大，睡眠時間越長。當所有執行緒都完成睡眠後，它們按照睡眠時間的長短排列，從而實現排序。

主要思路：

建立一個陣列，其中包含待排序的整數。
對於陣列中的每個整數，建立一個執行緒來處理它。
每個執行緒計算自己要休眠的時間，通常是整數值乘以一個常數，以確保休眠時間的差異。
所有執行緒同時開始休眠。
當一個執行緒醒來後，它將自己的整數放入一個結果陣列中。
重複步驟4和步驟5，直到所有執行緒都完成。
最後，結果陣列中的整數按照休眠時間的升序排列，即得到排序後的結果。

限制：

不穩定性：由於執行緒的排程和休眠不穩定，這個演演算法不保證排序的穩定性。
效率問題：演演算法的效率極低，它的時間複雜度可以達到O(n^2)級別，這在實際應用中不可接受。
負整數問題：如果待排序陣列包含負整數，那麼這個演演算法會在負整數的執行緒上休眠很長時間，導致等待時間非常長。

1.2 程式碼實現

import java.util.Random;
import java.util.concurrent.CountDownLatch;

public class SleepSort {
    public static void main(String[] args) throws InterruptedException {

        int count = 100;

        int[] nums = new int[count];
        Random random = new Random();
        // 限制程式不要過早中斷
        CountDownLatch countDownLatch = new CountDownLatch(count);
        // 隨機 100 個 1 - (10 * count) 的數
        for (int i = 0; i < count; i++) {
            nums[i] = random.nextInt(1, 10 * count);
        }
        // 開啟虛擬執行緒，延遲一定時間後列印數位
        for (int i = 0; i < count; i++) {
            int num = nums[i];
            Thread.startVirtualThread(() -> {
                try {
                    Thread.sleep(10L * num);
                } catch (InterruptedException e) {
                    throw new RuntimeException(e);
                }
                System.out.println(num);
                countDownLatch.countDown();
            });
        }
        countDownLatch.await();
    }
}

2. 隨機排序（猴子排序）

2.1 簡介

隨機排序，也稱為亂序排序（Random Sort）、洗牌排序（Shuffle Sort）或猴子排序（Monkey Sort），特點是將待排序的元素隨機排列。

主要思路：

輸入待排序的元素組成的列表或陣列。
對於列表中的每個元素，生成一個亂數或隨機權重，並將元素與其對應的亂數關聯。
根據亂數對元素進行排序。這通常可以使用標準的排序演演算法，如快速排序或歸併排序，但比較的標準是元素的亂數而不是元素本身的值。
完成排序後，元素就會以隨機的順序排列。

限制：

隨機性：由於亂數的引入，每次隨機排序的結果都會不同，即使相同的輸入資料也會產生不同的輸出。
不穩定性：隨機排序通常不保證排序的穩定性，因為它完全依賴於亂數。
低效性：隨機排序的時間複雜度通常較高，取決於用於排序的具體演演算法。這遠不如許多其他排序演演算法，因此不適合大規模資料集的排序任務。

2.2 程式碼實現

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.CountDownLatch;

public class RandomSort {
    public static void main(String[] args) throws InterruptedException {
        // 這個數建議不要太大，不然要隨機好久
        int count = 5;
        Random random = new Random();
        // 限制主執行緒不要退出
        CountDownLatch countDownLatch = new CountDownLatch(1);
        int[] nums = new int[count];
        for (int i = 0; i < count; i++) {
            nums[i] = random.nextInt(10);
        }
        int[] sortedNums = Arrays.copyOf(nums, nums.length);
        // 這裡偷懶直接用sort方法，然後在下面直接判斷
        Arrays.sort(sortedNums);
        long startTime = System.currentTimeMillis();
        // 這裡開一百萬個虛擬執行緒隨機
        for (int i = 0; i < 1000000; i++) {
            Thread.startVirtualThread(() -> {
                while (countDownLatch.getCount() > 0){
                    int[] tmp = new int[count];
                    for (int j = 0; j < count; j++) {
                        tmp[j] = random.nextInt(10);
                    }
                    // 可以列印中間過程的輸出
                    // System.out.println(Arrays.toString(tmp));
                    if (Arrays.equals(sortedNums, tmp)){
                        System.out.println("排序完畢:未排序資料" + Arrays.toString(nums));
                        System.out.println("排序完畢:已排序資料" + Arrays.toString(tmp));
                        countDownLatch.countDown();
                        break;
                    }
                }
            });
        }
        countDownLatch.await();
        // 計算總時間
        System.out.println(System.currentTimeMillis() - startTime);
    }
}

3. 總結

這兩個排序演演算法可以說是排序演演算法界的臥龍鳳雛，建議大家還是不要在生產環境使用。