algorithm -- 選擇排序

選擇排序是《導論》第一章課后習題，仿照插入排序，再次運用循環不變式來證明下算法的正確性，C++ 源碼：

// 交換函數 
void swap( int& a, int& b )
{a = a^b;b = a^b;a = a^b;
}
void selectSort( int *arr, int count )
{if( arr == nullptr || count == 0 ){return;}for( int i = 1; i < count; i++ ){int tem = arr[ i - 1 ];for( int j = i; j < count; j++ ){if( tem > arr[j] ){swap( tem, arr[ j ] );}}arr[ i - 1 ] = tem;}
}

傳入待排序數組指針和數組大小，同樣正在排序的元素前面的是已經排序好的部分，未排序的在后面。

• 初始化： i = 1; tem = arr[ 0 ]; tem 等于第一個元素，依次和后面的元素比較，如果 tem 大則交換值，這樣到和后面元素比較完后 tem 就是值最小的一個，賦值給 arr[ 0 ]， arr[ 0 ] 的原值在比較過程中賦值給后面的第一個小于它的元素，數組本身數據沒有增加或減少。

• 保持：第 i 個元素排序時前面元素已經按從小到大的順序排好了，依次各后面的元素比較，如果大于后面的元素則交換值，直到比較完全部剩余的元素，這時 tem 就是剩余元素中值最小的一個賦值給 arr[ i - 1 ]，0~（i-1）的元素已經排好序了，后面的則是無序的

• 終止： 當 i == count 時，循環條件不滿足，跳出循環，此時 數組的前 i-1 個已排好順序，而數組大小為 conut 個，數組最后一個元素的下標是 conut-1 等于此時的 i-1 ，所以此時數組已排好序了，算法正確。

循環不變式 的證明結束了，需要說明的一點是上面的交換函數：

// 交換函數 
void swap( int& a, int& b )
{a = a^b;b = a^b;a = a^b;
}

函數參數使用引用，可以修改參數原來的值，引用在 C++ 中是變量別名，即同一個變量可以有多個名字，區別定義是名字，其他的別名叫引用，引用可以像變量本身一樣對數值操作，作為函數參數時，可以在函數內部修改變量；普通的函數參數，會將傳遞過來變量拷貝一份，在函數內部的修改不到影響外部變量的值。

函數內部使用 ^ 異或來交換值，異或是 位 運算符，位運算比一般的運算要快；異或有個特殊的性質，連續兩次異或變量的值不會變，即第一次異或會變成奇怪的值，再次異或就會變成原值，這個交換函數就是利用這個性質，

• a b 異或賦值 a, a是異或后的結果
  
• a b 再次異或結果為原來的 a, 賦值 b,交換一個
  
• a b(原a值)異或結果為原來的 b 賦值 a,交換完成

實踐兩次 循環不變式 下次嘗試算法分析！

algorithm wiki