Stooge排序与Bogo排序算法

Stooge排序算法

Stooge排序是一种低效的递归排序算法，甚至慢于冒泡排序。在《算法导论》第二版第7章（快速排序）的思考题中被提到，是由Howard、Fine等教授提出的所谓“漂亮的”排序算法。

使用Stooge排序为一列数字进行排序的过程

Stooge排序算法原理：

1、如果最后一个值小于第一个值，则交换它们

2、如果当前子集元素数量大于等于3：

算法的复杂度正比于: T(n)=3T(2n/3)+1. 已被证明时间复杂度接近于O(n2.71) ，可见此算法效率相当的低下，比选择、插入、冒泡排序更差

算法实现：

// Completed on 2014.10.8 21:35

// Language: C99

// 版权所有（C）codingwu (mail: oskernel@126.com) 

// 博客地址：http://www.cnblogs.com/archimedes/

#include stdio.h 

#include stdbool.h 

void swap(int *a, int *b) //交换两元素的值

 int t;

 t = *a;

 *a = *b;

 *b = t;

void printArray(int a[], int count) //打印数组元素

 int i;

 for(i = 0; i count; i++)

 printf("%d ",a[i]);

 printf("\n");

void stooge_sort(int a[], int left, int right)

 int t;

 if(a[left] a[right])

 swap( a[left], a[right]);

 if(right - left + 1 = 3) {

 t = (right - left + 1) / 3;

 stooge_sort(a, left, right - t);

 stooge_sort(a, left + t, right);

 stooge_sort(a, left, right - t);

int main(void) 

 int a[] = {3, 5, 4, 6, 9, 7, 8, 0, 1};

 int n = sizeof(a) / sizeof(*a);

 printArray(a, n);

 stooge_sort(a, 0, n - 1);

 printArray(a, n);

 return 0;

}

Bogo排序算法

在计算机科学中，Bogo排序（bogo-sort）是个既不实用又原始的排序算法，其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自Quantum bogodynamics，又称bozo sort、blort sort或猴子排序.

其平均时间复杂度是 O(n × n!)，在最坏情况所需时间是无限。它并非一个稳定的算法。

运行时间

      这个排序算法基于可能性。平均而言，让所有元素都被排好序的期望比较次数渐近于(e-1)n!，期望的位置交换次数渐近(n-1)n!。期望的位置交换次 数增长地比期望比较次数快，是因为只需要比较几对元素就能发现元素是无序的，但是随机地打乱顺序所需要的交换次数却与数据长度成比例。在最差的情况下，交 换和比较次数都是无限的，这就像随机投掷硬币可能连续任意次正面向上。

最好的情况是所给的数据是已经排好序的，这种情况下不需要任何位置交换，而比较次数等于n-1。

对任何固定长度的数据，算法的预期运行时间像无限猴子定理一样是无限的：总有一些可能性让被正确排好序的序列出现。

算法实现：

// Completed on 2014.10.8 21:50

// Language: C99

// 版权所有（C）codingwu (mail: oskernel@126.com) 

// 博客地址：http://www.cnblogs.com/archimedes/

#include stdio.h 

#include stdbool.h 

void swap(int *a, int *b) //交换两元素的值

 int t;

 t = *a;

 *a = *b;

 *b = t;

void printArray(int a[], int count) //打印数组元素

 int i;

 for(i = 0; i count; i++)

 printf("%d ",a[i]);

 printf("\n");

unsigned int Random1(int a, int b) //随机生成[a,b)之间的数

 return (rand() % (b - a) + a);

unsigned int Random2(int n) //随机生成[0,n)之间的数

 return (rand() % n);

bool inorder(int a[], int n) //判断序列是否已经有序

 int i;

 for(i = 0; i i++)

 if(a[i] a[i + 1]) return false;

 return true;

void shuffle(int a[], int n)

 int i, swapPosition;

 for(i = 0; i i++)

 swapPosition = Random2(i + 1);

 swap( a[i], a[swapPosition]);

void bogo_sort(int a[], int n)

 while(!inorder(a, n))

 shuffle(a, n);

int main(void) 

 int a[] = {3, 5, 4, 6, 9, 7, 8, 0, 1};

 int n = sizeof(a) / sizeof(*a);

 srand((unsigned)time(NULL)); 

 printArray(a, n);

 bogo_sort(a, n);

 printArray(a, n); 

 return 0;

}

算法排序4——插入排序 每个元素要比较的是它之前的已排序的元素，并判断大小，所以再定义一个元素 j，从已排序组内从后往前比较；例如当 i = 5 的时候，其实是第6个位置，而 j = 5 的时候，由于从第一个开始计数，所以就表示第五个位置，恰好满足已排序组内的最后一个，终止值就是元素第一个
排序：选择排序（算法） 排序就是算法。   选择排序（Selection sort）是一种简单直观的排序算法。 选择排序是不稳定的排序方法。   eg：序列[9，9， 1]第一次就将第一个[9]与[1]交换，导致第一个9挪动到第二个9后面 Note：一般面试的时候才会用到选择、冒泡排序。
1.选出数组中一个元素，将整个数组中比他小的元素放在他左边，比他大的放在他右边。这样整个数组就被分成了两部分，被选出的那个元素就在这两部分中间。 2.再对每一部分执行同样的操作。 3.重复执行第2步，直到每一个部分只有一个元素。 具体是这样实现的，假设有数组a[10]：