4、【经典算法】希尔排序
一、希尔排序介绍希尔排序(Shell Sort)是插入排序的一种,它是针对直接插入排序算法的改进。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。 希尔排序实质上是一种分组插入方法。它的基本思想是:对于n个待排序的数列,取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列,所有距离为gap的倍数的记录放在同一个组中;然后,对各组内的元素进行直接插入排序。 这一趟排序完成之后,每一个组的元素都是有序的。然后减小gap的值,并重复执行上述的分组和排序。重复这样的操作,当gap=1时,整个数列就是有序的。 二、希尔排序的时间复杂度和稳定性希尔排序时间复杂度 希尔排序稳定性 三、希尔排序的C++实现main.cpp 1 #include <iostream> 2 using namespace std; 3 4 /* 5 * 希尔排序 6 * 7 * 参数说明: 8 * a -- 待排序的数组 9 * n -- 数组的长度 10 */ 11 void shellSort1(int* a,int n) 12 { 13 int i,j,gap; 14 15 // gap为步长,每次减为原来的一半。 16 for (gap = n / 2; gap > 0; gap /= 2) 17 { 18 // 共gap个组,对每一组都执行直接插入排序 19 for (i = 0 ;i < gap; i++) 20 { 21 for (j = i + gap; j < n; j += gap) 22 { 23 // 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。 24 if (a[j] < a[j - gap]) 25 { 26 int tmp = a[j]; 27 int k = j - gap; 28 while (k >= 0 && a[k] > tmp) 29 { 30 a[k + gap] = a[k]; 31 k -= gap; 32 } 33 a[k + gap] = tmp; 34 } 35 } 36 } 37 38 } 39 } 40 41 /* 42 * 对希尔排序中的单个组进行排序 43 * 44 * 参数说明: 45 * a -- 待排序的数组 46 * n -- 数组总的长度 47 * i -- 组的起始位置 48 * gap -- 组的步长 49 * 50 * 组是"从i开始,将相隔gap长度的数都取出"所组成的! 51 */ 52 void groupSort(int* a,int n,int i,int gap) 53 { 54 int j; 55 56 for (j = i + gap; j < n; j += gap) 57 { 58 // 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。 59 if (a[j] < a[j - gap]) 60 { 61 int tmp = a[j]; 62 int k = j - gap; 63 while (k >= 0 && a[k] > tmp) 64 { 65 a[k + gap] = a[k]; 66 k -= gap; 67 } 68 a[k + gap] = tmp; 69 } 70 } 71 } 72 73 /* 74 * 希尔排序 75 * 76 * 参数说明: 77 * a -- 待排序的数组 78 * n -- 数组的长度 79 */ 80 void shellSort2(int* a,int n) 81 { 82 int i,gap; 83 84 // gap为步长,每次减为原来的一半。 85 for (gap = n / 2; gap > 0; gap /= 2) 86 { 87 // 共gap个组,对每一组都执行直接插入排序 88 for (i = 0 ;i < gap; i++) 89 groupSort(a,n,i,gap); 90 } 91 } 92 93 int main() 94 { 95 int i; 96 int a[] = {80,30,60,40,20,10,50,70}; 97 int ilen = (sizeof(a)) / (sizeof(a[0])); 98 99 cout << "before sort:"; 100 for (i=0; i<ilen; i++) 101 cout << a[i] << " "; 102 cout << endl; 103 104 shellSort1(a,ilen); 105 //shellSort2(a,ilen); 106 107 cout << "after sort:"; 108 for (i=0; i<ilen; i++) 109 cout << a[i] << " "; 110 cout << endl; 111 112 return 0; 113 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |