C語言易錯點總結（四）

9.排序技術
(1)交換類排序技術
    ①冒泡排序法   
  冒泡排序的思想如下:
      線上性表中依次查找相鄰的資料元紫,将表中最大的元素不斷往後移動,反複操作直到消除所有逆序，此時,該表已經排序結束。
    假設線性表的長度為n,則在最壞的情況下，冒泡排序需要經過n/2遍的從前往後的掃描和n/2遍的從後往前掃描，需要比較n(n-1)/2次，其數量級為n⒉
    ②快速排序法
快速排序法。
      快速排序法的基本思想如下:
      線上性表中逐個選取元素,将線性表進行分制，直到所有元素全部選取完畢此時線性我已經排序結束。需要比較n(n-1)/2次

(2)插入類排序法
      插人排序是指將無序序列中的各元素依次插人到已經有序的線性表中。  
     ①簡單插人排序法。
      簡單插人排序是把n個待排序的元素看成一個有序表和一個無序表，開始時，有序表隻包含一個元素，而無序表包含n-1個元素，每次取無序表中的第一個元素插人到有序表中的正确位置， 使之成為增加一個元素的新的有序表。插人元素時,插人位置及其後的記錄依次向後移動。最後有序表的長度為n,而無序表為空，此時排序完成。
      在簡單插人排序中,每一次比較後最多移掉一個逆序，是以，該排序方法的效率與冒泡排序法相同。在最壞的情況下，簡單插人排序需要n(n-1)/2次比較。
    ②希爾排序法。
      ​希爾排序法的基本思路為:将整個無序序列分割成若千個小的子序列并分别進行插人排序。
希爾排序的效率與所選取的增量序列有關

(3)選擇類排序法
    選擇類排序法的基本思想是通過每越從待排字序列中選出值最 小的元家，按順序放在已排好序的有字子表的後面，直到全  序部序列滿足排序要求為止
    ①簡單選擇排序法。
    簡單選擇排序的基本思想是:首先從所有n個待排序的資料元素中選擇最小的元素，将該元素與第一個元素交換，再從剩下的n-1個元素中選出最小的元素與第二個元素交換。重複這樣的操作直到所有的元素有序為止。
簡單選擇排序在最壞情況下需要比較n(n-1)/2次。    ②堆排序法。
堆排序的方法如下:
①将一個無序序列建成堆;
②将堆頂元素與堆中最後一個元素交換。忽略已經交換到最後的那個元素，考慮前n-1個元素構成的子序列，隻有左、右子樹是堆，可以将該子樹調整為堆。這樣重複去做第二步，直到剩下的子序列為空時止。
在最壞的情況下，堆排序需要比較的次數為nlog2n。
總結：線性表排序中，堆排序的比較次數為nlog2n；快速排序、冒泡排序、直接插入排序、簡單選擇排序比較次數均為​n(n-1)/2次；二分法為log2n；順序查找為n

10.資料流圖與程式流程圖
資料流圖------>資料流
程式流程圖---->控制流
要注意差別

11.将E-R轉化為資料模型屬于邏輯設計階段

12.算法複雜度指所需要的計算工作量
    計算工作量指用所執行的基本運算次數的度量

13.白盒測試與黑盒測試
    白盒測試方法：邏輯覆寫測試（語句覆寫、路徑覆寫、判斷覆寫、條件覆寫）、基本路徑測試等
    黑盒測試方法：等價類劃分法、邊界值分析法、錯誤推理法、因果圖等