臭皮匠排序（英語：Stooge Sort）是一種低效的遞歸排序算法，甚至慢於冒泡排序。在《算法導論》第二版第7章（快速排序）的思考題中被提到，是由Howard、Fine等教授提出的所謂“漂亮的”排序算法。
基本介紹
- 中文名：臭皮匠排序
- 外文名：Stooge Sort
- 學科：計算機科學
詳解,時間複雜度：,實現,
詳解
臭皮匠排序（英語：Stooge Sort）是一種低效的遞歸排序算法，甚至慢於冒泡排序。在《算法導論》第二版第7章（快速排序）的思考題中被提到，是由Howard、Fine等教授提出的所謂“漂亮的”排序算法，代碼很漂亮但是很耗時。
該排序是一種低效的遞歸排序算法，不僅慢於一般的有效排序算法（如：插入排序，合併排序，堆排序和快速排序），甚至慢於冒泡排序。所以相比於經典的排序算法，STOOGE算法具有非常差的性能。
時間複雜度：
最差的時間複雜度為：O(n^log(3/2)3)
最差的空間複雜度為： O（n^2.7）
可見此算法效率相當的低下，比選擇、插入、冒泡排序更差！
最差的空間複雜度為： 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) ; } }
