數(shù)據(jù)結(jié)構(gòu)上機(jī)基本習(xí)題-展示頁
2025-05-25 21:27本頁面
【正文】 i j 快速排序中的一趟劃分 i 38 65 97 13 27 49 55 1 2 3 4 5 6 7 8 04 9 49 pivot j a[i]與 pivot比較， a[i]大則 a[i] → a[j]；否則 i增 1 快速排序中的一趟劃分 i 38 65 97 13 27 49 55 1 2 3 4 5 6 7 8 04 9 49 pivot j a[j]與 pivot比較， a[j]小則 a[j] → a[i]；否則 j減 1 1 2 3 4 5 6 7 8 9 i 38 65 97 13 27 49 55 04 49 pivot j 快速排序中的一趟劃分 i 38 65 97 13 27 49 55 1 2 3 4 5 6 7 8 04 9 49 pivot j a[i]與 pivot比較， a[i]大則 a[i] → a[j]；否則 i加 1 1 2 3 4 5 6 7 8 9 i 38 65 97 13 49 55 04 49 pivot j 27 快速排序中的一趟劃分 i 38 65 97 13 27 49 55 1 2 3 4 5 6 7 8 04 9 49 pivot j a[j]與 pivot比較， a[j]小則 a[i] → a[j]；否則 j減 1 i 38 65 97 13 27 49 55 1 2 3 4 5 6 7 8 04 9 49 pivot j 快速排序中的一趟劃分 i 38 65 97 13 27 49 55 1 2 3 4 5 6 7 8 04 9 49 pivot j i與 j相等時(shí)，完成一次劃分， 樞軸元素歸位 i 38 65 97 13 27 49 55 1 2 3 4 5 6 7 8 04 49 9 j 快速排序中的一趟劃分 38 27 13 49 97 49 55 1 2 3 4 5 6 7 8 04 65 9 int Partition(SqList amp。 快速排序 ? 快速排序 (Quick Sorting)是迄今為止所有內(nèi)排序算法中速度最快的一種。 （ 1）用冒泡法對(duì)數(shù)組 A排序； （ 2）用簡(jiǎn)單選擇排序方法對(duì)數(shù)組 A排序； （ 3）用直接插入排序法對(duì)數(shù)組 A排序； 將上述排序算法分別用函數(shù)實(shí)現(xiàn)， 輸出每種排序過程中元素的比較次數(shù)、交換（或移動(dòng)）次數(shù) ，以及排序過程所消耗的時(shí)間（以 s或 ms為單位）； 基本要求 2． 將問題 1中所有 1000個(gè)（或更多）整數(shù)讀入數(shù)組 A，用快速排序算法對(duì)數(shù)組 A中的元素排序，輸出排序結(jié)果、 排序過程中元素的比較和交換（移動(dòng)）次數(shù) 、排序算法消耗的時(shí)間 。 簡(jiǎn)單選擇排序 ? 簡(jiǎn)單選擇排序的基本思想是：第一趟在 n個(gè)記錄中選取最小記錄作為有序序列的第一個(gè)記錄，第二趟在 n1個(gè)記錄中選取最小記錄作為有序序列的第二個(gè)記錄，第 i趟在 ni+1個(gè)記錄中選取最小的記錄作為有序序列多中的第 i個(gè)記錄。 有序序列 R[1..i1] R[i] 無序序列 R[i..n] 有序序列 R[1..i] 無序序列 R[i+1..n] 冒泡排序 ? 冒泡排序 (Bubble Sorting)的基本思想是：將相鄰位置的關(guān)鍵字進(jìn)行比較，若為逆序則交換之。單元實(shí)驗(yàn)二 排序算法 排序的分類 內(nèi)部排序 外部排序 插入排序（ 直插排序、二分插入排序 、 希爾排序 ） 交換排序（冒泡排序、快速排序） 選擇排序（ 簡(jiǎn)單選擇排序、樹型排序、堆排序 ） 歸并排序（二路歸并排序、多路歸并排序） 分配排序（多關(guān)鍵字排序、基數(shù)排序） 多路平衡歸并排序 置換－選擇排序 最佳歸并樹 排序 直接插入排序 ? 直接插入排序 (Straight Insertion Sorting)的基本思想是： n個(gè)待排序的元素由一個(gè)有序表和一個(gè)無序表組成，開始時(shí)有序表中只包含一個(gè)元素。排序過程中，每次從無序表中取出第一個(gè)元素，將其插入到有序表中的適當(dāng)位置，使有序表的長(zhǎng)度不斷加長(zhǎng)，完成排序過程。 無序序列 R[1..ni+1] 有序序列 R[ni+2..n] ni+1 無序序列 R[1..ni] 有序序列 R[ni+1..n] 比較相鄰記錄，將關(guān)鍵字最大的記錄 交換到 ni+1 的位置上 第 i 趟起泡排序 ? 若在一趟排序過程中沒有進(jìn)行過交換記錄的操作，則整個(gè)排序過程終止。 有序序列 R[1..i1] 無序序列 R[i..n] 第 i 趟 簡(jiǎn)單選擇排序 從中選出關(guān)鍵字最小的記錄 有序序列 R[1..i] 無序序列 R[i+1..n] 基本要求 1．用隨機(jī)函數(shù)產(chǎn)生 1000個(gè)（或更多）整數(shù)（或浮點(diǎn)數(shù)），保存在文件（ / ）中，然后將文件中的所有整數(shù)（或浮點(diǎn)數(shù)）讀入一個(gè)數(shù)組 A。 3. 利用上面實(shí)現(xiàn)的任意一種排序算法，對(duì)實(shí)驗(yàn)題目一所產(chǎn)生的學(xué)生信息文件 ，讀取其中的所有學(xué)生信息： （ 1）按學(xué)號(hào)排序輸出學(xué)生信息； （ 2）按姓名排序輸出學(xué)生信息； （ 3）按三門課程的平均分從高到低排序輸出學(xué)生信息（除了學(xué)生基本信息外，還要輸出每個(gè)學(xué)生的平均成績(jī)），最后再加一行輸出信息：每門課程的平均成
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1