第10章 内排序
程序10.1 简单选择排序
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]); //最小元素与待排序序列中第一个元素交换
}
}
程序10.2 直接插入排序
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]; j--; //A[j-1]元素后移,j指针前移
}
A[j]=temp; //待插入元素存入找到的插入位置
}
}
程序10.3冒泡排序
template <class T>
void BubbleSort(T A[], int n)
{
int i,j,last;
i=n-1;
while (i>0){ //最多进行n-1趟
1