[数据结构]Extra 01 排序算法

其实是头两天看到一个视频，介绍了计算机领域的好几种排序算法，心血来潮准备好好学一下

Steven-Zhl 头像
[数据结构]Extra 01 排序算法

由于原视频的排序算法众多，且不少算法不仅难而且少见，所以可以预见的是，这又将会是个大坑，需要很长时间填…

1. 睡觉排序

给大家整个活，祝大家每天都能睡个好觉。

我在睡觉

1.1 原理介绍

  • 其思想是为每个未排序元素创建一个线程，并且根据元素值大小，阻塞对应线程一定的时间。这样，值较大的线程阻塞的时间长，较小的线程阻塞时间短，因此最终效果会按照从小到大的顺序输出。
  • 因为这种“阻塞线程”的函数通常都叫做sleep，所以这种排序方法被称为“睡觉排序”。
  • 直观理解就是“每个元素都在赛跑”，但是赛程不一样长，因此最先到达的就是最小的元素。

示意图

1.2 代码实现

以下是使用C、Python和JavaScript的代码实现：

  • C
#include <stdio.h>
#include <pthread.h>
#include <windows.h>

void sleepSortThread(int num) {
    Sleep(num);
    printf("%d\n", num);
}

void sleepSort(int *nums, int size) {
    pthread_t *threads = (pthread_t *) malloc(size * sizeof(pthread_t));
    for (int i = 0; i < size; i++)  // 初始化线程和数值
        pthread_create(&threads[i], NULL, (void *(*)(void *)) sleepSortThread, (void *) nums[i]);

    for (int i = 0; i < size; i++)  // 等待线程结束
        pthread_join(threads[i], NULL);
    free(threads);  // 释放内存
}

int main() {
    int size = 10;
    int nums[size];

    for (int i = 0; i < size; i++)
        nums[i] = rand() % 100;

    sleepSort(nums, size);
    return 0;
}
  • Python
from time import sleep
from threading import Thread
from typing import List
import random

def sleepSort(nums: List[int]):
    for num in nums:
        t = Thread(target=lambda num: (sleep(num * 0.001), print(num)), args=(num,))  # 创建线程
        t.start()  # 启动线程

sleepSort(random.sample(range(0, 100), k=10))
  • JavaScript
async function sleepSort(nums) {
    await Promise.all(nums.map(async (num) => {  // 创建线程
        await new Promise(handler => setTimeout(handler, num));
        console.log(num);
    }));
}

sleepSort(Array.from({ length: 10 }, () => Math.floor(Math.random() * 100)))
  • 效率对比

C语言的效率优势并不明显，不知道是不是我的写法有问题

编程语言 执行时间 输出结果
C 103ms C结果
Python 126ms Python结果
JavaScript 136ms JavaScript结果

2. 基于文件API的排序

其实这个排序算法比上一个更加生草

2.1 原理介绍

  • 当你使用某种编程语言的文件操作库时也许会注意到，你获取到的文件列表，其文件名是已经按照一定规则排好序的。
  • 那么我们可不可以利用这个特性，将实际排序的任务交给文件系统呢？所以就有了这个算法(实际上称不上算法)。

2.2 代码实现

以下是使用Python和JavaScript的代码实现：

  • Python
from typing import List
import os
import random

def fileSort(nums: List[int]):
    if not os.path.exists("temp"):
        os.mkdir("temp")
    fileLength = len(str(max(nums)))  # 获取最大值的长度，以保持文件名长度一致
    for i in nums:  # 创建文件
        open("temp/" + str(i).zfill(fileLength), "w").close()

    for i in os.listdir("temp"):
        print(i)
        os.remove("temp/" + i)

fileSort(random.sample(range(0, 100), k=10))
  • JavaScript
const fs = require('fs');
const path = require('path');

function fileSort(nums) {
    const temp = path.join(__dirname, 'temp');
    if (!fs.existsSync(temp)) fs.mkdirSync(temp);
    const fileLength = Math.max(...nums).toString().length;  // 获取最大值的长度，以保持文件名长度一致
    nums.forEach(num => {  // 创建空文件
        fs.closeSync(fs.openSync(path.join(temp, num.toString().padStart(fileLength, '0')), 'w'));
    });

    fs.readdirSync(temp).forEach(file => {  // 输出结果并删除文件
        console.log(file);
        fs.unlinkSync(path.join(temp, file));
    });
}

fileSort(Array.from({ length: 10 }, () => Math.floor(Math.random() * 100)));
  • 效率对比

虽然都是整活的排序算法，但这个排序算法的效率还是比睡觉排序明显高不少的，就是有点耗硬盘寿命。

编程语言 执行时间 输出结果
Python 69ms Python结果
JavaScript 50ms JavaScript结果