首页 > 代码库 > 排序算法之stooge排序

排序算法之stooge排序

5.stooge排序&冒泡排序

5.1 stooge排序

      stooge排序是一种递归排序算法,这种排序算法不仅慢于一般的有效排序算法(如:插入排序,合并排序,堆排序和快速排序),甚至慢于冒泡排序。是一种简单但低效的就地排序算法。

      其排序的思路为:

      首先,如果一段子数组的末位小于该子数组的首位,则交换两数。

      随后,若子数组的元素个数为3或者3以上,先对前2/3(取上界)的子数组调用stooge排序;然后,对后2/3(取上界)的子数组调用stooge排序;最后,再对前2/3(取上界)的子数组调用stooge排序。若子数组的元素个数小于3,则退出stooge排序。

 

      以数组{8,9,1,27}为例,其具体执行过程如图5-1所示。其中,灰色框为当前选取的2/3的子数组,红色的数字为进行比较并可能发生交换的数字。


      或者,可以参照以下stooge排序的动态图。


     该图的原始链接地址为:

      http://en.wikipedia.org/wiki/File:Sorting_stoogesort_anim.gif


C代码实现为:

#include <stdio.h>
#include <random>
#include <time.h>

void exchange(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}
void stooge_sort(int a[], int start, int end){
	if( a[start]>a[end] ) {
		exchange(a[start], a[end]);
	}
	if( start+1>=end ) {
		return;
	}
	int k = (end-start+1)/3;
	//对前2/3的子数组进行stooge排序
	stooge_sort(a, start, end-k);
	//对后2/3的子数组进行stooge排序
	stooge_sort(a, start+k, end);
	//再次对前2/3的子数组进行stooge排序
	stooge_sort(a, start, end-k);
}

int main(int argc, char** argv) {
	const int length = 25;
	int a[length];
	//告诉rand方法以time为种子去生成随机数
	srand( (unsigned)time( NULL ) );
	for(int i=0; i<length; i++) {
		a[i] = rand()%100;
		printf("%d ", a[i]);
	}
	printf("\n");
	stooge_sort(a, 0, length-1);
	for(int i=0; i<length; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

C++代码实现为:

#include <iostream>
#include <vector>
#include <random>
#include <time.h>
using namespace std;

void exchange(int &a, int &b) {
	int temp = a;
	a = b;
	b = temp;
}
//stooge排序
void stooge_sort(vector<int> &a, vector<int>::iterator itStart, vector<int>::iterator itEnd) {
	if( *(itStart)>*(itEnd) ) {
		exchange( *(itStart), *(itEnd) );
	}
	if( itStart+1>=itEnd ) {
		return;
	}
	int k = (itEnd-itStart+1)/3;
	//对前2/3的子数组进行stooge排序
	stooge_sort(a, itStart, itEnd-k);
	//对后2/3的子数组进行stooge排序
	stooge_sort(a, itStart+k, itEnd);
	//再次对前2/3的子数组进行stooge排序
	stooge_sort(a, itStart, itEnd-k);
}

int main() {
	const int length = 25;
	int a[length];
	//告诉rand方法以time为种子去生成随机数
	srand( (unsigned)time( NULL ) );
	for(int i=0; i<length; i++) {
		a[i] = rand()%100;
	}
	vector<int> aVec(a, a+length);
	vector<int>::iterator itStart = aVec.begin();
	vector<int>::iterator itEnd = aVec.end()-1;
	for(vector<int>::iterator it=itStart; it<=itEnd; it++) {
		cout<<*(it)<<" ";
	}
	cout<<endl;
	stooge_sort(aVec, itStart, itEnd);
	for(vector<int>::iterator it=itStart; it<=itEnd; it++) {
		cout<<*(it)<<" ";
	}
	cout<<endl;
	return 0;
}