Stooge 排序是一种低效的递归排序算法，甚至慢于冒泡排序。在《算法导论》第二版第7章（快速排序）的思考题中被提到，是由Howard、Fine等教授提出的所谓“漂亮的”排序算法。
该算法得名于三个臭皮匠，每个臭皮匠都打其他两个
实现
- 如果最后一个值小于第一个值，则交换这两个数
- 如果当前集合元素数量大于等于3：
-
- 使用臭皮匠排序前2/3的元素
- 使用臭皮匠排序后2/3的元素
- 再次使用臭皮匠排序前2/3的元素
| 最差时间复杂度 |
O(nlog 3 /log 1.5) |
| 最差空间复杂度 |
O(n) |
动态图：
代码实现：
- package com.baobaotao.test;
- /**
- * 排序研究
- * @author benjamin(吴海旭)
- * @email benjaminwhx@sina.com / 449261417@qq.com
- *
- */
- public class Sort {
- /**
- * 臭皮匠排序
- * @param array
- */
- public static void stoogeSort(int[] array) {
- stoogeSort(array, 0, array.length-1) ;
- }
-
- /**
- * 重载臭皮匠排序
- * @param array
- * @param low
- * @param high
- */
- public static void stoogeSort(int[] array, int low, int high) {
- printArr(array) ;
- if(array[low] > array[high]) {
- swap(array, low, high) ;
- }
- if(low + 1 >= high) return ;
- int third = (high-low+1)/3 ;
- stoogeSort(array, low, high-third) ;
- stoogeSort(array, low+third, high) ;
- stoogeSort(array, low, high-third) ;
- }
- /**
- * 按从小到大的顺序交换数组
- * @param a 传入的数组
- * @param b 传入的要交换的数b
- * @param c 传入的要交换的数c
- */
- public static void swap(int[] a, int b, int c) {
- if(b == c) return ;
- int temp = a[b] ;
- a[b] = a[c] ;
- a[c] = temp ;
- }
-
- /**
- * 打印数组
- * @param array
- */
- public static void printArr(int[] array) {
- for(int c : array) {
- System.out.print(c + " ");
- }
- System.out.println();
- }
-
- public static void main(String[] args) {
- int[] number={11,95,45,15,78,84,51,24,12} ;
- stoogeSort(number) ;
- }
- }
转载请标注：http://blog.csdn.net/benjamin_whx/article/details/42462485
