數(shù)組應(yīng)用的技巧與方法-文庫吧資料
2024-11-01 15:46本頁面
【正文】 結(jié)束條件： （ 1）查找成功 ： elem[mid] = key （ 2）查找不成功 ： high≤low （意即區(qū)間長度小于 0） 折半查找 19 折半查找法程序 int BinSearch(int R[], int n, int Key) //功能：在有序表 R[0..n1]中進行折半查找 //返回值：查找成功時返回數(shù)組下標，否則返回 1 { int low=0,high=n1,mid。重算 mid＝ ?(low+high)/2?； . (3) 若 elem[mid] key，說明 key?[low ,mid1]， 則令： high =mid–1。 Low指向待查元素所在區(qū)間的下界 high指向待查元素所在區(qū)間的上界 mid指向待查元素所在區(qū)間的中間位置 已知如下 11個元素的 有序表 ： （ 05 13 19 21 37 56 64 75 80 88 92） , 請查找關(guān)鍵字為 21 和 85的數(shù)據(jù)元素。 a[minj] = t。 if (minj != i) { t = a[i]。j N。i++) { minj = i。 for (i = 0。 算法停止。 第 1步 :找到 a[1]~a[N1]中的最小值元素與 a[1]交換； 第 2步 :找到 a[2]~a[N1]中的最小值元素與 a[2]交換； … 第 i步 :找到 a[i]~a[N1]中的最小值元素與 a[i]交換 。而這時候第 n個數(shù)據(jù)是第 n小。 ? 第 i次，在數(shù)組 a后的 ni+1個數(shù)據(jù)中，經(jīng)過類似選擇處理后，數(shù)組 a的第 i個數(shù)據(jù)為第 i小。 ? 第 1次，在數(shù)組 a的 n個數(shù)據(jù)中選出其小者（只標記其所在位置），若它不在其位置（即其下標不等于 1）則與第一個數(shù)據(jù)進行交換（只需交換一次），經(jīng)過本次處理后，總可以使得數(shù)組 a的第 1個數(shù)據(jù)為第 1小。 a[j] = t。j++) if (a[j] a[i]) { t = a[i]。i++) { for (j = i + 1。 for (i = 0。 前提： 順序存儲結(jié)構(gòu) 例： 關(guān)鍵字序列 T=(21， 25， 49， 25*， 16， 08），請寫出冒泡排序的具體實現(xiàn)過程。 交換排序的主要算法有： 1) 冒泡排序 2) 快速排序 交換排序的基本思想是： 11 冒泡排序 基本思路： 每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。j n。i L。 【 13】 , 6, 3, 31, 9, 27, 5, 11 【 6, 13】 , 3, 31, 9, 27, 5, 11 【 3, 6, 13】 , 31, 9, 27, 5, 11 【 3, 6, 13， 31】 , 9, 27, 5, 11 【 3, 6, 9, 13， 31】 , 27, 5, 11 【 3, 6, 9, 13， 27, 31】 , 5, 11 【 3, 5, 6, 9, 13， 27, 31】 , 11 【 3, 5, 6, 9, 11， 13， 27, 31】 在已形成的 有序表中 線性查找 ，并在適當位置插入，把原來位置上的元素向后 順移 。 簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。 2. 排序的目的是什么？ 存放在數(shù)據(jù)表中 按關(guān)鍵字排序 ？ ? 時間效率 ——排序速度 （ 即排序所花費的全部比較次數(shù) ） ? 空間效率 ——占內(nèi)存輔助空間的大小 ? 穩(wěn)定性 ——若兩個記錄 A和 B的關(guān)鍵字值相等 ， 但排序后 A、B的先后次序保持不變 ， 則稱這種排序算法是穩(wěn)定的 。 s=s*a。 } ? 累乘器 int s=1。 for (…) { … a=…。1 數(shù)組應(yīng)用的技巧與方法 桂林電子科技大學(xué) 周信東 2 常用算法：計數(shù)器、累加器、累乘器 ? 計數(shù)器 int count=0。 while (…) { … count ++ } ? 累加器 int s=0。 s=s+a。 for (…) { … a=…。 } 3 關(guān)于一維數(shù)組的問題 ? 一般一維數(shù)組所涉及的主要問題有 ? 排序 ? 插入 ? 刪除 ? 查找 ? 分類統(tǒng)計 ? 涉及到一些算法，我們通過例題介紹一部分 ? 具體問題的解題算法的思路要靠自己慢慢去體會 4 1. 什么是排序？ 將一組雜亂無章的 數(shù)據(jù) 按一定的 規(guī)律 順次排列起來。 ——便于查找 5 常見排序算法 ? 插入排序 ? 直接插入排序 ? 折半插入排序 ? 表插入排序 ? 希爾排序 ? 交換排序 ? 冒泡排序 ? 快速排序（不穩(wěn)定） ? 選擇排序 ? 歸并排序 ? 基數(shù)排序 6 插入排序 插入排序的基本思想是： 每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當位置上，直到對象全部插入為止。 7 直接插入排序 新元素插入到哪里？ 例 1： 關(guān)鍵字序列 T=（ 13， 6， 3， 31， 9， 27， 5， 11）， 請寫出直接插入排序的中間過程序列。 最簡單的排序法！ 8 有序插入 ? 首先查找要插入的位置，假設(shè)位置為 a[L]之前 ? 則： for (i =n+1。i) a[i]=a[i1] 9 有序刪除 ? 比如要刪除 a[d]這個元素， 則 for (j = d。j++) a[j]=a[j+1] 10 交換排序 兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。 優(yōu)點： 每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1