赞
踩
希尔排序实际上是插入排序的优化,所以要先介绍插入排序。
目录
又称直接插入排序。它的基本思想是将一个值插入到一个有序序列中。直至将所有的值都插入完。
假设数组某个位置的下标是end,end + 1对应的值为temp。
让arr[end],temp进行比较如果arr[end]>temp,将arr[end]向后移一位
在让temp与end的前一位进行比较,如果大于那就重复上述操作,反则跳出循环。注意end只能大于等于0。
离开循环后会存在上面图示的情况。我们只需要用temp把它给替换掉。
上面说的是一次插入,所以要再在外面套一层循环把所有的值都插入一次。
- //插入牌序
- void InsertSort(int* arr, int n)
- {
- for (int i = 0; i < n - 1; i++)
- {
- int end = i;
- int temp = arr[end + 1];
- while (end >= 0)
- {
- if (arr[end] > temp)
- {
- arr[end + 1] = arr[end];
- end--;
- }
- else
- {
- break;
- }
- }
- arr[end + 1] = temp;
- }
- }
又称缩小增量排序。它的基本思想是将整个待排元素序列分割成若干个小组,相隔一个gap为一组(gap是一个整数),各小组分别进行插入排序,然后缩减gap再进行排序,重复上述操作。当gap==1时,整个序列中的元素基本有序,在对全体元素进行一次插入排序。
假设gap=3,每隔gap个为一组分组如下:
遍历一次结束条件:在3对应的下标处加一个gap会正好造成非法访问,所以结束条件是下标小于n - gap。
下面的操作就和插入排序一样只不过是相隔gap个插入,经过一次一次的排序序列会变得更有序。
在上面提到gap会逐渐变小,那它怎么变小呢?一般是gap = (gap / 3) + 1(这是相对来说比较合理的记住即可)。当gap小于1时即排完序离开循环即可。
- //希尔排序
- void ShellSort(int* arr, int n)
- {
- int gap = n;
- while (gap > 1)
- {
- gap = gap / 3 + 1;
- for (int i = 0; i < n - gap; i++)
- {
- int end = i;
- int tmp = arr[end + gap];
- while (end >= 0)
- {
- if (arr[end] > tmp)
- {
- arr[end + gap] = arr[end];
- end -= gap;
- }
- else
- {
- break;
- }
- }
- arr[end + gap] = tmp;
- }
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。