接著上一篇文章常用的排序侠坎，繼續(xù)說排序蚁趁，剩下的還有直接插入排序，直接選擇排序和堆排序实胸，默認排序順序仍是遞增排序他嫡。廢話不多說了，開始進入正題庐完。
插入排序其實分為：直接插入排序钢属，二分插入排序（或折半插入排序），希爾排序门躯，其基本思想就是：每次將一個待排序的記錄淆党，按其關(guān)鍵字的大小插入到前面已經(jīng)排好序的子表中的適當位置，直到全部記錄插入完成為止。在這里只介紹直接插入排序染乌。
直接插入排序
直接先來代碼好了山孔。
void InsertSort(RecType R[],int n)
{
int i,j;
RecType tmp;
for (int i = 1; i < n; i++)
{
tmp = R[i];
j = i - 1;
while(j >= 0 && tmp.key < R[j].key)
{
R[j+1] = R[j];
j--;
}
R[j+1] = tmp;
}
}
此排序的操作過程為：假設(shè)有一序列為（6，3荷憋，7台颠，5，1勒庄，4串前，2，9）锅铅，剛開始時i = 1酪呻，j = 0，有序區(qū)暫時只有R[0]一個記錄盐须。從6起，從右向左查找漆腌，3小于6贼邓，將6右移一個位置，j-- 后while條件不滿足了闷尿，結(jié)束while循環(huán)塑径，將3插入R[0]的位置，此時序列變?yōu)椋?填具，6统舀，7，5劳景，1誉简，4，2盟广，9）闷串，第一趟排序結(jié)束。接下來第二趟排序烹吵，i = 2，待插入的記錄為R[2] = 7桨武，從6開始從右向左查找肋拔。7大于6，while條件不滿足呀酸，所以7的位置不變凉蜂。此時序列變?yōu)椋?，6，7跃惫，5叮叹，1，4爆存，2蛉顽，9），第三趟排序...以此類推先较，直到所有記錄都有序為止携冤。
初始序列：6 3 7 5 1 4 2
i = 1： <b><u>3</u></b> 6 7 5 1 4 2 9
i = 2： 3 6 <b> <u>7</u></b> 5 1 4 2 9
i = 3： 3 <b><u>5</u></b> 6 7 1 4 2 9
i = 4： <b><u>1</u></b> 3 5 6 7 4 2 9
i = 5： 1 3 <b> <u>4</u></b> 5 6 7 2 9
i = 6： 1 <b><u>2</u></b> 3 4 5 6 7 9
i = 7： 1 2 3 4 5 6 7 <b> <u>9</u></b>
選擇排序的基本思想是：每一趟排序是從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的記錄序列的末尾闲勺，直到全部記錄排序完畢曾棕。常用的選擇排序方法有直接選擇排序（或簡單選擇排序）以及 堆排序。
直接選擇排序
void selectSort(RecType R[],int n)
{
int i,j,k;
RecType tmp;
for (int i = 0; i < n - 1; i++)
{
k = i;
for (int j = i + 1; j < n; j++)
if (R[j].key < R[k].key)
k = j;
if (k != i)
{
tmp = R[i];
R[i] = R[k];
R[k] = tmp;
}
}
}
此排序的操作過程為：還是以序列為（6菜循，3翘地，7，5癌幕，1衙耕，4，2勺远，9）的例子來說吧橙喘。剛開始時 i = 0，假設(shè)i = 0這個位置對應(yīng)的關(guān)鍵字是最小的胶逢，從i+1開始厅瞎，在6后面的序列中找到最小的那個記錄，用 k 記下第一趟排序后目前找到的最小的關(guān)鍵字所在的位置初坠，判斷 k 是否等于 i和簸，不相等，說明最小值的位置發(fā)生了變化某筐，需要交換下R[i] 和 R[k]比搭，此時序列為（1，3南誊，7身诺，5，6抄囚，4霉赡，2，9）幔托。接著第二趟排序開始...以此類推穴亏，經(jīng)過n - 1趟排序后蜂挪，整個序列遞增有序。
初始序列：6 3 7 5 1 4 2 嗓化，排序過程如下所示：
堆排序
待續(xù) O(∩_∩)O
