希爾排序
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因D.L.Shell于1959年提出而得名。
希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。 [
原理
希爾排序是把序列看成一個矩陣，分成n列，然后逐列進(jìn)行排序，n逐漸減為1
矩陣的列數(shù)取決于步長
如果步長為[1,2,4,8];
就代表依次分為8列，4列，2列，1列，進(jìn)行排序，
希爾本人給出的步長公式為 n/2^k,假設(shè)n為16，那么步長為[1,2,4,8];
比如[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],先分為8列
[1, 2, 3, 4, 5, 6, 7, 8]
[9,10,11,12,13,14,15,16],
,然后對每一列進(jìn)行排序，相當(dāng)于1，9，排序，2，10排序，3，11排序，最后，排序為
[1, 2, 3, 4, 5, 6, 7, 8]
[9,10,11,12,13,14,15,16],
然后分為四列
[1, 2, 3, 4,]
[ 5, 6, 7, 8]
[9,10,11,12]
[13,14,15,16]
然后再對每一列進(jìn)行排序，變?yōu)?/p>
[1, 2, 3, 4,]
[ 5, 6, 7, 8]
[9,10,11,12]
[13,14,15,16],再接著分為兩列排序
[1,2]
[3,4]
[5,6]
[7,8]
[9,10]
[11,12]
[13,14]
[15,16]
,然后對上面繼續(xù)排序為
[1,2]
[3,4]
[5,6]
[7,8]
[9,10]
[11,12]
[13,14]
[15,16],
最后變成一列排序
[1]
[2]
[3]
[4]
[5]
[6]
...
[16],
然后對這一列進(jìn)行排序，我這里為了節(jié)省文字，所以用了個排好序的例子。
時間復(fù)雜度和穩(wěn)定性
最壞：O(n^2)
當(dāng)你在某個范圍內(nèi)，最好的情況下可達(dá)到O(1.3)
不穩(wěn)定排序
代碼及注釋
詳細(xì)看下面的代碼注釋
//
// SCXShellSoft.m
// TestArithmetic
//
// Created by 孫承秀 on 2020/7/16.
// Copyright ? 2020 孫承秀. All rights reserved.
//
#import "SCXShellSoft.h"
@interface SCXShellSoft()
@property (nonatomic , strong) NSMutableArray *softArr;
@end
@implementation SCXShellSoft
-(NSArray *)soft:(NSArray<NSNumber *> *)arr{
self.softArr = arr.mutableCopy;
// 獲取步長序列
NSArray *stepSequence = [self shellStepSequence:self.softArr];
// 根據(jù)步長序列，依次將序列分為例如，8列，4列，2列，1列，這樣，然后依次對每一列進(jìn)行排序
for (NSNumber *step in stepSequence) {
[self shellSoft:step.integerValue];
}
return self.softArr.copy;
}
- (void)shellSoft:(NSInteger)step{
/*
比如[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16],先分為8列
[1, 2, 3, 4, 5, 6, 7, 8]
[9,10,11,12,13,14,15,16],
那么1的索引為0，9的索引為8，2的索引為1，10的索引為9，所以第row行col列的索引為，col + row * step,
比如3的索引，row為0，col為2，那么索引為col + row * step = 2 + 0*8 = 2，
再比如11的索引為，2+1*8=10
*/
/* 然后對每一列進(jìn)行插入排序，比如這里傳來的 step 為 8
需要對以下數(shù)據(jù)進(jìn)行排序
[1, 2, 3, 4, 5, 6, 7, 8]
[9,10,11,12,13,14,15,16],
需要對每一列進(jìn)行排序，所以進(jìn)行8次排序，也就是step次數(shù)
每次排序的數(shù)為每一列的元素，他們的索引為col + row * step
*/
// 這里選擇插入排序
// 需要排序的次數(shù)，8列
for (NSInteger col = 0 ; col < step; col ++) {
// 利用插入排序，對 每一列，也就是 索引col + row * step排序
// 插入排序
// col + row * step
// row = 0: col
// row = 1: col + step
// row = 2: col + 2 * step
// 所以每次 += step
// begin = col + step 因為下面的比較要-step,每次比較的上下查值為step,相當(dāng)于直接拿第二個元素和第一個元素作比較
for (NSInteger begin = col + step; begin < self.softArr.count; begin += step) {
NSInteger index = begin;
// 比較的兩個數(shù)是列，col + row * step，所以上下差 step
// 插入排序，一次拿當(dāng)前的元素和前面的元素進(jìn)行比較，知道到最前面的那個元素
/*
如
[1, 2, 3, 4, 5, 6, 7, 8]
[9,10,11,12,13,14,15,16],
比如比較第三列，索引為2，也就是比較[3,11];
begin = col = 2
begin + step = col + 1 * 8 = 10;
所以先比較這兩個元素的大小，然后 -= step = 2，也就到了3的索引為2，就不能再減了
*/
while (index > col && ((NSNumber *)self.softArr[index]).integerValue < ((NSNumber *)self.softArr[index - step]).integerValue) {
// 交換前后兩個元素的值
NSNumber *tmp = self.softArr[index - step];
self.softArr[index - step] = self.softArr[index];
self.softArr[index] = tmp;
index -= step;
}
}
}
}
// 希爾提出來的步長
- (NSArray *)shellStepSequence:(NSArray *)arr{
// 步長公式 n/2^k
NSMutableArray *stepSequence = [NSMutableArray array];
NSInteger count = arr.count;
NSInteger step = count;
// 依次除以2
while ((step >>= 1) > 0) {
[stepSequence addObject:@(step)];
}
return stepSequence.copy;
}
@end
