第章 内排序.doc

第10章 内排序 程序10.1 简单选择排序 template class T void SelectSort(T A[], int n) { int small; for (int i=0; in-1; i++) { //执行n-1趟 small=i; //先定待排序序列中第个元素为最小 for (int j=i+1;jn;j++) //每趟扫描待排序序列n-i-1 if (A[j]A[small]) small=j; //如果扫描到个比最小值元素还小的，则记下其下标 Swap(A[i],A[small]); //最小元素与待排序序列中第个元素交换 } }template class T void InsertSort(T A[], int n) { for(int i=1; in; i++){ //执行n-1趟 int j=i; T temp=A[i]; //待插入元素存入临时变量 while (j0 tempA[j-1])//从后往前查找插入位置 A[j]=A[j-1]; j--; //A[j-1]元素后移，j指针前移 } A[j]=temp; //待插入元素存入找到的插入位置 } } template class T void BubbleSort(T A[], int n) { int i,j,last; i=n-1; while (i0){ //最多进行n-1趟 last=0; //进入循环就将last置成0 for (j=0; ji; j++) //从上往下进行相邻元素的两两比较 if (A[j+1]A[j]) Swap(A[j],A[j+1]); //由于后者小，故交换 last=j; //有交换就将last置成j } i=last; //如果趟排序中没有交换元素，则last为0 } }template class T void QuickSort(T A[], int n) { QSort(A,0,n-1); //以初始序列为序列开始快速排序 } template class T void QSort(T A[], int left, int right){ int i,j; if (leftright){ //若待排序序列多于个元素，则继续快速排序 i=left; j=right+1; //确定待排序序列的游动指针i,j do{ //开始一趟快速排序A[left]作为分割元素 do i++;while (A[i]A[left]); //i指针从左往右找第个(分割元素的元素 do j--; while (A[j]A[left]);//j指针从右往左找第个(分割元素的元素 f (ij) Swap(A[i],A[j]); //若ij，则交换元素 }while (ij); //若ij，则继续本趟排序 Swap(A[left],A[j]); //交换分割元素A[left]和A[j]的位置 QSort(A,left,j-1); //对低端序列快速排序 QSort(A,j+1,right); //对高端序列快速排序 } }template class T void Merge(T A[],int i1,int j1,int i2,int j2) { // i1,j1是子序列1的下、上界，i1,j2是子序列2的下、上界 T *Temp=new T[j2-i1+1]; //分配能存放个子序列的临时数组 int i=i1,j=i2,k=0; //i,j是个子序列的游动指针，k是Temp