好家伙,写作业
这是个非常简单的排序
将一串数分为有序区和无序区
然后将无序区的数一个个按照正确的顺序放到有序区
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
其中我们要解决的一个关键问题就是:
如何将两个有序序列合并成一个有序序列?
现在我们假设两个有序序列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;
}