選擇分類過程包括兩個動作：1．從分類檔案中選出一個關鍵字值最小的記錄；2．然後，將選出的記錄送入正在增長的結果檔案中。
基本介紹
- 中文名：選擇分類
- 外文名：selection sort
- 定義：選出關鍵字
- 作用：從小到大順序排列
- 系統：計算機
- 套用學科：計算機原理
選擇分類的思想,算法描述,分類,計數選擇法,直接選擇法,堆分類,
選擇分類的思想
選擇分類的思想是：首先在n個記錄中選擇一個具有最小關鍵字的記錄，並將它從n個記錄中刪除，作為新的一組記錄的第一個，再在n一1個記錄中，選擇一個具有最小關鍵字的的記錄，將它從n一1個記錄中刪除，作為新的一組記錄的第二個。如此繼續，便得到一組按從小到大順序排列的記錄。
設待分類的n個數據存放在數組a中。簡單選擇分類也是對數組a進行多遍掃描，第1遍掃描完成時，n個數據中關鍵字最小的數據將存入數組元素a[1]中；第2遍掃描，從a[2]到a[n]中選擇關鍵字最小的數據，且將它存入a[2]中；第i遍掃描，將從a[i]到a[n]中選擇關鍵字最小的數據，存入a[i]中；當第n一1遍掃描完成之後，僅剩下唯一的一個元素a[n]，它顯然是關鍵字最大的數據。
算法描述
#include”sort．h” void smpsele(int a[]，int n)； void main(){ int arr[MAX]，n； n=getdata(arr)；/*讀n個數據存入數組arr中*/ output(arr，1，n)；/*顯示數組arr中的n個數據*/ printf(”\n”)； smpsele(arr，n)；/*對數組arr中數據進行分類*/ output(arr，1，n)；/*顯示分類後的有序的數據序列*/ printf(”\n”)； } void smpsele(int a[]，int n){ int i，j，m，small，t； for(i=1；i<=n一1；i++){ m=i： small=a[i]； for(j=i+1；j<=n；j++) if(a[j]<small){ small=a[j]； m=j； } t=a[i]； a[i]=a[m]； a[m]=t； }}
分類
計數選擇法
確切地說，它不是一種分類方法，而是能用於各種分類方法的一種技術，執行的結果並不能將初始檔案轉化成有序檔案，而是計算出每個記錄的相對位置。以後再按它將記錄置入結果檔案，而得到一個排序檔案。
該方法是為每個記錄設一個計數器，構成一個記錄相對位置域。每遍掃描時，總是用一關鍵字與其後面的所有記錄關鍵字依次逐個地比較。每當發現一個關鍵字值大於另一個時，大值的計數加1，計數器中記載了小於其關鍵字的記錄數目。
掃描過程，一般第一次以第一個記錄作為固定記錄，第i次以第i個記錄作為固定記錄。第i遍結束時，計數器i中就記載了比第i個記錄小的記錄的個數。這一過程進行n-1遍，所有記錄相對位置標誌都將在計數器中給予記載。
關鍵字比較中，當兩記錄關鍵字相等時，固定記錄的計數標誌不變，而被比較的記錄計數標誌加1。按這種原則，相等時，排在前面的記錄始終排在前面，從而分類結果是穩定的。
對於整個檔案中最小記錄顯然是無一記錄比它小。假設它的計數標誌為1，即初始狀態時，所有計數標誌的值為1。
直接選擇法
直接選擇法是一種典型且簡單的分類方法。其分類思想是：首先在檔案中選出關鍵值最大的記錄，把它與最後一個記錄交換，然後在其餘的記錄中再選出關鍵字值次最大的記錄與例數第二個記錄交換，重複執行到第二個記錄，完成整個檔案的分類。
算法中，設一個指針，指向當前一遍掃描中最大關鍵字值的記錄，並不需要在掃描過程中將當前最大的記錄取出。直到一遍掃描結束時，再將指針所指記錄送到最終位置上去。
堆分類
堆分類算法是一種非線性算法。算法給分類檔案一個結構——二叉樹，‘其目的是為了提高分類效率，並且相當有效。
堆分類算法首先要使用一棵稱為堆的二叉樹，這棵樹有如下特點：
1、這棵二叉樹上任何一個頂點為根的子樹中，根結點的關鍵字值大於其所有子孫的關鍵字值；
2、這顆二叉樹識一顆順序完全二叉樹。
堆分類算法處理的待分類檔案是按線性結構順序存放的，而分類的過程是將整個檔案視為一樹形結構的檔案，即分類中是以先處理父結點再處理孩子結點的方式進行的。因此，也可以說，分類算法是非線性的，視分類檔案為一棵二叉樹來實現分類的。
