整型数组按奇偶排序实验报告

课程设计题目：整型数组按奇偶排序

一、问题描述

已知数组 A[n] 中的元素为整型，设计算法将其调整为左右两部分，左边的元素为奇数，右边的元素为偶数，并要求算法的时间复杂度为 $O(n)$ 。

二、基本要求

将数组按奇偶性排序，奇数在左，偶数在右。

三、概要设计

1. 算法的设计

采用快速排序的思路：设置两个指针l和r，分别从左向右和从右向左扫描，当l指向偶数且r指向偶数时，交换数值。

伪代码如下

void sort_by_parity(int *first, int *last)
{
    last--;
    while (first < last)
    {
        while (first指向奇数且没越界) first++;
        while (last指向偶数且没越界) last--;
        swap(*first, *last);
        first++, last--;
    }
}

时间复杂度	空间复杂度
$O(n)$	$O(1)$

四、详细设计

1. 设计每个函数

主要工作为设计排序函数void sort_by_parity(int *first, int *last)，参数规定为左闭右开，即实际含first但不含last。具体见前文伪代码。

2. 设计主函数

主函数包括输入数据规模，生成随机整型数组并输出，调用排序函数，再输出数组。

五、运行与测试

1. 测试环境

运行环境：Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM

编译器：gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)

编译命令：-g

运行终端：cmd

2. 在调试程序的过程中遇到的问题与解决方案

暂未发现异常。

3. 设计的测试数据与测试结果

样例1的数据规模为 n=5。

样例2的数据规模为 n=10。

样例3的数据规模为 n=20。

4. 程序清单及运行结果

程序清单如下

// ex2.cpp
// Encoding: UTF-8

/*
 * 2.编写程序：课本p53页习题5(2)
 * 课本p53页习题5(2)：已知数组 A[n] 中的元素为整型，设计算法将其调整为左右两部分，
 * 左边的元素为奇数，右边的元素为偶数，并要求算法的时间复杂度为 O(n) 。
 */

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

void sort_by_parity(int *first, int *last)
{
    last--;
    while (first < last)
    {
        while (*first & 1 && first < last)
            first++;
        while (~*last & 1 && first < last)
            last--;
        swap(*first, *last);
        first++, last--;
    }
}

int main()
{
    srand(time(NULL));

    int n;
    cout << "Please input n: ";
    cin >> n;

    int A[n];
    cout << "A: ";
    for (int i = 0; i < n; i++)
        cout << (A[i] = rand()) << " ";
    cout << endl;

    sort_by_parity(A, A + n);
    cout << "Sorting by parity complete." << endl;

    cout << "A: ";
    for (int i = 0; i < n; i++)
        cout << A[i] << " ";
    cout << endl;

    return 0;
}

样例 1（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex2
Please input n: 5
A: 208 15909 14589 16796 18237
Sorting by parity complete.
A: 18237 15909 14589 16796 208

样例 2（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex2
Please input n: 10
A: 172 28749 14691 14243 3081 20052 557 2788 1706 2433
Sorting by parity complete.
A: 2433 28749 14691 14243 3081 557 20052 2788 1706 172

样例 3（符合预期）

D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week03>ex2
Please input n: 20
A: 221 26135 20510 14745 26728 13417 14475 24415 20004 8516 11786 2040 346 10209 17337 11159 17600 15913 7601 3196
Sorting by parity complete.
A: 221 26135 7601 14745 15913 13417 14475 24415 11159 17337 10209 2040 346 11786 8516 20004 17600 26728 20510 3196

六、总结与心得

如果数组是由键盘输入的，那么采用链表也是可以的。

七、参考资料

王红梅, 胡明, 王涛. 数据结构(C++版)[M]. 2 版. 清华大学出版社, 2011.