对一组数据（6,9,5,4,8,3）排序，经过一趟排序后，变

[单选题]

对一组数据（6,9,5,4,8,3）排序，经过一趟排序后，变为（6,9,4,5,3,8），则采用的排序算法是（）

```
选择
```
```
归并
```
```
起泡
```
```
插入
```

张小头

//
// Created By John on 2021/02/24.
// 归并排序
// 主要有两个函数，一个合并函数，这个是核心函数，将两个子部分按顺序合并在一起，应该从分散往完整看；另一个是递归函数，主要用来分化数组，应该从完整往分散看
// 辅助数组B要全局，如果放到合并函数里面的话，每一次被调用就会被new一个新的，很浪费空间
#include<stdlib.h>
#define SIZE 10
static int *B = (int*) malloc(SIZE * sizeof (int));

/**
 * 合并函数
 * @param A 待排序的数组
 * @param low
 * @param mid
 * @param high n-1
 */
static void merge(int A[], int low, int mid, int high){
    int i,j,k;
    for (k = low; k <= high; ++k) B[k] = A[k]; //将A数组数据搬到辅助数组B中
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        //两路中小的要先放入到数组A中
        if (B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    //再将长的数组剩下的部分放回A数组中
    while (i <= mid) A[k++] = B[i++];
    while (j <= high) A[k++] = B[j++];
}

static void mergeSort(int A[],int low,int high){
    if (low < high){
        int mid = (low + high)/2;
        mergeSort(A,low,mid);
        mergeSort(A,mid + 1,high);
        merge(A,low,mid,high);
    }
}

发表于 2021-02-25 00:06:06 回复(0)