首页 > 代码库 > 排序算法之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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。