[工學(xué)]數(shù)據(jù)結(jié)構(gòu)第23講_插入排序2和交換排序_c-閱讀頁
2024-11-03 00:03本頁面
【正文】 // 一趟增量為 dlta[k]的插入排序 } // ShellSort 希爾排序的時間復(fù)雜度較直接插入排序低。到目前為止，還沒有求得一種最好的增量序列，但有大量的局部結(jié)論。 3）希爾排序算法分析 第 10章 內(nèi)部排序 排序的基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 各種內(nèi)部排序方法的比較 交換排序 1. 起泡排序 2. 快速排序 1）起泡排序的基本思想 小的浮起，大的沉底 具體做法： 第一趟：第 1個與第 2個比較，大則交換；第 2個與第 3個 比較，大則交換， … 關(guān)鍵字最大的記錄交換 到最后一個位置上； 第二趟：對前 n1個記錄進(jìn)行同樣的操作，關(guān)鍵字次大 的記錄交換到第 n1個位置上； 依次類推，則完成排序。 //當(dāng) flag為 0則停止排序 for (int i=n。 i) { //i表示趟數(shù) ， 最多 n1趟 flag=0。 j=i。 R[j]=R[j1]。 flag=1。 } } // Bubblesort 2）起泡排序算法描述 正序： 只需進(jìn)行一趟排序 ， 在排序過程中進(jìn)行 n1次關(guān)鍵字間的比較 ， 且不移動記錄；時間復(fù)雜度為 O(n) 。 總的時間復(fù)雜度為 O(n2) 。 適合于 數(shù)據(jù)較少 的情況 。 試設(shè)想：若能在經(jīng)過一趟排序，使無序序列的長度縮小一半，則必能加快排序的速度。 通常取第一個記錄的值為基準(zhǔn)值或樞軸 。 (3)重復(fù)這兩步直至 low=high為止 。 pivotkey = R[low].key。amp。 R[low] = R[high]。amp。 R[high] = R[low]。 //樞軸記錄到位 return low。 //將 R[low..high]一分為二 QSort(L,low, pivo1)。 // 對高子表遞歸排序 } } // QSort 對記錄序列進(jìn)行快速排序 void QuickSort(Elem R[], int n){ QSort(R, 1, n)。 最壞的情形（每次能劃分成兩個子區(qū)間，但其中一個是空），快速排序的最壞時間復(fù)雜度為 O(n2)。 快速排序是 不穩(wěn)定 的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1