最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

数据结构作业(三):直接插入排序 和 归并排序

来源：博客园

好家伙,写作业


(资料图片)

1.直接插入排序

这是个非常简单的排序

将一串数分为有序区和无序区

然后将无序区的数一个个按照正确的顺序放到有序区

2.归并排序

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

其中我们要解决的一个关键问题就是:

如何将两个有序序列合并成一个有序序列?

现在我们假设两个有序序列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 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<<"直接插入排序每次排序后数据如下:" <=0&&temp

关键词： 插入排序 归并排序 数据结构