插入排序算法的C++通用版本，支持任何以迭代器（或普通数组首、尾指针）传入的数组的就地排序。
myutil.h
代码:
#pragma once
#ifndef _MY_UTIL_H
#define _MY_UTIL_H
#include<iterator> //iterator_traits
//template function to display arrays with new line printed when finish.
template<class Iterator>
void displayArr(const Iterator &beg, const Iterator &end){
typedef typename std::iterator_traits<Iterator>::value_type Ty;
std::copy(beg, end, std::ostream_iterator<Ty>(std::cout, " "));
std::cout<<std::endl;
}
#endif
insertion_sort.h
代码:
#pragma once
#ifndef _INSERT_SORT_H
#define _INSERT_SORT_H
#include<iterator> //iterator_traits
template<class Iterator, class cmp>
void insertSort(const Iterator &beg, const Iterator &end){
typedef typename std::iterator_traits<Iterator>::value_type val_t;
Iterator step = beg;
Iterator insertPos;
Iterator beforeInsertPos;
for(++step; step != end; ++step){
val_t key = *step;
insertPos = step;
beforeInsertPos = insertPos;
for(--beforeInsertPos; cmp()(*beforeInsertPos, key); --beforeInsertPos){
*insertPos-- = *beforeInsertPos;
if(beforeInsertPos == beg)
break;
}//end of for
*insertPos = key;
}// end of for
}// end of insertion sort
#endif
main.cpp
代码:
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include"myutil.h" //displayArr
#include"insertion_sort.h" //insertSort
using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::list;
int main(int argc, char **argv)
{
int intArr[ ] = { 231, -547, -54, 54, 0, -1, 45, -54, 123, 9, -54 };
int *intArrEnd = intArr + sizeof(intArr) / sizeof(*intArr);
double doubleArr[ ] = { 0.0, -28.7, 465.2 };
double *doubleArrEnd = doubleArr + sizeof(doubleArr) / sizeof(*doubleArr);
string strArr[] = {"月夜幻影", "bill", "billhoo", "Alex", "alex", "Petter"};
string *strArrEnd = strArr + sizeof(strArr) / sizeof(*strArr);
vector<string> strVec(strArr, strArrEnd);
list<string> strList(strArr, strArrEnd);
cout<<"before insertion sort..."<<endl;
displayArr<int*>(intArr, intArrEnd);
displayArr<double*>(doubleArr, doubleArrEnd);
displayArr<string*>(strArr, strArrEnd);
displayArr(strVec.begin(), strVec.end());
displayArr(strList.begin(), strList.end());
//do insertion sort in ascending order
insertSort<int*, std::greater<int>>(intArr, intArrEnd);
insertSort<double*, std::greater<double>>(doubleArr, doubleArrEnd);
insertSort<string*, std::greater<string>>(strArr, strArrEnd);
insertSort<vector<string>::iterator, std::greater<string>>(strVec.begin(), strVec.end());
insertSort<list<string>::iterator, std::greater<string>>(strList.begin(), strList.end());
cout<<"\nascending order:"<<endl;
displayArr<int*>(intArr, intArrEnd);
displayArr<double*>(doubleArr, doubleArrEnd);
displayArr<string*>(strArr, strArrEnd);
displayArr(strVec.begin(), strVec.end());
displayArr(strList.begin(), strList.end());
//do insertion sort in descending order
insertSort<int*, std::less<int>>(intArr, intArrEnd);
insertSort<double*, std::less<double>>(doubleArr, doubleArrEnd);
insertSort<string*, std::less<string>>(strArr, strArrEnd);
insertSort<vector<string>::iterator, std::less<string>>(strVec.begin(), strVec.end());
insertSort<list<string>::iterator, std::less<string>>(strList.begin(), strList.end());
cout<<"\ndescending order:"<<endl;
displayArr<int*>(intArr, intArrEnd);
displayArr<double*>(doubleArr, doubleArrEnd);
displayArr<string*>(strArr, strArrEnd);
displayArr(strVec.begin(), strVec.end());
displayArr(strList.begin(), strList.end());
return EXIT_SUCCESS;
}
本文转自Bill_Hoo 51CTO博客，原文链接：http://blog.51cto.com/billhoo/793581，如需转载请自行联系原作者
