軟件技術基礎-數(shù)據(jù)結構-資料下載頁
2025-07-22 09:40本頁面
【正文】 4,74],查找關鍵字值為 60的元素。 ⑴幾個排序的基本概念 ?排序： 排序是將一組數(shù)據(jù)元素按排序碼遞增或遞減排列的一種運算操作。 ?排序碼： 排序的依據(jù)是排序碼，排序碼指數(shù)據(jù)元素中的一個或多個關鍵字。 ?內(nèi)部排序和外部排序： 內(nèi)排序 指在計算機內(nèi)存中進行的排序； 外排序 指使用計算機外存進行的排序。 ?排序算法的穩(wěn)定性： 如果待排序的序列中存在多個具有相同排序碼的數(shù)據(jù)元素，經(jīng)過排序后數(shù)據(jù)元素的相對次序保持不變，則稱這種排序算法是穩(wěn)定的；若經(jīng)過排序后數(shù)據(jù)元素的相對次序發(fā)生改變，則稱這種排序算法是不穩(wěn)定的。 ⑵內(nèi)排序方法 ①插入排序：分為直接插入排序、折半插入排序、2路插入排序、表插入排序和希爾 (Shell)排序。 ②選擇排序：分為簡單選擇排序 (或稱選擇排序 )、樹形選擇排序和堆排序。 ③交換排序：分為冒泡排序和快速排序。 ④歸并排序：歸并排序分為 2路歸并排序和 k路歸并排序。 ⑵幾種最常用、最簡單的排序方法： 插入排序 基本思想： 將待排序的記錄插入到已排序的子文件中，使得插入之后得到的子文件仍然有序。 ?插入一個記錄，首先要對有序子文件進行查找，以確定這個記錄的插入位置。 ?按查找方式不同，插入排序又分為線性插入排序(順序查找 )和折半插入排序 (折半查找 )。 插入排序舉例： 選擇排序 基本思想： 從待排序文件 r[1..n]中，確定最小關鍵字 Rmin，與某個元素交換位置。 第一趟： 在 n個記錄中按排序碼選出最小關鍵字Rmin，與 r1元素交換位置； 第二趟： 在 n1個記錄中選出最小的元素 Rmin，與r2元素交換位置； 第 i趟： 在 r[1..n]中選出最小的元素 Rmin，與 ri元素交換位置； 如此反復，使得 r[1..n]有序。 選擇排序 舉例： 冒泡排序 基本思想： 設待排序文件 r[1..n]。 第一趟： 從 Rl開始兩兩比較 Ri+1排序碼大小，若 Ri＞ Ri+1則交換 Ri和 Ri+l的位置 。 第一趟排序后 Rn為最大元素。 第二趟： 從 Rl開始兩兩比較 Ri排序碼的大小，若 Ri＞ Ri+1則交換 Ri和 Ri+l的位置。第二趟排序后 Rn1為次大元素。 如此反復經(jīng) n1趟排序后，使得 r[1..n]有序。 冒泡排序舉例： 快速排序 基本思想： 在 r[1..n]中，確定一個 r[i]。 經(jīng)過比較和移動，將 r[i]放到“中間”某個位置上，使 r[i]左邊所有記錄的關鍵字 =r[i].key， r[i]右邊所有記錄的關鍵字 =r[i].key。以 r[i]為界 ,將文件 r[1..n]劃分為左、右兩個子文件。 ?再用同樣的方法分別對這兩個子文件進行劃分，得到 4個更小的子文件。 ?如此繼續(xù)，使每個子文件只有一個記錄為止，使得 r[1..n]有序。 ④歸并排序 ?歸并排序是把兩個或兩個以上有序的序列合并為一個有序的序列，若是對兩個有序序列進行歸并，又稱為 2路歸并。 基本思想： 將有 n個元素的原始序列看作 n個有序子序列，每個子序列的長度為 1。從第一個子序列開始把相鄰的子序列兩兩合并，得到 n/2個，長度為 2或 1的子序列，這一過程稱為一次歸并排序。對第一次歸并排序后的 n/2個子序列采用上述方法，繼續(xù)順序成對歸并，如此重復最后得到長度為 n的有序序列。歸并排序舉例： 幾種排序比較 ?穩(wěn)定性： 插入排序、歸并排序和冒泡排序穩(wěn)定性好；選擇排序不穩(wěn)定。 ?綜合情況 ：歸并排序速度較快，插入排序和冒泡排序速度較慢。 各種排序法選用依據(jù)： ①數(shù)據(jù)規(guī)模 n大 ，內(nèi)存足夠大，有穩(wěn)定要求時，可使用歸并排序。 ②數(shù)據(jù)規(guī)模 n較小，有穩(wěn)定要求，可用插入排序。 ③數(shù)據(jù)規(guī)模 n較小，不要求穩(wěn)定，可用選擇排序。
外語相關推薦
鄂ICP備17016276號-1