一、為什么學了之后過段時間又會忘記了？
因為沒有去運用它和認為面試需要而沒有真正的重視。現在給它賦予意義：1.那就是基礎牢固，才可觸類旁通2.真正記得和隨時可以拿出手，那么面試可以PK掉一大批人。不然看到一個精妙的算法就學一個，永遠只是學到某一個而沒有自己的思維在里面。
二、選擇排序算法代碼
#include <iostream> using namespace std;void selectionSort(int arr[],int n){for (int i = 0; i < n; i++){int minIndex = i;
//尋找i~n中的最小值，然后進行位置的轉換for (int j = i + 1; j < n; j++){if ( arr[j] < arr[minIndex] ){minIndex = j;}swap(arr[i], arr[j]);}} }int main(int argc, const char * argv[]) {int a[10] = {10,9,8,7,6,5,4,3,2,1};selectionSort(a,10);for( int i = 0 ; i < 10 ; i ++ )cout<<a[i]<<" ";cout<<endl;return 0; }
?核心思想：每次都是去找到最小的值。
三、插入排序算法代碼
//插入排序 template<typename T> void insertionSort(T arr[],int n){//因為第0個元素不需要比較，直接從下標為1的元素開始比較for (int i = 1; i < n; i++) {for (int j = i; j > 0; j--) {if (arr[j] < arr[j-1]) {swap(arr[j], arr[j-1]);}else break;}} }
思路：插入排序，從下標為1的元素開始和它前面的元素進行相比，小就換位置，大就退出循環。從下標為2的元素開始...
比如 ? ? ? 8、6、2、3、1、5、7、4
先變成 ? ?6、8、2、3、1、5、7、4然后用2和它之前的數進行比較。。。
四、插入排序算法改進
一次交換就是3次賦值。改進就是改進交換，每次比較后只交換一次。
//改進版插入排序template<typename T>
void insertionExcellentSort(T arr[],int n){for (int i = 1; i < n; i++) {T e = arr[i];int j;for ( j = i; j > 0 && arr[j-1] > e; j--) {arr[j] = arr[j-1];}arr[j] = e;}
}
