欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

希尔排序

程序员文章站 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;
}
相关标签: 希尔排序