数据结构面试之九——排序1（直接插入、希尔、冒泡、直接选择排序）
题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。
九、数据结构面试之九——排序1（直接插入、希尔、冒泡、直接选择排序）
1.直接插入排序
【算法思想】：每次将一个待排序的元素，插入到前面已经排序的子序列中，直到全部元素插入完毕为止。
【算法实现】：
//最简实现排序[交换实现].
template <class T>void SelectSort(T arr[], int N){ intminPos; for(int i = 0; i < N; i++) { minPos= i; for(intj=i+1; j<N; j++) { if(arr[j]< arr[minPos]) { minPos= j; }//endif }//endfor if(minPos!= i) { swap(arr[minPos],arr[i]);//交换 } }}