希尔排序
程序员文章站
2022-06-04 17:53:54
...
0. 简述
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列,对子序列之间相同位置的元素分为一组,每组进行插入排序,这样就实现了整体的待整个序列"基本有序"时,再对全体数列进行直接插入排序。
1. 算法步骤
1、选择一个增量序列:如:gap = lenght / 3 ,gap = gap / 3
2、按增量序列个数 k,对序列进行 k 趟排序;
3、每趟排序,根据对应的增量 gap,将待排序列分割成若干长度为 m = lenght / gap 的子序列,分别对各子表对应元素进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
4、直到增量为1时,即可完成整个序列的排序。
2. 动图演示
3. C++代码实现
#include <iostream>
using namespace std;
/*
希尔排序的基本思想是:
先将整个待排序的记录序列分割成为若干子序列
分别进行直接插入排序,待整个序列中的记录"基本有序"时,
再对全体记录进行依次直接插入排序。
希尔排序步骤:
1、将整个待排序序列分割成 n 个子序列(分段)
2、段与段之间进行整体的插入排序
3、三段相对应的元素进行比较、置换,小的在第一段,大的在第三段)
4、段排序完成后进行整体的插入排序。
优点:
避免了(原数列位置)与(排序好数列元素应该位于的位置)相距很远的进行元素插入
*/
void shell_sort(int arr[], int len)
{
int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1)//向右移位,相当于除2; >>=:自身移位后给自己赋值
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;
}
}
template<typename T>
void Shell_Sort(T array[], int length)
{
int i, j;
int h = 1;
while (h < length / 3)
h = h * 3 + 1;
while (h >= 1)
{
for (i = h; i < length; i++)
{
for (j = i; (j >= h) && (array[j] < array[j - h]); j -= h)
swap(array[j], array[j - h]);
}
h = h / 3;
}
}
int main()
{
int arri[] = { 1,35,98,63,24,84,10,24,3,62,99,75,7 };
int len = (int)sizeof(arri) / sizeof(*arri);//(*arri)为数组第一个元素
shell_sort(arri, len);
for (int i = 0; i < len; i++)
{
cout << arri[i] << " ";
}
cout << endl;
float arrf[] = { 52.3,85.6,75.2,20.0,2.3,5.6,36.4,57.2,77.7 };
len = (int)sizeof(arrf) / sizeof(*arrf);//(*arrf)为数组第一个元素
Shell_Sort(arrf, len);
for (int i = 0; i < len; i++)
{
cout << arrf[i] << " " << endl;
}
return 0;
}
上一篇: 男人可以不懂女人的疼,但请你善待她余生。
下一篇: 情侣吵架该怎么处理才好?