前几天，面试时有被问到一些常见的排序算法，快速排序命中率很高，现整理一些常见的排序算法模板：
#include<iostream>
using namespace std;
template <class T>
void Swap(T *a, T *b)
{
T temp;
temp = *a;
*a = *b;
*b = temp;
}
/**************************************** 简单排序算法 begin ****************************************/
/*
* 简单选择排序
* A: 以数组存放的无数数
* n: 数组A中从位置0到n排序(从小到大)
*/
template <class T>
void SelectSort(T A[], int n)
{
int small;
for( int i = 0; i < n - 1; i++) { // 执行 n-1 趟
small = i; // 先假定待排序序列中第一个元素最小
for( int j = i + 1; j < n; j++ ) { // 每趟扫描待排序序列n-i-1次
if( A[j] < A[small] ) { // 如果扫描到一个比最小值元素还小的，则记下其下标
small = j;
}
}
Swap(&A[i],&A[small]); // 最小元素与待排序序列中第一个元素交换
}
}
/*
* 直接插入排序
* A: 以数组存放的无数数
* n: 数组A中从位置0到n排序(从小到大)
*/
template <class T>
void InsertSort(T A[], int n)
{
for(int i = 1; i < n; i++) { // 执行 n-1 趟
int j = i;
T temp = A[i]; // 待插入元素存入临时变量
while(j > 0 && temp < A[j-1]) { // 从后往前查找插入位置
A[j] = A[j-1]; // A[j-1]元素后移
j--; // j指针前移
}
A[j] = temp; // 待插入元素存入找到的插入位置
}
}
/*
* 冒泡排序
* A: 以数组存放的无数数
* n: 数组A中从位置0到n排序(从小到大)
*/
template <class T>
void BubbleSort(T A[], int n)
{
int i,j,last;
i = n - 1;
while ( i > 0 ) { // 最多进行n-1躺
last = 0; // 将last赋值为0
for( j = 0; j < i; j++) { // 从前往后进行相邻元素的两两比较
if(A[j+1] < A[j]) {
Swap(&A[j],&A[j+1]); // 后者小，则交换
last = j; // 有交换，last置为j
}
}
i = last; //如果一趟没有元素交换，则last为0
}
}
/**************************************** 简单排序算法 end ****************************************/
/**************************************** 快速排序 begin ****************************************/
/*
* 快速排序
* A: 以数组存放的无数数
* left和right: A[left] 和 A[right] 之间的元素排序
*/
template <class T>
void QuickSort(T A[], int left, int right)
{
int i,j;
if(left < right) { // 若待排序序列多于一个元素，则继续快速排序
i = left; // 游动指针i,j
j = right + 1;
Swap(&A[left],&A[(left + right)/2]); // 避免最坏境况发生
do { // 开始一趟快速排序,A[left]做为分割元素
do i++; while(A[i] < A[left]); // i指针从左往右找第一个 大于等于 分割元素的元素
do j--; while(A[j] > A[left]); // j指针从右往左找第一个 小于等于 分割元素的元素
if( i < j ) Swap(&A[i],&A[j]); // 若 i < j,则交换两个元素
} while(i<j); // 若 i < j,则继续本趟排序
Swap(&A[left],&A[j]); // 交换分割元素A[left]和A[j]的位置
QuickSort(A,left,j-1); // 对低端序列快速排序
QuickSort(A,j+1,right); // 对高端序列快速排序
}
}
/**************************************** 快速排序 end ****************************************/
/*对上面的几种排序算法，进行简单的测试*/
int main() {
int a[5] = {2,1,6,8,3};
// SelectSort(a,5);
// InsertSort(a,5);
// BubbleSort(a,5);
QuickSort(a,0,4);
for(int i = 0; i < 5; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}