Last updated 6 years ago
比較第iii筆資料與第i+i+i+span筆資料,若前者大於後者,則兩者交換。
span
每一回合(每一個span)要做到都沒有發生交換才可以結束。
span的型式: [n2k][\frac{n}{2^k}][2kn]
void Sort(char *arr){ int n = strlen(arr); int span = n/2; int flag = 0; while(span >= 1){ while(flag != n-span){ //判斷是否整個回合都沒有swap flag = n - span; for (int i = 0; i < n-span; i++){ if (arr[i] > arr[i+span]){ //swap int temp = arr[i]; arr[i] = arr[i+span]; arr[i+span] = temp; flag--; } } } span/=2; } }
演算法分析:
span=1,shell sort結束。
Time Complexity:
Shell sorting is a unstable sorting method.
input={5,7,8,9,3,1,4,2}input=\{5,7,8,9,3,1,4,2\}input={5,7,8,9,3,1,4,2}
span=[n2k]=821=4⇒{3,1,4,2,5,7,8,9}span=[\frac{n}{2^k}]=\frac{8}{2^1}=4 \quad \Rightarrow \{3,1,4,2,5,7,8,9\}span=[2kn]=218=4⇒{3,1,4,2,5,7,8,9} ,下一回合沒有發生交換,此回合結束。
span=822=2⇒{3,1,4,2,5,7,8,9}span = \frac{8}{2^2}=2 \quad \Rightarrow \{3,1,4,2,5,7,8,9\}span=228=2⇒{3,1,4,2,5,7,8,9},下一回合沒有發生交換,此回合結束。
span=823=1⇒{1,3,2,4,5,7,8,9}⇒{1,2,3,4,5,7,8,9}span = \frac{8}{2^3}=1 \quad \Rightarrow \{1,3,2,4,5,7,8,9\} \Rightarrow \{1,2,3,4,5,7,8,9\}span=238=1⇒{1,3,2,4,5,7,8,9}⇒{1,2,3,4,5,7,8,9},下一回合沒有發生交換,此回合結束。
Avg Case: O(n2)O(n^2)O(n2)
Worst Case: O(n2)O(n^2)O(n2)
Best Case: 和span的形式有關。 O(n32)O(n^{\frac{3}{2}})O(n23)
Space Complexity: O(1)O(1)O(1)