希尔排序
程序员文章站
2022-06-04 17:54:12
...
#include<iostream>
using namespace std;
void shell_sort(int arr[], int len) {
int increment, i, j;
increment = len;
do {
increment = increment / 3 + 1; //当 increment = 10 / 3 + 1 = 4时, 意味着数组被分成4组,且最后一个增量必须为1
for (i = increment; i < len; i++) {
int temp = arr[i];
//每组内分别进行直接插入排序
for (j = i - increment; j >= 0 && temp < arr[j]; j = j - increment) {
arr[j + increment] = arr[j];
}
arr[j + increment] = temp;
}
} while (increment > 1);
}
int main()
{
int arr[10] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
shell_sort(arr, 10);
for (int i = 0; i < 10; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
注意:
内层for循环的准确意义
性能分析:
其最坏时间复杂度依然为O(n2),一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2),其下界为nlogn
存储空间:O(1)
稳定性分析:因为排序过程中元素可能会前后跳跃,所以不稳定。