課程設(shè)計題目：整型數(shù)組按奇偶排序
一贬丛、問題描述
已知數(shù)組 A[n] 中的元素為整型缰犁，設(shè)計算法將其調(diào)整為左右兩部分装蓬，左邊的元素為奇數(shù)腺逛，右邊的元素為偶數(shù)荷愕，并要求算法的時間復(fù)雜度為 。
二棍矛、基本要求
- 將數(shù)組按奇偶性排序安疗，奇數(shù)在左，偶數(shù)在右够委。
三荐类、概要設(shè)計
1. 算法的設(shè)計
采用快速排序的思路：設(shè)置兩個指針l和r，分別從左向右和從右向左掃描茁帽，當(dāng)l指向偶數(shù)且r指向偶數(shù)時玉罐，交換數(shù)值。
偽代碼如下
void sort_by_parity(int *first, int *last)
{
last--;
while (first < last)
{
while (first指向奇數(shù)且沒越界) first++;
while (last指向偶數(shù)且沒越界) last--;
swap(*first, *last);
first++, last--;
}
}
| 時間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|
四潘拨、詳細設(shè)計
1. 設(shè)計每個函數(shù)
主要工作為設(shè)計排序函數(shù)void sort_by_parity(int *first, int *last)吊输，參數(shù)規(guī)定為左閉右開，即實際含first但不含last战秋。具體見前文偽代碼璧亚。
2. 設(shè)計主函數(shù)
主函數(shù)包括輸入數(shù)據(jù)規(guī)模，生成隨機整型數(shù)組并輸出脂信，調(diào)用排序函數(shù)癣蟋，再輸出數(shù)組。
五狰闪、運行與測試
1. 測試環(huán)境
運行環(huán)境：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. 在調(diào)試程序的過程中遇到的問題與解決方案
暫未發(fā)現(xiàn)異常疯搅。
3. 設(shè)計的測試數(shù)據(jù)與測試結(jié)果
樣例1的數(shù)據(jù)規(guī)模為 n=5。
樣例2的數(shù)據(jù)規(guī)模為 n=10埋泵。
樣例3的數(shù)據(jù)規(guī)模為 n=20幔欧。
4. 程序清單及運行結(jié)果
程序清單如下
// ex2.cpp
// Encoding: UTF-8
/*
* 2.編寫程序：課本p53頁習(xí)題5(2)
* 課本p53頁習(xí)題5(2)：已知數(shù)組 A[n] 中的元素為整型罪治，設(shè)計算法將其調(diào)整為左右兩部分，
* 左邊的元素為奇數(shù)礁蔗，右邊的元素為偶數(shù)觉义，并要求算法的時間復(fù)雜度為 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（符合預(yù)期）
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（符合預(yù)期）
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（符合預(yù)期）
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
六浴井、總結(jié)與心得
如果數(shù)組是由鍵盤輸入的晒骇，那么采用鏈表也是可以的。
七磺浙、參考資料
- 王紅梅, 胡明, 王濤. 數(shù)據(jù)結(jié)構(gòu)(C++版)[M]. 2 版. 清華大學(xué)出版社, 2011.
