当前位置：首页 > article >正文

探索非传统排序算法：从睡眠排序到量子博戈排序的趣味实现

article 2024/12/4 19:37:41

文章目录

- - 1. 睡眠排序（Sleep Sort）
  - 2. 猴子排序（Bogo Sort）
  - 3. 侏儒排序（Gnome Sort）
  - 4. 鸡尾酒排序（Cocktail Shaker Sort）
  - 5. 梳排序（Comb Sort）
  - 6. 砖块排序（Brick Sort 或 Odd-Even Sort）
  - 7. 量子博戈排序（Quantum Bogo Sort）

1. 睡眠排序（Sleep Sort）

概念: 使用多线程或多进程，每个元素创建一个线程/进程，根据其值延迟相应的时间后输出。
特点: 实现简单但效率极低，依赖于系统调度器，不适用于实际应用。
复杂度: 不适用（因为它的正确性和性能取决于外部因素）。

import time
import threading

def sleep_sort(values):
    def sleep_and_print(val):
        time.sleep(val)
        print(val, end=' ')

    threads = []
    for value in values:
        thread = threading.Thread(target=sleep_and_print, args=(value,))
        threads.append(thread)
        thread.start()

    for thread in threads:
        thread.join()

2. 猴子排序（Bogo Sort）

概念: 随机打乱数组直到偶然获得有序序列。
特点: 极端非高效，平均时间复杂度为O((n+1)!).
复杂度: 平均情况 O((n+1)!)，最坏情况无限大。

import random

def bogo_sort(arr):
    while not all(arr[i] <= arr[i+1] for i in range(len(arr)-1)):
        random.shuffle(arr)
    return arr

3. 侏儒排序（Gnome Sort）

概念: 类似插入排序，通过比较相邻元素并交换来排序。
特点: 实现简单，适合教育目的。
复杂度: 最坏情况 O(n^2)，最好情况 O(n).

def gnome_sort(arr):
    index = 0
    while index < len(arr):
        if index == 0 or arr[index-1] <= arr[index]:
            index += 1
        else:
            arr[index], arr[index-1] = arr[index-1], arr[index]
            index -= 1
    return arr

4. 鸡尾酒排序（Cocktail Shaker Sort）

概念: 冒泡排序的变体，从两端向中间进行双向遍历。
特点: 对于接近排序的数据集表现较好。
复杂度: 最坏和平均情况 O(n^2)，最好情况 O(n).

def cocktail_shaker_sort(arr):
    n = len(arr)
    swapped = True
    start = 0
    end = n - 1
    
    while (swapped == True):
        swapped = False
        
        for i in range(start, end):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
                
        if not swapped:
            break
            
        swapped = False
        end -= 1
        
        for i in range(end-1, start-1, -1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                swapped = True
                
        start += 1
    
    return arr

5. 梳排序（Comb Sort）

概念: 冒泡排序的改进，使用逐渐缩小的间隔对元素进行比较和交换。
特点: 减少了大的混乱，提高了排序速度。
复杂度: 最坏情况 O(n^2)，但在实践中通常比冒泡排序快。

def comb_sort(arr):
    gap = len(arr)
    shrink = 1.3
    sorted = False
    
    while not sorted:
        gap = int(gap / shrink)
        if gap > 1:
            sorted = False
        else:
            gap = 1
            sorted = True
        
        i = 0
        while i + gap < len(arr):
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                sorted = False
            i += 1
    
    return arr

6. 砖块排序（Brick Sort 或 Odd-Even Sort）

概念: 冒泡排序的另一种变体，交替对奇数索引和偶数索引的相邻元素排序。
特点: 可以减少遍历次数，对于某些数据分布效果更好。
复杂度: 最坏情况 O(n^2)，最好情况 O(n log n).

def brick_sort(arr):
    is_sorted = False
    n = len(arr)
    
    while not is_sorted:
        is_sorted = True
        
        # Even indexed elements
        for i in range(0, n-1, 2):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                is_sorted = False
        
        # Odd indexed elements
        for i in range(1, n-1, 2):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                is_sorted = False
    
    return arr