好家伙,写作业
这是个非常简单的排序
将一串数分为有序区和无序区
然后将无序区的数一个个按照正确的顺序放到有序区
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
其中我们要解决的一个关键问题就是:
如何将两个有序序列合并成一个有序序列?
现在我们假设两个有序序列R[low]~[mid]、R[mid＋1]~R[high]
void Merge(list R,list R1,int low,int mid,int high) { //合并R[low]~[mid]、R[mid＋1]~R[high]，结果在R1中 int i,j,k; i=low; j=mid+1; k=low; while(i<=mid && j<=high) { if(R[i]<=R[j]){ R1[k]＝R[i]; i++; }//小者先入 else{ R1[k]=R[j]; j++; } } while(i<=mid) R1[k++]＝R[i++];//复制左子表剩余 while(j<=high）) R1[k++]＝R[j++];//复制右子表剩余 }复制
作业题目如下:
对于给定的一组关键字：503,87,512,61,908,170,897,275,653,462，
请首先分别写出运用直接插入排序得到的每趟的结果。然后运用代码实现归并排序。
代码如下:
#include <iostream> using namespace std; //归并排序 void mergeArr(int arr[], int low, int mid, int hight) { int* tempArr = new int[hight - low + 1]; int i = low, j = mid + 1, k = 0; while (i <= mid && j <= hight) { if (arr[i] < arr[j]) { tempArr[k] = arr[i]; i++; } else { tempArr[k] = arr[j]; j++; } k++; } // 如果 arr[low] 到 arr[mid] 区间中的数组还没有比较完成 ，直接复制到tempArr 中 while (i <= mid) { tempArr[k] = arr[i]; i++; k++; } // 如果 arr[mid+1] 到 arr[hight] 区间中的数组还没有比较完成 ，直接复制到tempArr 中 while (j <= hight) { tempArr[k] = arr[j]; j++; k++; } // 比较完成之后 将原本的数组arr 下标 low-hight 对应的内容 进行改变 i = low; for (int tempK = 0;((tempK < k)&&(i<=hight));tempK++) { arr[i] = tempArr[tempK]; i++; } delete[] tempArr; tempArr = NULL; } void sortArr(int arr[], int low, int hight) { if (low < hight) { int mid = (hight + low) / 2; sortArr(arr,low,mid);// 递归拆解左边的序列 sortArr(arr, mid + 1, hight);// 递归拆解左边的序列 mergeArr(arr, low, mid, hight);// 将两个有序的子序列（arr[low至mid]、arr[mid+1至hight] 排序合并成一个新的有序列 } } //直接插入排序 void InsertSort(int a[],int l){ int temp; int j; cout<<"直接插入排序每次排序后数据如下:" <<endl; for(int i=1;i<l;i++) { if(a[i]<a[i-1]) { temp=a[i]; for(j=i-1;j>=0&&temp<a[j];j--) { a[j+1]=a[j]; } a[j+1]=temp; } for(int k=0;k<l;k++) { cout<<a[k]<<" "; } cout<<endl; } } int main() { int a[10]={503,87,512,61,908,170,897,275,653,462}; int len=9; InsertSort(a,len); sortArr(a,0,9); cout << endl << "归并排序后" << endl; for (int j = 0;j <9;j++) { cout << a[j] << " "; } return 0; }复制