大家好

好久没有发过文章了，今天来发一篇。

你看着我这个看起来很正经的题目，其实不然，这是我自己发明的一种 非常好用 的排序方法。

它的时间复杂度在O(n) 和 O(∞) 之间，主要看运气...

怎么搞

我之前写过一篇关于排序的文章，当时就提到了这个排序方法，

当时我的思路是随机下标，遍历数组把 a[i] 位置改成 a [随机数] 位置上的数，还要给下标去重...最后，程序不出意料地爆了99+个错。。。

直到今天，我突然想起来，并有了一种更完美的思路：

1. 先写一个 IsUp 函数，用来判断数组是不是升序（因为我要升序排序）

bool IsUp(int w[]){
	for(int i=0;i<n-1;i++){
		if(w[i+1]<w[i]) return false;
	}
	return true;
}

参数是一个数组，然后遍历它，注意只遍历到 n-1 ，因为我要判断后面的元素如果小于前面的元素，就 return false，如果循环到n，访问下标是 i+1 的元素时会报错。

2.我们可以打乱数组！再写一个打乱数组的函数。

void random(int a[],int n){
    int index,tmp,i;
    srand(time(NULL));
    for(i=0;i<n;i++){
        index=rand()%(n-i)+i;
        if (index != i){
            tmp = a[i];
            a[i] = a[index];
            a[index] = tmp;
        }
    }
}

随机下标，如果和当前位置的下标不一样即可。

3.最后主程序一个死循环，随机到为升序为止。

全部代码

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
using namespace std;
int n,a[10010];
bool IsUp(int w[]){
	for(int i=0;i<n-1;i++){
		if(w[i+1]<w[i]) return false;
	}
	return true;
}
void random(int a[],int n){
    int index,tmp,i;
    srand(time(NULL));
    for(i=0;i<n;i++){
        index=rand()%(n-i)+i;
        if (index != i){
            tmp = a[i];
            a[i] = a[index];
            a[index] = tmp;
        }
    }
}
int main(){
    cout<<"输入要排序数的数量:";cin>>n;
    cout<<"输入每个数:";
    for(int i=0;i<n;i++)cin>>a[i];
    cout<<"正在排序..."<<endl;
    while(1){
    	random(a,n);
    	if(IsUp(a)){
    		for(int i=0;i<n;i++)cout<<a[i]<<' ';
			break;	
		}	
	}
    return  0;
}