二进制序列号排序与快速排序算法分析

2. 假定每份考卷都有一个 8 位的二进制序列号。当且仅当一个序列号含有偶数个 1 时，它才是有效的。例如，00000000、01010011 都是有效的序列号，而 11111110 不是有效的。（20分）

那么有效的序列号共有多少个？请说明原因。（4分）

有效的序列号共有 2^7 = 128 个。因为序列号有 8 位，每一位都有两种可能的取值（0 或 1），所以总共有 2^8 = 256 种不同的序列号。其中，有 128 个序列号中含有偶数个 1，另外 128 个序列号中含有奇数个 1。因此，只有含有偶数个 1 的序列号才是有效的。

考卷序列号收取是从大到小排序（即序列号从二进制转化为十进制的数值大小），现在需要将考卷序列号由大到小变为小到大的排序方式，想通过计算机的方式协作工作，你能用熟悉的程序语言写一个程序，将一个有序的从大到小的数据，转换成从小到大的数据吗？请写出实现的代码。（不能使用内置排序函数，排序方法要有具体实现方式）（6分）

下面是一个用 Python 编写的程序，实现将有序的从大到小的数据转换为从小到大的数据：

def reverse_sort(arr):
    n = len(arr)
    for i in range(n // 2):
        arr[i], arr[n - i - 1] = arr[n - i - 1], arr[i]
    return arr

# 示例
data = [10, 8, 6, 4, 2, 0]
print(reverse_sort(data))

输出结果为：[0, 2, 4, 6, 8, 10]

收到的考卷的二进制序列号经常会出现没有按照顺序进行存放，老师们讨论后决定采用快速排序的方式对将收集的无序二进制序列号按照从小到大的方式排序。请用熟悉的程序语言实现将无序数组从小到大排序，采用快速排序方式。（10 分）

下面是一个用 C 语言实现快速排序的代码：

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 8, 6, 4, 2, 0};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

输出结果为：0 2 4 6 8 10