在初始数据表已经有序时，在排序过程中仍要改变数据表内容的排序算法是？

Question

在初始数据表已经有序时，在排序过程中仍要改变数据表内容的排序算法是
A 冒泡排序 B.堆排序 C.直接插入排序 D.快速排序

Answer 1

选择B

验证如下：

#include <stdio.h>
#include <stdlib.h>

void swap(int* a, int* b) {
    int temp = *b;
    *b = *a;
    *a = temp;
    printf("swap!!\n");
}

void max_heapify(int arr[], int start, int end) {
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { //若子节点指标在范围内才做比较
        if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
            return;
        else { //否则交换父子内容再继续子节点和孙节点比较
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    int i;
    //初始化，i从最後一个父节点开始调整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() {
    int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

很明显，只要程序存在交换，那么就会输出swap!!
你运行下就知道了。

至于快速排序，是不会改变的，验证代码如下：

#include <stdio.h>
#include <stdlib.h>

void sort(int *a, int left, int right)
{
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];

    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }

        if (i != j) printf("moved!!\n");
        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/

        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
        if (i != j) printf("moved!!\n");
        a[j] = a[i];
    }

    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

int main() {
    int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };
    sort(arr, 0, 17);
    for (int i = 0; i < 18; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

很明显，如果有移动，会输出moved，你运行下，看看，是不会输出的。但是如果你排序的不是有序的数，就会输出。

注：以上两个程序分别来自百度百科的堆排序和快速排序词条下的c语言版本。

如果问题得到解决，请点我回答左上角的采纳，谢谢