无聊排序讲解（bushi）

sczans.(3/4退站)

2026-07-11 16:52:51

发布于：天津

17阅读

0回复

0点赞

无聊排序讲解第 $β0.1$ 版

什么是无聊排序

思想

递归三分段排序
设数组区间 ([l,r])：如果 (a[l]>a[r])，交换两端；如果区间长度小于等于 2，直接返回；
取长度三分之一 (t=(r-l+1)/3)；递归排序左段 ([l,r-t])；递归排序右段 ([l+t,r])；再次递归排序左段 ([l,r-t])。

怎么实现？

#include <cstdio>
#include <algorithm>
using namespace std;
void stooge(int a[], int l, int r){
    if(a[l] > a[r]) swap(a[l], a[r]);
    if(r - l + 1 <= 2) return;
    int t = (r - l + 1) / 3;
    stooge(a, l, r - t);
    stooge(a, l + t, r);
    stooge(a, l, r - t);}
int main(){
    int arr[] = {5, 2, 7, 1, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    stooge(arr, 0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;}