這是數(shù)據(jù)結(jié)構(gòu)基數(shù)排序ppt，包括了內(nèi)部排序，概述，插入排序，交換排序，選擇排序，歸并排序，基數(shù)排序，什么是排序等內(nèi)容，歡迎點(diǎn)擊下載。

數(shù)據(jù)結(jié)構(gòu)基數(shù)排序ppt是由紅軟PPT免費(fèi)下載網(wǎng)推薦的一款課件PPT類(lèi)型的PowerPoint.

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容vnJ紅軟基地
第10章 內(nèi)部排序vnJ紅軟基地
10.1   概述vnJ紅軟基地
10.1   概述vnJ紅軟基地
4. 什么叫內(nèi)部排序？什么叫外部排序？vnJ紅軟基地
6. 順序存儲(chǔ)（順序表）的抽象數(shù)據(jù)類(lèi)型如何表示？vnJ紅軟基地
7.  內(nèi)部排序的算法有哪些？vnJ紅軟基地
10.2 插入排序vnJ紅軟基地
1)  直接插入排序vnJ紅軟基地
例2：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)寫(xiě)出直接插入排序的具體實(shí)現(xiàn)過(guò)程。vnJ紅軟基地
Void InsertSort(SqList  &L)vnJ紅軟基地
{  // 對(duì)順序表L做直接插入排序vnJ紅軟基地
    for ( i=2; i<=L.length; ++i )vnJ紅軟基地
       if (  LT(L.r[i].key，L.r[i-1].key) ) vnJ紅軟基地
                                         // “<“，需將L.r[i]插入有序子表vnJ紅軟基地
         {  L.r[0] = L.r[i];          // 復(fù)制為哨兵vnJ紅軟基地
            L.r[i] = L.r[i-1];vnJ紅軟基地
            for( j=i-2; LT(L.r[0].key，L.r[i].key);--j )vnJ紅軟基地
               L.r[ j+1] = L.r[ j];   // 記錄后移vnJ紅軟基地
            L.r[ j+1] = L.r[0];     // 插入到正確位置vnJ紅軟基地
          }vnJ紅軟基地
}  // InsertSortvnJ紅軟基地
直接插入排序的算法分析vnJ紅軟基地
2） 折半插入排序vnJ紅軟基地
Void  BInsertSort (SqList  &L)  // 折半插入排序vnJ紅軟基地
{  for ( i=2；i<=L.length；++i )vnJ紅軟基地
   {  L.r[0] = L.r[ i ]；      // 將L.r [i] 暫存到L.r[0]vnJ紅軟基地
      low=1；high=i-1；vnJ紅軟基地
      while (low<=high)     //  比較，折半查找插入位置vnJ紅軟基地
      {  m=(low+high)/2；        // 折半vnJ紅軟基地
         if (LT(L.r[0].key，L.r[m].key))  high=m-1；//插入點(diǎn)在低半?yún)^(qū)vnJ紅軟基地
         else   low=m+1；                  // 插入點(diǎn)在高半?yún)^(qū)vnJ紅軟基地
       } // whilevnJ紅軟基地
      for (j=i-1；j>=high+1；--j)  L.r [j+1] = L.r [j]；// 記錄后移vnJ紅軟基地
      L.r [high+1] = L.r [0]；                       // 插入vnJ紅軟基地
    }  // forvnJ紅軟基地
}  // BInsertSortvnJ紅軟基地
折半插入排序的算法分析vnJ紅軟基地
討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？vnJ紅軟基地
答：直接插入不僅可行，而且還無(wú)需移動(dòng)元素，時(shí)間效率更高！但鏈表無(wú)法“折半”！vnJ紅軟基地
折半插入排序的改進(jìn)——2-路插入排序見(jiàn)教材P267。vnJ紅軟基地
  （1）基本思想： P267vnJ紅軟基地
  （2）舉        例：P268  圖10.2vnJ紅軟基地
  （3）算法分析：移動(dòng)記錄的次數(shù)約為n2/8 vnJ紅軟基地
             2-路插入排序只能減少移動(dòng)記錄的次數(shù)，而不能絕對(duì)避免移動(dòng)記錄。實(shí)現(xiàn)是借助循環(huán)向量。vnJ紅軟基地
=>  若希望在排序過(guò)程中不移動(dòng)記錄，只有改變存儲(chǔ)結(jié)構(gòu)，進(jìn)行表插入排序。vnJ紅軟基地
4）希爾（shell）排序（又稱(chēng)縮小增量排序）vnJ紅軟基地
例：關(guān)鍵字序列 T=(49，38，65，97， 76， 13， 27， 49*，55，  04），請(qǐng)寫(xiě)出希爾排序的具體實(shí)現(xiàn)過(guò)程。vnJ紅軟基地
時(shí)間效率：vnJ紅軟基地
附：希爾排序算法分析vnJ紅軟基地
希爾排序算法（其中某一趟的排序操作）vnJ紅軟基地
課堂練習(xí)：vnJ紅軟基地
原始序列： 256，301，751，129，937，863，742，694，076，438vnJ紅軟基地
原始序列： 256，301，751，129，937，863，742，694，076，438vnJ紅軟基地
10.3 交換排序vnJ紅軟基地
 1)  冒泡排序vnJ紅軟基地
for(j=0;j<n;j++)vnJ紅軟基地
  for(i=0;i<n-1-j;i++) vnJ紅軟基地
      if (a[i]>a[i+1])        // 需要互換vnJ紅軟基地
       {   vnJ紅軟基地
                 t=a[i];vnJ紅軟基地
                 a[i]=a[i+1];vnJ紅軟基地
                 a[i+1]=t;vnJ紅軟基地
             }vnJ紅軟基地
冒泡排序的算法分析vnJ紅軟基地
2） 快速排序vnJ紅軟基地
例1：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出快速排序的算法步驟。vnJ紅軟基地
討論1.這種不斷劃分子表的過(guò)程，計(jì)算機(jī)如何自動(dòng)實(shí)現(xiàn)？vnJ紅軟基地
例2：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出快速排序算法的一趟實(shí)現(xiàn)過(guò)程。vnJ紅軟基地
一趟快速排序算法流程圖vnJ紅軟基地
整個(gè)快速排序的遞歸算法：vnJ紅軟基地
例3：以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫(xiě)出執(zhí)行快速算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。vnJ紅軟基地
快速排序算法詳細(xì)分析：vnJ紅軟基地
討論2. “快速排序”是否真的比任何排序算法都快？vnJ紅軟基地
10.4   選擇排序vnJ紅軟基地
1）簡(jiǎn)單選擇排序vnJ紅軟基地
例：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)給出簡(jiǎn)單選擇排序的具體實(shí)現(xiàn)過(guò)程。vnJ紅軟基地
簡(jiǎn)單選擇排序的算法如下：（亦可參見(jiàn)教材P276）vnJ紅軟基地
2） 錦標(biāo)賽排序  (又稱(chēng)樹(shù)形選擇排序)vnJ紅軟基地
第一趟：vnJ紅軟基地
第二趟：vnJ紅軟基地
第三趟：vnJ紅軟基地
第四趟：vnJ紅軟基地
第五趟：vnJ紅軟基地
第六趟：vnJ紅軟基地
第七趟：vnJ紅軟基地
算法分析：vnJ紅軟基地
3） 堆排序vnJ紅軟基地
例：vnJ紅軟基地
2. 怎樣建堆？vnJ紅軟基地
Void HeapAdjust(HeapType &H， int s，int m)vnJ紅軟基地
{  // vnJ紅軟基地
   rc = H.r[s];vnJ紅軟基地
   for ( j=2*s; j<=m; j*=2)   // 沿key較大的孩子結(jié)點(diǎn)向下篩選vnJ紅軟基地
   {   if (  j<m && LT(H.r[ j].key， H.r[ j+1].key) ) vnJ紅軟基地
             ++j ;                         // j 為key較大的記錄的下標(biāo)vnJ紅軟基地
     if (!LT(rc.key，H.r[ j].key))  break; // rc應(yīng)插入在位置s上vnJ紅軟基地
       H.r[s] = H.r[ j];   s=j;vnJ紅軟基地
    }vnJ紅軟基地
    H.r[s]=rc;     // 插入vnJ紅軟基地
 }vnJ紅軟基地
3. 怎樣進(jìn)行堆排序？vnJ紅軟基地
例：對(duì)剛才建好的大根堆進(jìn)行排序：vnJ紅軟基地
堆排序的算法vnJ紅軟基地
附1：基于初始堆進(jìn)行堆排序的算法步驟：vnJ紅軟基地
附2：算法流程vnJ紅軟基地
堆排序算法分析：vnJ紅軟基地
10.5  歸并排序vnJ紅軟基地
一趟歸并排序算法: (兩路有序并為一路)     參見(jiàn)教材P283vnJ紅軟基地
遞歸形式的兩路歸并排序算法:          參見(jiàn)教材P284              (一路無(wú)序變?yōu)橛行?vnJ紅軟基地
歸并排序算法分析：vnJ紅軟基地
各種內(nèi)部排序方法的比較    (教材P289）vnJ紅軟基地
討論：若初始記錄基本無(wú)序，則選用哪些排序方法比較適合？若初始記錄基本無(wú)序，則最好選用哪些排序方法？vnJ紅軟基地

數(shù)據(jù)結(jié)構(gòu)查找ppt：這是數(shù)據(jù)結(jié)構(gòu)查找ppt，包括了基本概念與術(shù)語(yǔ)，靜態(tài)查找表，動(dòng)態(tài)查找表，哈希表查找，小結(jié)與習(xí)題等內(nèi)容，歡迎點(diǎn)擊下載。

數(shù)據(jù)結(jié)構(gòu)ppt最短路徑：這是數(shù)據(jù)結(jié)構(gòu)ppt最短路徑，包括了最短路徑的定義，Dijkstra算法，F(xiàn)loyd算法，F(xiàn)loyd算法——C++描述等內(nèi)容，歡迎點(diǎn)擊下載。

數(shù)據(jù)庫(kù)答辯ppt：這是數(shù)據(jù)庫(kù)答辯ppt，包括了數(shù)據(jù)庫(kù)用戶(hù)管理和安全設(shè)置，數(shù)據(jù)庫(kù)日志、作業(yè)與警報(bào)管理，復(fù)雜數(shù)據(jù)庫(kù)備份和數(shù)據(jù)庫(kù)維護(hù)，收獲與體會(huì)等內(nèi)容，歡迎點(diǎn)擊下載。