希爾排序
- 時(shí)間復(fù)雜度：平均O(n^1.3),最好為O(n),最壞為0(n ^ 2)
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
算法解析：
- 希爾排序是直接插入排序的一種改進(jìn)，又稱做縮小增量排序
- 希爾排序是把待排序集合計(jì)算出一個(gè)增量集合Tn
- 把待排序集合分成若干個(gè)子集，然后每個(gè)子集進(jìn)行直接插入排序剥险，知道Ti=1為止，排序結(jié)束
- 遍歷次數(shù)為增量集合的count數(shù)
舉例
有一個(gè)集合如下圖所示：
list.png
計(jì)算增量：gap = length/2
-
第一次：gap = 4蟀俊，把待排序列劃分為4個(gè)子序列
第一次.png -
第二次 ：gap = 2旗扑，把待排序列劃分為2個(gè)子序列
第二次.png 第三次：gap = 1捎谨，進(jìn)行一次直接插入排序诫尽，排序結(jié)束
排序結(jié)果：
第一次：7 3 1 2 8 5 4 10 9
第二次：1 2 4 3 7 5 8 10 9
第三次：1 2 3 4 5 7 8 9 10
C語言實(shí)現(xiàn)
void shellSort(int arr[],int length) {
int gap;//間距or增量
for (gap = length/2; gap>0; gap/=2) { //gap->1 共分幾次
for (int i=gap; i<length; i++) {//從gap個(gè)元素開始禀酱，直接插入排序
if (arr[i] < arr[i-gap]) {
int tmp = arr[i];
int k = i-gap;
while (k>=0 && arr[k] > tmp) {
arr[k+gap] = arr[k];
k-=gap;
}
arr[k+gap] = tmp;
}
}
}
}
OC實(shí)現(xiàn)
- (NSArray *)shellSort:(NSMutableArray *)arr {
int length = arr.count;
int gap;
for (gap = length/2; gap>0; gap/=2) {
for (int i = gap; i < length; i++) {
if ([arr[i] intValue] < [arr[i-gap] intValue]) {
NSNumber *tmp = arr[i];
int k = i-gap;
while (k>=0 && [arr[k] intValue] > tmp.intValue) {
arr[k+gap] = arr[k];
k-=gap;
}
arr[k+gap] = tmp;
}
}
}
return arr.copy;
}
以下實(shí)現(xiàn)來源于網(wǎng)絡(luò)，未驗(yàn)證
c++實(shí)現(xiàn)
void shell_sort(const int start, const int end) {
int increment = end - start + 1; //初始化劃分增量
int temp{ 0 };
do { //每次減小增量牧嫉，直到increment = 1
increment = increment / 3 + 1;
for (int i = start + increment; i <= end; ++i) { //對(duì)每個(gè)劃分進(jìn)行直接插入排序
if (numbers[i - increment] > numbers[i]) {
temp = numbers[i];
int j = i - increment;
do { //移動(dòng)元素并尋找位置
numbers[j + increment] = numbers[j];
j -= increment;
} while (j >= start && numbers[j] > temp);
numbers[j + increment] = temp; //插入元素
}
}
} while (increment > 1);
}
js實(shí)現(xiàn)
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len/3) { //動(dòng)態(tài)定義間隔序列
gap =gap*3+1;
}
for (gap; gap > 0; gap = Math.floor(gap/3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
}
return arr;
}
Python 代碼實(shí)現(xiàn)
def shellSort(arr):
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr
}
Go 代碼實(shí)現(xiàn)
func shellSort(arr []int) []int {
length := len(arr)
gap := 1
for gap < gap/3 {
gap = gap*3 + 1
}
for gap > 0 {
for i := gap; i < length; i++ {
temp := arr[i]
j := i - gap
for j >= 0 && arr[j] > temp {
arr[j+gap] = arr[j]
j -= gap
}
arr[j+gap] = temp
}
gap = gap / 3
}
return arr
}
Java 代碼實(shí)現(xiàn)
public class ShellSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對(duì) arr 進(jìn)行拷貝剂跟，不改變參數(shù)內(nèi)容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int gap = 1;
while (gap < arr.length) {
gap = gap * 3 + 1;
}
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
gap = (int) Math.floor(gap / 3);
}
return arr;
}
}
PHP 代碼實(shí)現(xiàn)
function shellSort($arr)
{
$len = count($arr);
$temp = 0;
$gap = 1;
while($gap < $len / 3) {
$gap = $gap * 3 + 1;
}
for ($gap; $gap > 0; $gap = floor($gap / 3)) {
for ($i = $gap; $i < $len; $i++) {
$temp = $arr[$i];
for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
$arr[$j+$gap] = $arr[$j];
}
$arr[$j+$gap] = $temp;
}
}
return $arr;
}
