在SS算法中，我们为输入数组中的每个元素创建不同的线程，然后每个线程休眠一段时间，该时间量与相应的数组元素的值成比例。
因此，最少睡眠时间的线程将首先被唤醒并且打印出来，然后是第二最小元素，依此类推。最长的元素在最后醒来，然后元素在最后被打印出来。因此输出是有序的。
所有这些多线程过程都发生在后台和操作系统的核心。我们对背景中发生的事情一无所知，因此这是一种“神秘”的排序算法。
示例：假设(为方便起见)我们的计算机速度需要3秒才能完成对所有元素的排序：
INPUT: 8 2 9
3s: sleep 8
6s: sleep 2
8s: "2" (2 wakes up so print it)
9s: sleep 9
11s: "8" (8 wakes up so print it)
18s: "9" (9 wakes up so print it)
OUTPUT: 2 8 9实现
为了实现sleep排序，我们需要调用多线程函数，例如_beginthread()和WaitForMultipleObjects()。因此我们需要包含windows.h来使用这些函数。我们必须在PC上运行它(注意这段代码是针对WINDOWS而不是针对LINUX)。
要执行睡眠排序，我们需要为输入数组中的每个值创建线程。我们使用_beginthread()函数执行此操作 。
在每个线程中，我们分配两个指令：
睡眠：将此线程休眠直到
arr[i]毫秒(其中arr[i]是与该线程关联的数组元素)。我们使用Sleep()函数执行此操作。Sleep(n)函数暂停与此线程关联的活动，直到’n’毫秒。因此，如果我们写Sleep(1000)，那么这意味着线程将休眠1秒(1000毫秒= 1秒)打印：当线程在睡眠后’唤醒’然后打印数组元素与此线程关联的
arr[i]。
创建线程后，我们处理这些线程。我们使用WaitForMultipleObjects()来做到这一点。
// C implementation of Sleep Sort
#include <stdio.h>
#include <windows.h>
#include <process.h>
// This is the instruction set of a thread
// So in these threads, we "sleep" for a particular
// amount of time and then when it wakes up
// the number is printed out
void routine(void *a)
{
int n = *(int *) a; // typecasting from void to int
// Sleeping time is proportional to the number
// More precisely this thread sleep for 'n' milliseconds
Sleep(n);
// After the sleep, print the number
printf("%d ", n);
}
/* A function that performs sleep sort
_beginthread() is a C run-time library call that creates a new
'thread' for all the integers in the array and returns that
thread.
Each of the 'thread' sleeps for a time proportional to that
integer and print it after waking.
We pass three parameters to _beginthread :-
1) start_address --> start address of the routine/function
which creates a new thread
2) stack_size --> Stack Size of the new thread (which is 0)
3) arglist --> Address of the argument to be passed
The return value of _beginthread() function is a handle to the
thread which is created. So we must accept is using the datatype-
'HANDLE' which is included in windows.h header
'HANDLE' datatype is used to represent an event/thread/process etc
So 'HANDLE' datatype is used to define a thread
We store the threads in an array - threads[] which is declared
using 'HANDLE' datatype.
WaitForMultipleObjects() is a function that processes the threads
and has four arguments-
1) no_of_threads --> Number of threads to be processed
2) array_of_threads --> This is the array of threads which should be
processed. This array must be of the type
'HANDLE'
3) TRUE or FALSE --> We pass TRUE if we want all the threads in the
array to be processed
4) time_limit --> The threads will be processed until this time limit
is crossed. So if we pass a 0 then no threads will
be processed, otherwise if we pass an INFINITE, then
the program will stop only when all the threads
are processed. We can put a cap on the execution
time of the program by passing the desired time
limit */
void sleepSort(int arr[], int n)
{
// An array of threads, one for each of the elements
// in the input array
HANDLE threads[n];
// Create the threads for each of the input array elements
for (int i = 0; i < n; i++)
threads[i] = (HANDLE)_beginthread(&routine, 0, &arr[i]);
// Process these threads
WaitForMultipleObjects(n, threads, TRUE, INFINITE);
return;
}
// Driver program to test above functions
int main()
{
// Doesn't work for negative numbers
int arr[] = {34, 23, 122, 9};
int n = sizeof(arr) / sizeof(arr[0]);
sleepSort (arr, n);
return(0);
}限制
1)此算法不适用于负数，因为线程无法在负时间内休眠。
2)由于该算法依赖于输入元素，因此输入数组中的大量数字导致该算法急剧减速(因为与该数字相关联的线程必须长时间休眠)。因此，即使输入数组元素仅包含2个元素，例如 -{1,100000000}，我们也必须等待更长的持续时间才能进行排序。
3)该算法每次都不产生正确的排序输出。这通常发生在输入数组中非常大的数字左边有一个非常小的数字时。
例如 - {34,23,1,12253,9}。
睡眠排序后的输出为{9,1,23,34,1223}
当输入数组最初反向排序时，也会出现错误的输出，例如 - {10,9,8,7,6,5}。
这种意外输出的原因是因为扫描每个元素以及一些其他OS操作(例如将每个线程插入优先级队列中进行调度)之间需要花费一些时间。我们不能简单地忽略这些事情所花费的时间。
我们使用下面的例子来描述这种情况，假设(为方便起见)我们的计算机速度需要3秒才能完成对所有元素的排序：
INPUT: 10 9 8 7 6 5
3s: sleep 10
6s: sleep 9
9s: sleep 8
12s: sleep 7
13s: "10" (10 wakes up so print it)
15s: sleep 6
15s: "9" (9 wakes up so print it)
17s: "8" (8 wakes up so print it)
18s: sleep 5
19s: "7" (7 wakes up so print it)
21s: "6" (6 wakes up so print it)
23s: "5" (5 wakes up so print it)
OUTPUT: 10 9 8 7 6 5以上输出只是一个例子。
显然，现代计算机计算机并不是那么慢(需要3秒才能扫描每个元素)。
实际上，上面的输入在现代计算机上运行睡眠排序会产生输出 - {9,5,7,10,8,6}
如何解决这个问题？
1)我们可以通过对新输出重复进行睡眠排序来解决此问题，直到输出变为排序。每次它都会更准确地对元素进行排序。
2)由于其他操作系统工作所花费的时间和扫描每个元素所发生的错误输出。
在我们的程序中，我们使用了函数Sleep(arr[i])，这意味着与数组元素相关联的每个线程都会休眠arr[i]毫秒。由于毫秒是一个非常小的数量，其他OS任务可能比arr[i]毫秒花费更多的时间，这最终可能导致睡眠排序错误。将睡眠时间增加10倍就可以提供排序输出，因为OS任务将在这么多睡眠之间完成所有任务，因此不会产生任何错误。
如果我们使用Sleep(10 * arr[i])而不是Sleep(arr[i])那么我们肯定会获得比后者更精确的输出。例如，输入数组 - {10,9,8,7,6,5}将给出正确的排序输出 - {5,6,7,8,9,10}如果我们使用Sleep(10 * arr[i])而不仅仅是睡眠(arr[i])秒。
但是，对于某些测试用例，Sleep(10 * arr[i])仍然可能会给出错误的结果。为了使它更精确，增加睡眠时间，比如Slepp(20 * arr[i])。
因此，结论就是睡眠时间越长，结果越准确。(听起来很有趣，嗯？)。但同样会增加此算法的运行时间。
时间复杂性
尽管关于睡眠排序的时间复杂性存在许多不同的观点，但我们可以使用以下推理来估计时间复杂度
由于Sleep()函数和创建多个线程是由OS在内部使用优先级队列(用于调度目的)完成的。因此，在优先级队列中插入所有数组元素需要 $O(Nlog N)$ 的时间。此外，只有在处理完所有线程时才获得输出，即当所有元素都被唤醒时。因为它需要 $O(arr[i])$ 时间来唤醒第i个数组元素的线程。因此，唤醒阵列的最大元素需要最多 $O(max(输入))$ 。因此，总时间复杂度可以假设为 $O(NlogN + max(输入))$ ，
其中，N =输入数组中元素的数量，输入=输入数组元素
辅助空间
所有操作都由OS的内部优先级队列完成。因此可以忽略辅助空间。
结论
睡眠排序与操作系统的关系比任何其他排序算法都要多。这种排序算法是OS完成的多线程和调度的完美演示。
java implementation
public class SleepSort {
public static void main(String[] args){
int[] nums={9,7,2,6,15,8,9,9,9,9,9};
SleepSort.sort(nums);
for(int n:nums)
System.out.printf("%d ",n);
}
public static void sort(int[] nums){
Sleeper.idx=0;
Sleeper.output=new int[nums.length];
for(int i=0;i<nums.length;i++) //[1]
new Sleeper(nums[i]).start();
try {
Thread.sleep(100); //[2]
} catch (InterruptedException e) {
e.printStackTrace();
}
for(int i=0;i<nums.length;i++)
nums[i]=Sleeper.output[i];
}
}
class Sleeper extends Thread{
public static int[] output;
public static int idx;
private int sleep_time;
public Sleeper(){
this.sleep_time=0;
}
public Sleeper(int sleep_time){
this.sleep_time=sleep_time;
}
@Override
public void run(){
try{
Thread.sleep(this.sleep_time);
}catch(InterruptedException e){
e.printStackTrace();
}
output[idx++]=this.sleep_time;
}
}
