簡(jiǎn)述：引入gap概念直砂，分塊進(jìn)行插入排序幌陕。gap會(huì)根據(jù)要求遞減，當(dāng) gap == 1 等于1時(shí)存崖，為基本的插入排序冻记。
- 最優(yōu)時(shí)間復(fù)雜度：根據(jù)步長(zhǎng)序列的不同而不同
- 最壞時(shí)間復(fù)雜度：O(n2)
- 穩(wěn)定型：不穩(wěn)定
python3
# coding: utf-8
def shell_sort(alist):
"""希爾排序"""
n = len(alist)
gap = n // 2
while gap > 0:
for j in range(gap,n):
i = j
while i > 0:
if j >= gap and alist[i] < alist[i - gap]:
alist[i], alist[i - gap] = alist[i - gap], alist[i]
i -= gap
else:
break
gap //= 2
if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
shell_sort(li)
print(li)
/**
希爾算法
*/
- (void)shell_sort:(NSMutableArray *)arr {
NSInteger gap = arr.count / 2;
while (gap >= 1) {
for (NSInteger i = gap; i < arr.count; i++) {
NSInteger j = i;
while (j > 0) {
if (j >= gap && arr[j] < arr[j - gap]) {
NSNumber *temp = arr[j];
arr[j] = arr[j - gap];
arr[j - gap] = temp;
j -= gap;
} else {
break;
}
}
}
// 縮短步長(zhǎng)
gap = gap / 2;
}
}
