本文共 1721 字，大约阅读时间需要 5 分钟。
#include#include #include using namespace std;/*问题:插入排序。分析 ：插入排序的本质是：对于当前元素，从当前元素前面已经排好序的序列寻找出一个元素大于当前元素。然后将这两个元素交换最容易混淆的两个排序：选择排序，前面序列A[1..i-1]有序，当前第i个元素是后面序列A[i....n]中挑选的最小的元素组成，然后与A[i]元素交换。输入:81 4 9 6 5 4 3 8输出:1 3 4 4 5 6 8 9*/void bubbleSort(){}//插入排序：前面A[1..i-1]有序，寻找A[j] <= A[i]的元素位置j,然后A[j...i]往后移动一位，令A[j]=A[i]。void insertSort(vector & datas){ if(datas.empty()) { return; } int size = datas.size(); int temp; int j; for(int i = 0 ; i < size ; i++) { temp = datas.at(i); for(j = i ; j >= 1 ; j--) { //元素往后移动,如果前面一个元素 > 当前元素，就继续寻找 if( datas.at(j-1) > temp ) { datas.at(j) = datas.at(j-1); } //如果前面序列中最大元素都<=当前元素，符合要求，直接退出 else { break; } } datas.at(j) = temp; }}//选择排序本质：序列A[1..i-1]已经有序，从A[i..n]中选择出最小的元素作为A[i]void selectSort(vector & datas){ if(datas.empty()) { return; } int size = datas.size(); for(int i = 0 ; i < size - 1; i++) { int minIndex = i; for(int j = i + 1 ; j < size ;j++) { if(datas.at(j) < datas.at(minIndex)) { minIndex = j; } } int temp = datas.at(minIndex); datas.at(minIndex) = datas.at(i); datas.at(i) = temp; }}void mergeSort(){}void quickSort(){}void heapSort(){}void radixSort(){}void print(vector & datas){ if(datas.empty()) { cout << "no result" << endl; return; } int size = datas.size(); for(int i = 0 ; i < size ; i++) { cout << datas.at(i) << " "; } cout << endl;}void process(){ int num; int value; vector datas; while(cin >> num) { datas.clear(); for(int i = 0 ; i < num ; i++) { cin >> value; datas.push_back(value); } insertSort(datas); //selectSort(datas); print(datas); }}int main(int argc , char* argv[]){ process(); getchar(); return 0;}
转载地址：http://dhofn.baihongyu.com/