本文主要是介绍内排序(四)——谢尔(Shell)排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
我的视频课:《面试之排序算法》欢迎大家围观~
核心思想
谢尔(Shell)排序,也叫缩小增量排序法,其核心思想如下:
首先确定一个元素的间隔数gap。
将参加排序的元素按照gap分隔成若干个子序列( 即分别把那些位置相隔为gap的元素看作一个子序列),然后对各个子序列采用某一种排序方法进行排序;此后减小gap值,重复上述过程,直到gap<1。
常用的一种减小gap的方法如下:
基于上述减小gap的方法,谢尔排序法的完整过程图解如下:
gap为4时,初始数据分为4个序列,49、76、35;97、65;38、13;50、27;分别对这个4个序列内进行排序得到第一趟排序,然后gap除以2,得到新的序列…
希尔排序,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
1、插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
2、但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
算法实现
谢尔排序的C语言实现如下,其中子序列内采用冒泡排序方法:
#include <stdio.h>
//打印数组
void print_arr(int arr[],int len)
{int i;for(i=0;i<len;i++){printf("%5d",arr[i]);}printf("\n");
}
/**
**gap初始值为len/2,一趟排序之后gap=gap/2;
**/
void shell_sort(int arr[],int len)
{int i, j, flag, gap=len,trip=1;int temp;while(gap>1){gap=gap/2;printf("the %d trip:\n",trip);do{flag=0;for(i=0;i<len-gap;i++){j=i+gap;if(arr[i]>arr[j]){temp=arr[i];arr[i]=arr[j];arr[j]=temp;flag=1;}}}while(flag!=0);print_arr(arr,len);trip=trip+1;}
}int main() {int arr[] = { 49,97,38,50,76,65,13,27,25};int len = (int) sizeof(arr) / sizeof(*arr);shell_sort(arr, len);printf("\n\n\nthe result is:\n");print_arr(arr,len);return 0;
}
程序运行结果如下:
算法分析
谢尔排序算法的时间复杂度和gap分割方法有关,经过大量实验测试,其时间复杂度在O(nlog2n)与O(n2)之间,小于O(n3/2)
这篇关于内排序(四)——谢尔(Shell)排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!