• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            插入排序是一種簡單的排序方法,因為的實現比較簡單,所以在數據量較少時應用很廣泛。插入排序根據其插入的不同方式,可以分為直接插入排序,折半插入排序,2-路插入排序,表插入排序和希爾排序。在這里我將一一寫出各種插入排序的算法代碼。
            直接插入排序
            template <class T>
            void InsertSort(T a[], int len)
            {
                  int i, j;
                  T temp;
                  for (i=1; i<len; i++)
                  {
                        temp = a[i];
                        for (j=i-1; j>=0 && a[j]>temp; j--)//元素后移
                              a[j+1] = a[j];
                        a[j+1] = temp;  //插入
                  }
            }
                  有些算法把a[0]設置為臨時數據存放處(即原數組中a[0]未存儲元素),這樣就可以少進行一些判斷,在數據量較大時可以節省一些時間,算法如下:
            template <class T>
            void InsertSort(T a[], int len)
            {
                  int i, j;
                  for (i=1; i<len; i++)
                  {
                        a[0] = a[i];
                        for (j=i-1; a[j]>temp; j--)
                              a[j+1] = a[j];
                        a[j+1] = temp;
                  }
            }
            折半插入排序法
                  由于插入排序的基本操作是在一個有序表中進行查找和插入,則這個查找操作可以利用折半查找來實現。但是折半插入排序僅減少了元素間的比較次數,而元素的移動次數不變,因此折半插入排序法的時間復雜度仍為O(n^2)。算法如下:
            template <class T>
            void HalfInsertSort(T a[], int len)
            {
                  int i, j;
                  int low, high, mid;
                  T temp;
                  for (i=1; i<len; i++)
                  {
                        temp = a[i];
                        low = 0;
                        high = i - 1;
                        while (low <= high) //在a[low。。。high]中折半查找有序插入的位置
                        {
                              mid = (low + high) / 2;
                              if (a[mid] > temp)
                                    high = mid - 1;
                              else
                                    low = mid + 1;
                        } //while
                        
                        for (j=i-1; j>high; j--)//元素后移
                              a[j+1] = a[j];
                        a[high+1] = temp; //插入
                  }//for
            }

            希爾排序法
                  希爾排序法又稱縮小增量排序法,它也是插入排序類的方法,但在時間效率上較前面幾種插入排序算法有較大的改進。
                  希爾排序法通過比較相距一定間隔的元素來工作,各趟比較所用的距離隨著算法的進行而減小,直到比較相鄰元素的最后一趟排序為止。算法如下:
            template <class T>
            void ShellSort(T a[], int len)
            {
                  for (int increment=len/2; increment>0; increment/=2)
                  {
                        for (int i=increment; i<len; i++)
                        {
                              T temp = a[i];
                              int j = i;
                              for (; j>=increment; j-=increment)//元素后移
                              {
                                    if (temp < a[j-increment])
                                          a[j] = a[j-increment];
                                    else
                                          break;
                              }
                              a[j] = temp; //插入
                        }//for
                  }//for
            }
            注:缺2-路插入排序和表插入排序,有意者請補上!謝謝!
            Posted on 2006-06-20 23:22 夢想飛揚 閱讀(3361) 評論(1)  編輯 收藏 引用

            Feedback

            # re: 我所理解的插入排序算法  回復  更多評論   

            2008-10-24 16:16 by 么樣
            你就是一個傻逼,要寫就寫全,就會寫最簡單的
            日韩一区二区久久久久久| 国产精品乱码久久久久久软件| 蜜臀av性久久久久蜜臀aⅴ | 波多野结衣中文字幕久久| 97久久婷婷五月综合色d啪蜜芽| 伊人久久成人成综合网222| 国产综合精品久久亚洲| 国产99久久久国产精免费| 国产精品18久久久久久vr | 国产精品久久久久久搜索| 亚洲精品蜜桃久久久久久| 一本一道久久综合狠狠老| 色综合久久久久综合体桃花网| 久久99热这里只有精品国产| 日产精品久久久久久久性色| 91久久婷婷国产综合精品青草| 91久久精品视频| 污污内射久久一区二区欧美日韩| 国产精品久久久久久久人人看 | 91精品国产乱码久久久久久| 四虎国产精品免费久久5151| 久久精品18| 嫩草伊人久久精品少妇AV| 久久狠狠高潮亚洲精品| 国内精品久久久久久麻豆| 伊人久久大香线蕉成人| 久久96国产精品久久久| 无码8090精品久久一区| 精品无码久久久久久午夜| 亚洲国产成人久久笫一页| 97久久精品无码一区二区| 热综合一本伊人久久精品 | 国产精品成人精品久久久| 思思久久99热只有频精品66| 日韩精品久久无码人妻中文字幕| 精品久久8x国产免费观看| 久久亚洲精品无码观看不卡| 亚洲av伊人久久综合密臀性色| 人人狠狠综合久久亚洲88| 国产精品久久久久久久久软件| 久久综合伊人77777|