R8-2 sort代码阅读题 分数 10 作者 康长青 单位 湖北文理学院 void Sort1(int r[ ], int n) { int i, j, index; for (i = 1; i < n; i++) { index = i; for (j = i + 1; j <= n; j++) if (r[j] < r[index]) index = j; if (index != i) { r[0] = r[i]; r[i] = r[index]; r[index] = r[0]; }}} 1、判断Sort1属于什么排序？文字叙述上面代码的基本思想(4分） 2、代码的时间复杂度式多少？（2分） 3、这个算法是否稳定？不稳定给出反例(4分）

1、Sort1属于选择排序。

上面代码的基本思想是：每次从待排序的元素中选出最小的一个，与当前的第i个元素交换位置，直到排序完成。

2、代码的时间复杂度为O(n^2)。

Sort1算法中包含两层循环，外层循环需要执行n-1次，内层循环需要执行(n-i)次，因此总的时间复杂度为O(n^2)。

3、Sort1算法是不稳定的。

反例：假设待排序的序列为{3, 2, 3, 1}，则第一次选择2作为最小值，与第一个3交换位置，得到序列{2, 3, 3, 1}；第二次选择1作为最小值，与第一个3交换位置，得到序列{2, 1, 3, 3}。可以看出，原来在前面的3和后面的3位置发生了变化，因此Sort1算法是不稳定的。

相关问题

对下面的C语言伪代码函数进行分析 推测关于该函数的使用环境和预期目的详细的函数功能等信息 并为这个函数取一个新的名字 ) _BYTE *__fastcall sub_74918(int a1, int a2, int a3, int a4) { int v6; // r2 void *v7; // r0 void *v8; // r1 void *v9; // r3 int v10; // r10 char *v11; // r0 int v12; // r8 unsigned int v13; // r5 int i; // r1 unsigned int j; // r2 _BYTE *result; // r0 int v17; // r4 int v18; // r9 int k; // r6 char *v20; // r1 unsigned __int8 v22; // [sp+9h] [bp-27h] unsigned __int8 v23; // [sp+Ah] [bp-26h] unsigned __int8 v24; // [sp+Bh] [bp-25h] char v25; // [sp+Ch] [bp-24h] char v26; // [sp+Dh] [bp-23h] char v27; // [sp+Eh] [bp-22h] char v28; // [sp+Fh] [bp-21h] if ( a3 ) { v6 = 56; v7 = off_D7060; v8 = off_D7064; v9 = &unk_EA328; } else { v7 = off_D7068; v8 = off_D706C; v9 = &unk_EA329; v6 = 131; } v10 = ((int (__fastcall *)(void *, void *, int, void *, int))loc_74AC4)(v7, v8, v6, v9, a4); v11 = (char *)malloc(1u); if ( !v11 ) return 0; v12 = 0; LABEL_6: v13 = 0; while ( a2 != v13 ) { *(&v22 + v13) = *(_BYTE *)(a1 + v13); if ( ++v13 == 3 ) { v25 = v22 >> 2; v28 = v24 & 0x3F; v26 = (v23 >> 4) | (16 * (v22 & 3)); v27 = (v24 >> 6) | (4 * (v23 & 0xF)); v11 = (char *)realloc(v11, v12 + 4); a2 -= 3; a1 += 3; for ( i = 0; i != 4; ++i ) v11[v12 + i] = *(_BYTE *)(v10 + (unsigned __int8)*(&v25 + i)); v12 += 4; goto LABEL_6; } } if ( v13 ) { for ( j = v13; j <= 2; ++j ) *(&v22 + j) = 0; v25 = v22 >> 2; v28 = v24 & 0x3F; v26 = (v23 >> 4) | (16 * (v22 & 3)); v17 = 0; v27 = (v24 >> 6) | (4 * (v23 & 0xF)); while ( v13 + 1 != v17 ) { v11 = (char *)realloc(v11, v12 + v17 + 1); v11[v12 + v17] = *(_BYTE *)(v10 + (unsigned __int8)*(&v25 + v17)); ++v17; } v18 = v12 + v17; for ( k = 0; v13 + k <= 2; ++k ) { v11 = (char *)realloc(v11, v18 + k + 1); v20 = &v11[k]; v20[v12 + v17] = 61; } v12 = v18 + k; } result = realloc(v11, v12 + 1); result[v12] = 0; return result; }

off_D7068; v10 = a3; do { v11 = *(char **)(v7 + 4 * (a1 & 0xF) + 4 * (v6 & 0xF)); v12 = *(_BYTE *)(v7 + 4 * (a1 & 0xF) + 4 * (v6 & 0xF)); v13 = (unsigned __int8)v11[a2 & 0xF]; for ( i = 0; i < v10; ++i ) { j = (unsigned __int8)v11[a2 & 0xF]; if ( v13 > j ) v13 = j; ++v11; } v17 = 0; v18 = 0; for ( k = 0; k < v12; ++k ) { v20 = *(char **)(v8 + 4 * (a1 & 0xF) + 4 * (v6 & 0xF)); if ( (unsigned __int8)v20[a2 & 0xF] == v13 ) ++v17; ++v18; ++v20; } v22 = 0; *(_BYTE *)(v9 + 4 * (a1 & 0xF) + 4 * (v6 & 0xF)) = v17; v23 = 0; v24 = 0; v25 = 0; v26 = 0; v27 = 0; v28 = 0; result = (_BYTE *)sub_749E8(a1, v6, &v22); v6 += 8; v10 -= 8; } while ( v10 > 0 ); } else { result = 0; } return result; }这个函数可以用来计算特定条件下字符串数组中的最小值。我可以将其命名为calculateMinimumValueOfStringArray()。

R8-1 字母分家 分数 10 作者 DS课程组 单位 临沂大学 已知一个字符序列，请提出一种较优的算法将所有大写字母调整到序列的左边，所有小写字母调整到序列的右边，并完成以下三个问题： （1）写出这算法思路的操作步骤。 （2）用C语言实现（1）中的算法，自行设计函数名和参数。 （3）分析算法的时间复杂度。

算法思路的操作步骤：

1. 定义两个指针left和right，分别指向字符序列的起始位置和末尾位置。
2. 当left < right时，循环执行以下步骤：
- 如果str[left]是小写字母，则left指针向右移动，直到str[left]是大写字母。
- 如果str[right]是大写字母，则right指针向左移动，直到str[right]是小写字母。
- 如果left < right，交换str[left]和str[right]的值，并将left指针向右移动，right指针向左移动。
3. 循环结束后，所有大写字母都在左边，所有小写字母都在右边。

C语言实现：

void adjust(char* str, int len) {
    int left = 0, right = len - 1;
    while (left < right) {
        while (left < right && str[left] >= 'A' && str[left] <= 'Z') {
            left++;
        }
        while (left < right && str[right] >= 'a' && str[right] <= 'z') {
            right--;
        }
        if (left < right) {
            char temp = str[left];
            str[left] = str[right];
            str[right] = temp;
            left++;
            right--;
        }
    }
}

算法的时间复杂度：

该算法的时间复杂度为O(n)，其中n为字符序列的长度。因为算法只需要对字符序列进行一次遍历，所以时间复杂度为线性的。