臭皮匠排序

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

详解臭皮匠排序（英语：Stooge Sort）是一种低效的递归排序算法，甚至慢于冒泡排序。在《算法导论》第二版第7章（快速排序）的思考题中被提到，是由Howard、Fine等教授提出的所谓“漂亮的”排序算法，代码很漂亮但是很耗时。

该排序是一种低效的递归排序算法，不仅慢于一般的有效排序算法（如：插入排序，合并排序，堆排序和快速排序），甚至慢于冒泡排序。所以相比于经典的排序算法，STOOGE算法具有非常差的性能。

时间复杂度：最差的时间复杂度为：O(n^log(3/2)3)
最差的空间复杂度为： O（n^2.7）
可见此算法效率相当的低下，比选择、插入、冒泡排序更差！

实现如果最后一个值小于第一个值，则交换这两个数1

如果当前集合元素数量大于等于3：

1.使用臭皮匠排序前2/3的元素

2.使用臭皮匠排序后2/3的元素

3.再次使用臭皮匠排序前2/3的元素

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) ; } }本词条内容贡献者为:

孔祥杰 - 副教授 - 大连理工大学软件学院