|
1、希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。 2、希尔排序基本思想： 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。 该方法实质上是一种分组插入方法。 给定实例的shell排序的排序过程 假设待排序文件有10个记录，其关键字分别是： 49，38，65，97，76，13，27，49，55，04。 增量序列的取值依次为： 5，3，1 3、缩小增量法 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序 排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止 初始：d=5 49 38 65 97 76 13 27 49* 55 04 49 13 |-------------------| 38 27 |-------------------| 65 49* |-------------------| 97 55 |-------------------| 76 04 |-------------------| 一趟结果 13 27 49* 55 04 49 38 65 97 76 d=3 13 27 49* 55 04 49 38 65 97 76 13 55 38 76 |------------|------------|------------| 27 04 65 |------------|------------| 49* 49 97 |------------|------------| 二趟结果 13 04 49* 38 27 49 55 65 97 76 d=1 13 04 49* 38 27 49 55 65 97 76 |----|----|----|----|----|----|----|----|----| 三趟结果 04 13 27 38 49* 49 55 65 76 97 -------------------------------------------------------------------------------------------- 例如对503,17,512,908,170,897,275,653,462，154，509，612，677，765，703，94排序的C语言算法 ================================================ 功能：希尔排序 输入：数组名称（也就是数组首地址）、数组中元素个数 ================================================ */ /* ==================================================== 算法思想简单描述： 在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点， 并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为 增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除 多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现 了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中 记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量 对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成 一组，排序完成。 下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量， 以后每次减半，直到增量为1。 希尔排序是不稳定的。 4、Shell排序 Shell排序的算法实现: 1． 不设监视哨的算法描述 void ShellPass(SeqList R，int d) {//希尔排序中的一趟排序，d为当前增量 for(i=d+1;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区 if(R[ i ].key<R[i-d].key){ R[0]=R[i];j=i-d； //R[0]只是暂存单元，不是哨兵 do {//查找R的插入位置 R[j+d]=R[j]； //后移记录 j=j-d； //查找前一记录 }while(j>0&&R[0].key<R[j].key)； R[j+d]=R[0]； //插入R到正确的位置上 } //endif 5、算法分析 优劣： 不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)， 没有快速排序算法快 O(N*(logN))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。 专家门提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当N值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。 时间性能： 1．增量序列的选择 Shell排序的执行时间依赖于增量序列。 好的增量序列的共同特征： ① 最后一个增量必须为1； ② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。 有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。 2．Shell排序的时间性能优于直接插入排序 希尔排序的时间性能优于直接插入排序的原因： ①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 ②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。 ③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。 因此，希尔排序在效率上较直接插人排序有较大的改进。 稳定性 排序前一个序列中,如果出现N个与关键字相同的数据,那么排序后仍然按照原先序列的排列顺序排列,就说这个算法是稳定的,反之就是不稳定的。通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj, Ai原来在位置前，排序后Ai还是要在Aj位置前。 6、希尔分析 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。 7、希尔排序的JAVA实现 public class Test { public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; public static void main(String args[]) { int i; // 循环计数变量 int Index = a.length;// 数据索引变量 System.out.print("排序前: "); for (i = 0; i < Index - 1; i++) System.out.printf("%3s ", a[i]); System.out.println(""); ShellSort(Index - 1); // 选择排序 // 排序后结果 System.out.print("排序后: "); for (i = 0; i < Index - 1; i++) System.out.printf("%3s ", a[i]); System.out.println(""); } public static void ShellSort(int Index) { int i, j, k; // 循环计数变量 int Temp; // 暂存变量 boolean Change; // 数据是否改变 int DataLength; // 分割集合的间隔长度 int Pointer; // 进行处理的位置 DataLength = (int) Index / 2; // 初始集合间隔长度 while (DataLength != 0) // 数列仍可进行分割 { // 对各个集合进行处理 for (j = DataLength; j < Index; j++) { Change = false; Temp = a[j]; // 暂存Data[j]的值,待交换值时用 Pointer = j - DataLength; // 计算进行处理的位置 // 进行集合内数值的比较与交换值 while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) { a[Pointer + DataLength] = a[Pointer]; // 计算下一个欲进行处理的位置 Pointer = Pointer - DataLength; Change = true; if (Pointer < 0 || Pointer > Index) break; } // 与最后的数值交换 a[Pointer + DataLength] = Temp; if (Change) { // 打印目前排序结果 System.out.print("排序中: "); for (k = 0; k < Index; k++) System.out.printf("%3s ", a[k]); System.out.println(""); } } DataLength = DataLength / 2; // 计算下次分割的间隔长度 } } } 8、希尔排序的C#实现 using System; public class ShellSorter { public void Sort(int[] list) { int inc; for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ; for (; inc > 0; inc /= 3) { for (int i = inc + 1; i <= list.Length; i += inc) { int t = list[i - 1]; int j = i; while ((j > inc) && (list[j - inc - 1] > t)) { list[j - 1] = list[j - inc - 1]; j -= inc; } list[j - 1] = t; } } } } public class MainClass { public static void Main() { int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 }; ShellSorter sh = new ShellSorter(); sh.Sort(iArrary); for (int m = 0; m <= 13; m++) Console.WriteLine("{0}", iArrary[m]); Console.ReadKey(); } } for (int i = k; i < len; i++) { if (arry[i - k] > arry[i]) { int temp; temp = arry[i - k]; arry[i - k] = arry[i]; arry[i] = temp; } } } foreach (int i in arry) { Console.WriteLine(i); } Console.ReadLine(); |
|
|
