啪啪拉拉噼里啪啦

1.選擇排序
  　選擇排序(Selection Sort)的基本思想是：每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排好序的子文件的最后，直到全部記錄排序完畢。
   　 常用的選擇排序方法有直接選擇排序和堆排序。

直接選擇排序(Straight Selection Sort)

1、直接選擇排序的基本思想
   　 n個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果：
 ①初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空。
 ②第1趟排序
    　在無(wú)序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R[1]交換，使R[1..1]和R[2..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)。
　　……
 ③第i趟排序
　　第i趟排序開(kāi)始時(shí)，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當(dāng)前無(wú)序區(qū)中選出關(guān)鍵字最小的記錄R[k]，將它與無(wú)序區(qū)的第1個(gè)記錄R[i]交換，使R[1..i]和R[i+1..n]分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)。
    　這樣，n個(gè)記錄的文件的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果。

2、直接選擇排序的過(guò)程
　　對(duì)初始關(guān)鍵字為49、38、65、97、76、13、27和49的文件進(jìn)行直接選擇排序的過(guò)程【參見(jiàn)動(dòng)畫(huà)演示】

3、算法描述
　　直接選擇排序的具體算法如下：
　void SelectSort(SeqList R)
　{
   int i，j，k；
   for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)
     k=i；
     for(j=i+1;j<=n;j++) //在當(dāng)前無(wú)序區(qū)R[i..n]中選key最小的記錄R[k]
       if(R[j].key<R[k].key)
         k=j; //k記下目前找到的最小關(guān)鍵字所在的位置
       if(k!=i){ //交換R[i]和R[k]
         R[0]=R[i]；R[i]=R[k]；R[k]=R[0]； //R[0]作暫存單元
        } //endif
     } //endfor
  } //SeleetSort

4、算法分析
（1）關(guān)鍵字比較次數(shù)
    　無(wú)論文件初始狀態(tài)如何，在第i趟排序中選出最小關(guān)鍵字的記錄，需做n-i次比較，因此，總的比較次數(shù)為：
     n(n-1)/2=0(n²)

（2）記錄的移動(dòng)次數(shù)
    　當(dāng)初始文件為正序時(shí)，移動(dòng)次數(shù)為0
    　文件初態(tài)為反序時(shí)，每趟排序均要執(zhí)行交換操作，總的移動(dòng)次數(shù)取最大值3(n-1)。
    　直接選擇排序的平均時(shí)間復(fù)雜度為O(n²)。

（3）直接選擇排序是一個(gè)就地排序

（4）穩(wěn)定性分析
    　直接選擇排序是不穩(wěn)定的

2.冒泡排序
3.字符轉(zhuǎn)換