七寝蹈、排序算法

七李命、排序算法

1. 插入排序

把數(shù)據(jù)分成兩部分,前面是有序的(最初只有一個(gè)數(shù)據(jù))箫老,依次將后面無序部分的數(shù)據(jù)插入到前面部分封字,逐漸擴(kuò)大有序部分,直至無序部分的數(shù)據(jù)全部插入到有序部分。

  • 直接插入排序
    將待插數(shù)據(jù)逐一與有序部分的數(shù)據(jù)作比較以確定插入位置周叮。
  • 折半插入排序
    先找出有序部分位于中間的關(guān)鍵字辩撑,與待插數(shù)據(jù)做比較,每比較一次仿耽,就可將有序部分的一半數(shù)據(jù)排除而不需比較合冀,在數(shù)據(jù)量大時(shí)效率很高。
  • 二路插入排序
    先找出有序部分位于數(shù)據(jù)中間的關(guān)鍵字项贺,與待插數(shù)據(jù)做比較君躺,如果插在前半部分,則把前面的數(shù)據(jù)向前移(一路)开缎,反之棕叫,把后面的數(shù)據(jù)向后移(另一路),這樣可以減少移動(dòng)次數(shù)(移動(dòng)的數(shù)據(jù)少于有序部分的二分之一)奕删,但需要一個(gè)額外的數(shù)組俺泣。

實(shí)現(xiàn)

//插入排序類
template<typename D>class InsSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的插入排序類
public:
  void InsertSort()
  {//直接插入排序
    int i, j;
    for(i = 2; i <= length; i++)
      if LT(elem[i].key, elem[i-1].key)  //小于
      {
        elem[0] = elem[i];  //用 elem[0] 存入
        for(j = i-1; LT(elem[0].key, elem[j].key); j--)
          elem[j + 1] = elem[j];
        elem[j + 1] = elem[0];  
      }
  }
  void BInsertSort()
  {//折半插入排序
    int i, j, m, low, high;
    for(i = 2; i <= length; i++)
      if LT(elem[i].key, elem[i-1].key)
      {
        elem[0] = elem[i];
        low = 1; 
        high = i - 1;
        while(low <= high)
        {
          m = (low + high) / 2;
          if LT(elem[0].key, elem[m].key)
            high = m - 1;
          else
            low = m + 1;
        }
        for(j = i - 1; j >= high + 1; j--)
          elem[j + 1] = elem[j];
        elem[high + 1] = elem[0];
      }
  }
  void P2_InsertSort()
  {//二路插入排序
    int i, j, first, final, mid;
    D *d;
    d = new D[length];
    d[0] = elem[1];  //設(shè)第一個(gè)數(shù)據(jù)為 d 中有序的數(shù)據(jù)(存在 [0])
    first = final = 0; //first和final分別指示d中有序數(shù)據(jù)的第一個(gè)位置和最后一個(gè)位置
    for(i = 2; i <= length; i++)
    {
      if (first > final)
        j = length;  //j 是調(diào)整系數(shù)
      else
        j = 0;
      mid = (first + final + j) / 2 % length;  
      if (elem[i].key < d[mid].key)
      {
        j = first;
        first = (first - 1 + length) % length;
        while(elem[i].key > d[j].key)
        {
          d[(j - 1 + length) % length] = d[j];
          j = (j + 1) % length;
        }
        d[(j - 1 + length) % length] = elem[i];
      }
      else
      {
        j = final++;
        while(elem[i].key < d[j].key)
        {
          d[(j + 1) % length] = d[j];
          j = (j - 1 + length) % length;
        }
        d[(j + 1) % length] = elem[i];
      }
    }
    for(i = 1; i <= length; i++)
      elem[i] = d[(first + i - 1) % length];
    delete[] d;
  }
};

2. 冒泡排序

冒泡排序算法是從前到后逐一比較相鄰的兩個(gè)數(shù)據(jù),將小值數(shù)據(jù)交換到前面完残。一趟排序后伏钠,最大值的數(shù)據(jù)即排到最后。如果一趟排序中沒有數(shù)據(jù)交換谨设,說明所有數(shù)據(jù)都已有序熟掂,退出排序過程。

實(shí)現(xiàn)

//冒泡排序類
template<typename D>class BubSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的冒泡排序類
public:
  void BubbleSort()
  {//冒泡排序
    int i, j;
    bool change;
    for(i = length, change = true; i > 1 && change; --i)
    {
      change = false;
      for(j = 1; j < i; ++j)
        if LT(elem[j+1].key, elem[j].key)
        {
          swap(elem[j], elem[j+1]);
          change = true;
        }
    }
  }
};

兩種優(yōu)化思路:

  • 優(yōu)化外層循環(huán):判斷上一趟排序是否發(fā)生交換扎拣,未交換則已有序
  • 優(yōu)化內(nèi)層循環(huán):記住最后一次交換發(fā)生的位置 lastExchange 赴肚,該位置之后的相鄰記錄均已有序

推薦閱讀
冒泡排序算法及其兩種優(yōu)化

3. 簡單選擇排序

簡單選擇排序算法是在一趟排序中找出關(guān)鍵字最小的數(shù)據(jù),并將它交換到正確位置二蓝。

實(shí)現(xiàn)

//簡單選擇排序類
template<typename D>class SelSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的簡單選擇排序類
private:
  int SelectMinKey(int i)
  {//返回在 [i ~ length] 中 key 最小的數(shù)據(jù)的序號(hào)
    int j, k = i;
    KeyType min = elem[i].key;
    for(j = i + 1; j <= length; j++)
      if (elem[j].key < min)
      {
        k = j;
        min = elem[j].key;
      }
      return k;
  }
public:
  void SelectSort()
  {//簡單選擇排序
    int i, j;
    for(i = 1; i < length; i++)
    {
      j = SelectMinKey(i);
      if (i != j)
        swap(elem[i], elem[j]);
    }
  }
};

4. 希爾排序

希爾排序算法是把數(shù)據(jù)等間隔分成若干組誉券。這樣分組的好處是:數(shù)據(jù)在兩兩交換時(shí),不是與相鄰的數(shù)據(jù)交換刊愚,而是與較遠(yuǎn)處的數(shù)據(jù)交換横朋。對(duì)于離正確位置很遠(yuǎn)的數(shù)據(jù),可以減少交換次數(shù)就能到達(dá)正確位置百拓。但這樣分組并不能保證完全有序,所以希爾排序要進(jìn)行幾次晰甚,逐漸減小兩相鄰數(shù)據(jù)的間隔衙传,最后一次排序,所有數(shù)據(jù)在一組中厕九,兩相鄰數(shù)據(jù)沒有間隔蓖捶。由于希爾排序在交換時(shí)有跳躍,所以是一種不穩(wěn)定排序扁远。

實(shí)現(xiàn)

//希爾排序類
template<typename D>class SheSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的希爾排序類
private:
  int n;  //增量序列長度
  int *dt;  //增量序列數(shù)組指針
  void ShellInsert(int dk)
  {//希爾插入排序俊鱼,前后數(shù)據(jù)位置增量是 dk
    for(int i = dk + 1; i <= length; i++)
      if LT(elem[i].key, elem[i - dk].key)
      {
        elem[0] = elem[i];
        for(int j = i - dk; j > 0 && LT(elem[0].key, elem[j].key); j -= dk)
          elem[j + dk] = elem[j];
        elem[j + dk] = elem[0];
      }
  }
public:
  SheSort(int* DT, int N)
  {//構(gòu)造函數(shù)
    n = N;
    dt = new int[N];
    for(int i = 0; i < N; i++)
      dt[i] = DT[i];
    assert(dt[n-1] == 1);  //最后一個(gè)增量值必須等于 1 刻像,否則退出
  }
  ~SheSort()
  {//析構(gòu)函數(shù)
    delete[] dt;
  }
  void ShellSort()
  {//希爾排序
    for(int k = 0; k < n; k++)
    {
      ShellInsert(dt[k]);
      cout << endl << "dt[" << k <<"] = " << dt[k] << ",第" << k+1 
           << "趟排序結(jié)果(僅輸出關(guān)鍵字)" ;
      for(int i = 1; i <= length; i++)
        cout << elem[i].key << " " ;
    }
  }
};

5. 快速排序

快速排序算法是在無序數(shù)據(jù)中任選一個(gè)作為樞軸并闲,將樞軸數(shù)據(jù)放在臨時(shí)單元 [0] 中细睡, low 和 high 指示邊界。凡是比樞軸數(shù)據(jù)小的放在 low 的左邊帝火,low 向右移溜徙;比樞軸數(shù)據(jù)大的放在 high 的右邊, high 向左移犀填。low 和 high 重合之處蠢壹,將樞軸放入。此時(shí)九巡,樞軸左邊元素都不大于樞軸的图贸,樞軸右邊元素的數(shù)據(jù)都不小于樞軸的。樞軸數(shù)據(jù)已到正確位置冕广。遞歸地對(duì)樞軸左右兩部分?jǐn)?shù)據(jù)繼續(xù)進(jìn)行快速排序疏日,遞歸到只有一個(gè)數(shù)據(jù)時(shí)退出〖岩ぃ快速排序也是一種 “不穩(wěn)定排序” 制恍。

實(shí)現(xiàn)

//快速排序類
template<typename D>class QkSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的快速排序類
private:
  int Partition(int low, int high)
  {//以 elem[low] 的關(guān)鍵字作為樞軸,進(jìn)行快速排序過程神凑,返回樞軸所在位置
    int i = low, j = high;
    elem[0] = elem[low];
    while(low < high)
    {//從表的兩端交替掃描
      while(low < high && elem[high].key >= elem[0].key)
        --high;
      elem[low] = elem[high];
      while(low < high && elem[low].key <= elem[0].key)
        ++low;
      elem[high] = elem[low];
    }
    elem[low] = elem[0];
    return low;
  }
  void QSort(int low, int high)
  {//快速排序
    if (low < high)
    {
      int pivotloc = Partition(low, high);
      QSort(low, pivotloc - 1);
      QSort(pivotloc + 1, high);
    }
  }
public:
  void QuickSort()
  {
    QSort(1, length);
  }
};

6. 堆排序

堆排序算法是把順序存儲(chǔ)的數(shù)據(jù)看成是一棵完全二叉樹净神。對(duì)于大頂堆,確保每棵子樹的根結(jié)點(diǎn)都是整個(gè)子樹中最大的溉委,這就保證了根結(jié)點(diǎn)是所有數(shù)據(jù)中的最大值鹃唯,但并不能保證所有數(shù)據(jù)有序。

外部排序往往也使用堆排序算法瓣喊。堆排序算法也可以用于構(gòu)建優(yōu)先隊(duì)列坡慌。堆排序也是一種 “不穩(wěn)定排序” 。

實(shí)現(xiàn)

//堆排序類
template<typename D>class HSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的堆排序類
private:
  void HeapAdjust(int low, int high, bool flag)
  {//已知 elem[low ~ high] 中數(shù)據(jù)的關(guān)鍵字除了elem[low].key之外均滿足大頂堆的定義
   //調(diào)整 elem[low] 的位置藻三,使得都滿足大頂堆定義
    int j;
    elem[0] = elem[low];
    for(j = 2 * low; j <= high; j *= 2)
    {
      if (flag)  //大頂堆洪橘,升序
      {
        if (j < high && LT(elem[j].key, elem[j+1].key))
          j++;
        if (!LT(elem[0].key, elem[j].key))
          break;
      }
      else  //小頂堆,降序
      {
        if (j < high && GT(elem[j].key, elem[j+1].key))
          j++;
        if (!GT(elem[0].key), elem[j].key)
          break;
      }
      elem[low] = elem[j];
      low = j;
    }
    elem[low] = elem[0];
  }
public:
  void HeapSort(bool flag)
  {//堆排序(flag == true : 大頂堆棵帽;flag == false : 小頂堆)
    int i;
    for(i = length / 2; i >= 1; i--)
      HeapAdjust(i, length, flag);
    for(i = length; i >= 2; i--)
    {
      swap(elem[1], elem[i]);
      HeapAdjust(1, i-1, flag);
    }
  }
};

7. 二路歸并排序

二路歸并排序算法首先將所有數(shù)據(jù)分成每組一個(gè)數(shù)據(jù)的情況熄求,這時(shí)每組數(shù)據(jù)都是有序的;然后再把每兩組(二路)有序數(shù)據(jù)歸并成一組有序數(shù)據(jù)逗概,減少了有序數(shù)據(jù)的組數(shù)弟晚,增加每組數(shù)據(jù)的個(gè)數(shù); 最后把所有數(shù)據(jù)歸并到一個(gè)有序數(shù)組。歸并排序需要一個(gè)臨時(shí)數(shù)組用來存放已歸并的數(shù)據(jù)卿城。每次歸并后枚钓,再把臨時(shí)數(shù)組中的數(shù)據(jù)復(fù)制回去。

實(shí)現(xiàn)

//二路歸并排序類
template<typename D>class MerSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的二路歸并排序類
private:
  D *temp;
  void Merge(int low, int m, int high)
  {//將 elem[low, m] 和 elem[m+1, high] 歸并為 elem[low, high]
    int i = low, j = m+1, k = low, p;
    for(; i <= m && j <= high; k++)
      if LQ(elem[i].key, elem[j].key)
        temp[k] = elem[i++];
      else
        temp[k] = elem[j++];
    if (i <= m)
      for(p = 0; p <= m-i; p++)
        temp[k+p] = elem[i+p];
    if (j <= high)
      for(p = 0; p <= high-j; p++)
        temp[k+p] = elem[j+p];
    for(p = low; p <= high; p++)
      elem[p] = temp[p];
  }
  void MSort(int low, int high)
  {//將 elem[low ~ high] 歸并排序?yàn)?temp[low ~ high]
    if (low < high)
    {
      int m = (low + high) / 2;
      MSort(low, m);
      MSort(m+1, high);
      Merge(low, m, high);
    }
  }
public:
  ~MerSort()
  {//析構(gòu)函數(shù)
    if (temp != NULL)
      delete[] temp;
  }
  void MergeSort()
  {//二路歸并排序
    temp = new D[length + 1];
    MSort(1, length);
  }
};

8. 靜態(tài)鏈表排序

兩種算法:

  • Arrange() 算法:順著靜態(tài)鏈表的 next 域依次找到應(yīng)該排在位置 [i] 的數(shù)據(jù)目前所在位置 [p] 瑟押。將 elem[i] 和 elem[p] 交換搀捷,使得 elem[i] 排到正確位置。為了使靜態(tài)鏈表不斷鏈勉耀,令 elem[i].next = p 指煎,即到位置 [p] 去找原來在位置 [i] 的數(shù)據(jù)。該算法在最壞情況下(每個(gè)數(shù)據(jù)都不在正確位置)要做 length-1 次交換便斥。
  • Rearrange() 算法:通過調(diào)用私有成員函數(shù) Sort() 至壤,給私有數(shù)據(jù)成員 adr[] 數(shù)組賦值。adr[i] 的值即是應(yīng)該排在位置 [i] 的數(shù)據(jù)目前所在位置枢纠。通過循環(huán)使得所有數(shù)據(jù)排到正確位置像街。

實(shí)現(xiàn)

//靜態(tài)鏈表插入排序類
template<typename D>class SLinkSort: public SqTable<D>
{//帶模板并繼承 SqTable<D> 的靜態(tài)鏈表插入排序類
private:
  int *adr;
  void Sort()
  {//求得 adr[i] 為靜態(tài)鏈表中第 i 個(gè)最小數(shù)據(jù)的序號(hào)
    int i = 1, p = elem[0].next;
    while(p != 0)
    {
      adr[i++] = p;
      p = elem[p].next;
    } 
  }
public:
  SLinkSort()
  {
    adr = NULL;
  }
  ~SLinkSort()
  {
    if (adr != NULL)
      delete[] adr;
  }
  void MakeTableSorted()
  {//使無序的靜態(tài)鏈表成為有序鏈表
    int i, p, q;
    elem[0].rc.key = INT_MAX;
    elem[0].next = 0;
    for(i = 1; i <= length; i++)
    {
      q = 0;
      p = elem[0].next;
      while LQ(elem[p].rc.key, elem[i].rc.key)
      {
        q = p;
        p = elem[p].next;
      }
      elem[q].next = i;
      elem[i].next = p;
    }
  }
  void Arrange()
  {//Arrange() 算法
    int i, p, q;
    p = elem[0].next;
    for(i = 1; i < length; i++)
    {
      while(p < i)
        p = elem[p].next;
      q = elem[p].next;
      if (p != i)
      {
        swap(elem[p], elem[i]);
        elem[i].next = p;
      }
      p = q;
    }
  }
  void Rearrange()
  {//Rearrange() 算法
    int i, j, k;
    adr = new int[length+1];
    Sort();
    for(i = 1; i < length; i++)
      if (adr[i] != i)
      {
        j = i;
        elem[0] = elem[i];
        while(adr[j] != i)
        {
          k = adr[j];
          elem[j] = elem[k];
          adr[j] = j;
          j = k;
        }
        elem[j] = elem[0];
        dar[j] = j;
      }
  }
};

9. 基數(shù)排序

基數(shù)排序算法采用靜態(tài)鏈表排序算法對(duì)字符串進(jìn)行按位排序。

推薦閱讀
基數(shù)排序

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末晋渺,一起剝皮案震驚了整個(gè)濱河市镰绎,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌木西,老刑警劉巖畴栖,帶你破解...
    沈念sama閱讀 216,372評(píng)論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異八千,居然都是意外死亡吗讶,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,368評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門恋捆,熙熙樓的掌柜王于貴愁眉苦臉地迎上來照皆,“玉大人,你說我怎么就攤上這事沸停∧せ伲” “怎么了?”我有些...
    開封第一講書人閱讀 162,415評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵愤钾,是天一觀的道長瘟滨。 經(jīng)常有香客問我,道長能颁,這世上最難降的妖魔是什么杂瘸? 我笑而不...
    開封第一講書人閱讀 58,157評(píng)論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮劲装,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘。我一直安慰自己占业,他們只是感情好绒怨,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,171評(píng)論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著谦疾,像睡著了一般南蹂。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上念恍,一...
    開封第一講書人閱讀 51,125評(píng)論 1 297
  • 那天六剥,我揣著相機(jī)與錄音,去河邊找鬼峰伙。 笑死疗疟,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的瞳氓。 我是一名探鬼主播策彤,決...
    沈念sama閱讀 40,028評(píng)論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢(mèng)啊……” “哼匣摘!你這毒婦竟也來了店诗?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 38,887評(píng)論 0 274
  • 序言:老撾萬榮一對(duì)情侶失蹤音榜,失蹤者是張志新(化名)和其女友劉穎庞瘸,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體赠叼,經(jīng)...
    沈念sama閱讀 45,310評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡擦囊,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,533評(píng)論 2 332
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了梅割。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片霜第。...
    茶點(diǎn)故事閱讀 39,690評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖户辞,靈堂內(nèi)的尸體忽然破棺而出泌类,到底是詐尸還是另有隱情,我是刑警寧澤底燎,帶...
    沈念sama閱讀 35,411評(píng)論 5 343
  • 正文 年R本政府宣布刃榨,位于F島的核電站,受9級(jí)特大地震影響双仍,放射性物質(zhì)發(fā)生泄漏枢希。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,004評(píng)論 3 325
  • 文/蒙蒙 一朱沃、第九天 我趴在偏房一處隱蔽的房頂上張望苞轿。 院中可真熱鬧茅诱,春花似錦、人聲如沸搬卒。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽契邀。三九已至摆寄,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間坯门,已是汗流浹背微饥。 一陣腳步聲響...
    開封第一講書人閱讀 32,812評(píng)論 1 268
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留古戴,地道東北人欠橘。 一個(gè)月前我還...
    沈念sama閱讀 47,693評(píng)論 2 368
  • 正文 我出身青樓,卻偏偏與公主長得像允瞧,于是被迫代替她去往敵國和親简软。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,577評(píng)論 2 353

推薦閱讀更多精彩內(nèi)容