啪啪拉拉噼里啪啦

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

直接選擇排序(Straight Selection Sort)

1、直接選擇排序的基本思想
   　 n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：
 ①初始狀態：無序區為R[1..n]，有序區為空。
 ②第1趟排序
    　在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
　　……
 ③第i趟排序
　　第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R[i..n](1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[i]交換，使R[1..i]和R[i+1..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
    　這樣，n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。

2、直接選擇排序的過程
　　對初始關鍵字為49、38、65、97、76、13、27和49的文件進行直接選擇排序的過程【參見動畫演示】

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++) //在當前無序區R[i..n]中選key最小的記錄R[k]
       if(R[j].key<R[k].key)
         k=j; //k記下目前找到的最小關鍵字所在的位置
       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）關鍵字比較次數
    　無論文件初始狀態如何，在第i趟排序中選出最小關鍵字的記錄，需做n-i次比較，因此，總的比較次數為：
     n(n-1)/2=0(n²)

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

（3）直接選擇排序是一個就地排序

（4）穩定性分析
    　直接選擇排序是不穩定的

2.冒泡排序
3.字符轉換