vlambda博客
学习文章列表

十大排序算法之四-希尔排序【Shell'sSort】-初体验

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。


关键点:

增量分组

直接插入排序算法


如上图,增量为4时,划分为3,4,5;    2,7,10;     8,6;     9,1;四个序列先进行插入排序。


当增量为5时,划分为15,6,8;5,1,10;  2,4;  7,3;  12,9; 5个序列进行插入排序;

当增量为3时。。。

当增量为1时,直接进行插入排序。


先写个.h文件

#ifndef SORT_SHELLSORT_H#define SORT_SHELLSORT_H
template<typename T>void ShellSort(T *arr, int length){ int i, j, inc; T key = arr[0]; //初始增量:n/2,每一趟之后除以2 for (inc = length / 2; inc > 0; inc /= 2) { cout << "增量为" << inc<<endl; //每一趟采用插入排序 for (i = inc; i < length; i++) { key = arr[i]; for (j = i; j >= inc && key < arr[j - inc]; j -= inc) arr[j] = arr[j - inc]; arr[j] = key; } for (int i = 0; i < length; i++) cout << arr[i] << " "; cout << endl; } cout << endl;}
#endif SORT_SHELLSORT_H

再加入到main函数里


#include <iostream>#include"InsertionSort.h"#include"ShellSort.h"
using namespace std;
template <typename T>void PrintArray(T arr[], int n){ for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl;}
template <typename T>void checkArrayIsSort(T arr[], int n){ for (int i = 0; i < n-1; i++) { if (arr[i] > arr[i + 1]) { cout << "\n该数组为乱序\n"; break; } } cout << "\n该数组已经排好序\n";}
int main(){ int arr[] = { 1,8,9,3,16,2,18,28}; int length = sizeof(arr) / sizeof(arr[0]); /* cout << "插入排序前\n"; PrintArray(arr, length); cout << endl<<"开始插入排序"<<endl; insertionSort(arr, length); cout << "插入排序后\n"; PrintArray(arr, length);
checkArrayIsSort(arr, length);*/
cout << "希尔排序前\n"; PrintArray(arr, length); cout << endl<<"开始希尔排序"<<endl; ShellSort(arr, length); cout << "希尔排序后\n"; PrintArray(arr, length);
checkArrayIsSort(arr, length); std::cout << "Hello World!\n";}

运行结果如下





                                希尔排序完结,撒花