為什么取名為梳，可能每個(gè)梳都有自己的 gap 吧，大梳子 gap 大一點(diǎn)，小梳子 gap 小一點(diǎn)。上一篇我們看到雞尾酒排序是在冒泡排序上做了一些優(yōu)化，將單向的比較變成了雙向，同樣這里的梳排序也是在冒泡排序上做了一些優(yōu)化。
冒泡排序上我們的選擇是相鄰的兩個(gè)數(shù)做比較，就是他們的 gap 為 1，其實(shí)梳排序提出了不同的觀點(diǎn)，如果將這里的 gap 設(shè)置為一定的大小，效率反而必 gap=1 要高效的多。
下面我們看看具體思想，梳排序有這樣一個(gè) 1.3 的比率值，每趟比較完后，都會(huì)用這個(gè) 1.3 去遞減 gap，直到 gap=1 時(shí)變成冒泡排序，這種算法比冒泡排序的效率要高效的多，時(shí)間復(fù)雜度為 O(N2/2p) 這里的 p 為增量，是不是跟希爾排序有點(diǎn)點(diǎn)神似。
比如下面有一組數(shù)據(jù): 初始化的 gap=list.count/1.3， 然后用這個(gè) gap 作為數(shù)組下標(biāo)進(jìn)行跨數(shù)字比較大小，前者大于后者則進(jìn)行交換，每一趟排序完成后都除以 1.3, 最后一直除到 gap=1.

最后我們的數(shù)組就排序完畢了，下面看代碼：

 using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 using System.Xml.Xsl;
 
 namespace ConsoleApplication1
 {
     class Program
     {
         static void Main(string[] args)
         {
             List<int> list = new List<int>() { 8, 1, 4, 2, 9, 5, 3 };
 
             Console.WriteLine("\n排序前 => {0}\n", string.Join(",", list));
 
             list = CombSort(list);
 
             Console.WriteLine("\n排序后 => {0}\n", string.Join(",", list));
 
             Console.Read();
         }
 
         /// <summary>
         /// 梳排序
         /// </summary>
         /// <param name="list"></param>
         /// <returns></returns>
         static List<int> CombSort(List<int> list)
         {
             //獲取最佳排序尺寸： 比率為 1.3
             var step = (int)Math.Floor(list.Count / 1.3);
 
             while (step >= 1)
             {
                 for (int i = 0; i < list.Count; i++)
                 {
                     //如果前者大于后者，則進(jìn)行交換
                     if (i + step < list.Count && list[i] > list[i + step])
                     {
                         var temp = list[i];
 
                         list[i] = list[i + step];
 
                         list[i + step] = temp;
                     }
 
                     //如果越界，直接跳出
                     if (i + step > list.Count)
                         break;
                 }
 
                 //在當(dāng)前的step在除1.3
                 step = (int)Math.Floor(step / 1.3);
             }
 
             return list;
         }
     }
 }

————————————————

版權(quán)聲明：本文為CSDN博主「神仙別鬧」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接及本聲明。

原文鏈接：https://blog.csdn.net/s1t16/article/details/134640675