希尔排序
希尔排序
希尔排序(Shell Sort)，也称递减增量排序算法，是插入排序的一种更高效的改进版本。其基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。
希尔排序首先对相距较远的元素进行排序，然后依次减小要排序的元素之间的间隔。元素之间的间隔随所使用的序列而减少。在shell排序算法中可以使用的一些优化序列类型有：
Shell 的原始序列：
N/2 , N/4 , …, 1Knuth 的增量：1, 4, 13, ..., (3k – 1) / 2Sedgewick 的增量：1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1Hibbard 的增量：1, 3, 7, 15, 31, 63, 127, 255, 511、...Papernov & Stasevich 增量：1, 3, 5, 9, 17, 33, 65,...普拉特：1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81,...
希尔排序的性能取决于用于给定输入数组的序列类型。
希尔排序的工作流程
-
这里假设对以下这个数组排序。
-
这里使用希尔原始序列(
N/2, N/4, ...1) 作为排序算法迭代的间隔。如在第1个循环中，由数组大小N=8，则比较位于N/2=4区间的元素，如果他们非有序排列就交换操作。
对所有剩下的元素持续做这种处理。 
-
在第2个循环中，采用
N/4 = 8/4 = 2的间隔，并再次对位于这些间隔的元素进行排序。
-
继续对剩下的元素做同样的处理。
-
最后，对间隔为
N/8 = 8/8 =1的数组元素进行排序后，就完全排序完成。
复杂度
|Time Complexity|| |—|—| |Best | O(nlog n) | |Worst | O(n^2) | |Average | O(nlog n) | |Space Complexity | O(1) | |Stability | No |
代码实现
Swift实现
// Shell 排序是插入排序算法的通用版本。 它首先对相距较远的元素进行排序，然后依次减小要排序的元素之间的间隔。
import Foundation
// Rearrange elements at each n/2, n/4, n/8, ... intervals
//参考：https://www.programiz.com/dsa/shell-sort
func shellSort(array:inout [Int]) {
if(array.count==0){
return
}
//交换距离(步长)interval
var interval = array.count / 2
while interval > 0 {
//让每个元素按interval距离迭代交换, 双指针：i是迭代指针，j是交换指针
//遍历距离内的每个元素
// for i in 0 ..< interval {
// //排序
// let temp = array[i]
// var j = i
// while j < array.count && array[j + interval] > temp {
// //交换
// array[j] = array[j + interval]
// j += interval
// }
// array[j] = temp
// }
//遍历不在interval距离内的每个元素
for i in interval ..< array.count {
let temp = array[i]
var j = i //i后往走，j以i为参照点往前按interal步长走
//如果前面 array[j - interval] 的值大于后面的 array[i]，则交换
while j >= interval && temp < array[j - interval] {
//交换
array[j] = array[j - interval]
j -= interval //继续按照这个距离(步长)往前走，j每往前走一次就做一次交换判断
}
array[j] = temp
}
//每一轮间距减半
interval /= 2
}
}
//打印
func printShellSort(_ array:inout [Int]){
//var array:[Float] = [3, 2, 5, 7, 1, 5, 4, 8, 11, 0]
shellSort(array: &array)
print(array)
}
let arr:[Int] = [3, 2, 5, 7, 1, 5, 4, 8, 11, 0]
printShellSort(&arr)
Python 实现
# Shell sort in python
def shellSort(array, n):
# Rearrange elements at each n/2, n/4, n/8, ... intervals
interval = n // 2
while interval > 0:
for i in range(interval, n):
temp = array[i]
j = i
while j >= interval and array[j - interval] > temp:
array[j] = array[j - interval]
j -= interval
array[j] = temp
interval //= 2
data = [9, 8, 3, 7, 5, 6, 4, 1]
size = len(data)
shellSort(data, size)
print('Sorted Array in Ascending Order:')
print(data)
Java 实现
// Shell sort in Java programming
import java.util.Arrays;
// Shell sort
class ShellSort {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
void shellSort(int array[], int n) {
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Driver code
public static void main(String args[]) {
int[] data = { 9, 8, 3, 7, 5, 6, 4, 1 };
int size = data.length;
ShellSort ss = new ShellSort();
ss.shellSort(data, size);
System.out.println("Sorted Array in Ascending Order: ");
System.out.println(Arrays.toString(data));
}
}
C 实现
// Shell Sort in C programming
#include <stdio.h>
// Shell sort
void shellSort(int array[], int n) {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Print an array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// Driver code
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / sizeof(data[0]);
shellSort(data, size);
printf("Sorted array: \n");
printArray(data, size);
}
C++ 实现
// Shell Sort in C++ programming
#include <iostream>
using namespace std;
// Shell sort
void shellSort(int array[], int n) {
// Rearrange elements at each n/2, n/4, n/8, ... intervals
for (int interval = n / 2; interval > 0; interval /= 2) {
for (int i = interval; i < n; i += 1) {
int temp = array[i];
int j;
for (j = i; j >= interval && array[j - interval] > temp; j -= interval) {
array[j] = array[j - interval];
}
array[j] = temp;
}
}
}
// Print an array
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
// Driver code
int main() {
int data[] = {9, 8, 3, 7, 5, 6, 4, 1};
int size = sizeof(data) / sizeof(data[0]);
shellSort(data, size);
cout << "Sorted array: \n";
printArray(data, size);
}