臭皮匠排序（英語：Stooge Sort）是一種低效的遞歸排序算法，甚至慢於冒泡排序。在《算法導論》第二版第7章（快速排序）的思考題中被提到，是由Howard、Fine等教授提出的所謂“漂亮的”排序算法。
基本介紹
- 中文名：臭皮匠排序
- 外文名：Stooge Sort
- 學科：計算機科學
詳解,時間複雜度,實現,
詳解
臭皮匠排序（英語：Stooge Sort）是一種低效的遞歸排序算法，甚至慢於冒泡排序。在《算法導論》第二版第7章（快速排序）的思考題中被提到，是由Howard、Fine等教授提出的所謂“漂亮的”排序算法，代碼很漂亮但是很耗時。
該排序是一種低效的遞歸排序算法，不僅慢於一般的有效排序算法（如：插入排序，合併排序，堆排序和快速排序），甚至慢於冒泡排序。所以相比於經典的排序算法，STOOGE算法具有非常差的性能。
時間複雜度
最差的時間複雜度為：O(n^log(3/2)3)
最差的空間複雜度為： O（n^2.7）
可見此算法效率相當的低下，比選擇、插入、冒泡排序更差！
實現
如果最後一個值小於第一個值，則交換這兩個數
如果當前集合元素數量大於等於3：
1.使用臭皮匠排序前2/3的元素
2.使用臭皮匠排序後2/3的元素
3.再次使用臭皮匠排序前2/3的元素
package com.baobaotao.test;
/**
* 排序研究
* @author benjamin(吳海旭
* @email [email protected] / [email protected]
*
*/
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) ;
}
}
