程序分享--排序算法--希尔排序

关注我，持续分享逻辑思维&管理思维； 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；
有意找工作的同学，请参考博主的原创：《面试官心得--面试前应该如何准备》，《面试官心得--面试时如何进行自我介绍》《做好面试准备，迎接2024金三银四》。

-------------------------------------正文----------------------------------------

希尔排序：概述
希尔排序是一种分组插入排序方法，它是直接插入排序算法的一种改进版本，它是由 Donald Shell 在1959年提出的。希尔排序的思想是让数组中任意间隔为h的元素都是有序的，这样在整个数组中就形成了一个新的有序的子序列，然后逐渐减小h的值，再进行排序，最后当h为1时，整个数组就是有序的。
 

希尔排序：算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。
1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2.按增量序列个数k，对序列进行 k 趟排序；
3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

#include <iostream>
using namespace std;
 
void shellSort(int* arr, int n) 
{
    // Start with a big gap, then reduce the gap
    for (int gap = n / 2; gap > 0; gap /= 2) 
    {
        // Do insertion sort on gapped sequence
        for (int i = gap; i < n; i += 1) 
        {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) 
            {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}
 

 
int main() 
{
    int vec = { 4，8，9，2，100，400，20，7，17，31，22，0，1，55，30 };
	cout << "希尔排序前：";
	for (int i = 0; i < 15; i++)
		cout << vec[i] << ' ';
	cout << std::endl;

	shellSort(vec, 0, 15);

	cout << "希尔排序后：";
	for (int i = 0; i < 15; i++)
		cout << vec[i] << ' ';
	cout << std::endl;
}