JZ-C-14

剑指offer第十四题:调整数组顺序使得奇数在偶数之前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
//============================================================================
// Name        : JZ-C-14.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description :调整数组顺序使得奇数在偶数之前
//============================================================================
 
#include <iostream>
#include <stdio.h>
using namespace std;
 
void Reorder(int *pData, unsigned int length, bool (*func)(int));
bool isEven(int n);
 
// ====================方法一====================
void ReorderOddEven_1(int *pData, unsigned int length) {
    if (pData == NULL || length == 0)
        return;
 
    int *pBegin = pData;
    int *pEnd = pData + length - 1;
 
    while (pBegin < pEnd) {
        // 向后移动pBegin,直到它指向偶数
        while (pBegin < pEnd && (*pBegin & 0x1) != 0)
            pBegin++;
 
        // 向前移动pEnd,直到它指向奇数
        while (pBegin < pEnd && (*pEnd & 0x1) == 0)
            pEnd--;
 
        if (pBegin < pEnd) {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}
 
// ====================方法二====================
void ReorderOddEven_2(int *pData, unsigned int length) {
    Reorder(pData, length, isEven); //将判断标准函数指针作参数传入,修改判断标准函数即可实现模式应用
}
 
void Reorder(int *pData, unsigned int length, bool (*func)(int)) { //函数指针:同:typedef bool (*FuncPointer)(int); FunPointer func = isEven;
    if (pData == NULL || length == 0)
        return;
 
    int *pBegin = pData;
    int *pEnd = pData + length - 1;
 
    while (pBegin < pEnd) {
        // 向后移动pBegin
        while (pBegin < pEnd && !func(*pBegin))
            pBegin++;
 
        // 向前移动pEnd
        while (pBegin < pEnd && func(*pEnd))
            pEnd--;
 
        if (pBegin < pEnd) {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}
 
bool isEven(int n) {
    return (n & 1) == 0;
}
 
// ====================测试代码====================
void PrintArray(int numbers[], int length) {
    if (length < 0)
        return;
 
    for (int i = 0; i < length; ++i)
        printf("%d\t", numbers[i]);
 
    printf("\n");
}
 
void Test(char* testName, int numbers[], int length) {
    if (testName != NULL)
        printf("%s begins:\n", testName);
 
    int* copy = new int[length];
    for (int i = 0; i < length; ++i) {
        copy[i] = numbers[i];
    }
 
    printf("Test for solution 1:\n");
    PrintArray(numbers, length);
    ReorderOddEven_1(numbers, length);
    PrintArray(numbers, length);
 
    printf("Test for solution 2:\n");
    PrintArray(copy, length);
    ReorderOddEven_2(copy, length);
    PrintArray(copy, length);
 
    delete[] copy;
}
 
void Test1() {
    int numbers[] = { 1, 2, 3, 4, 5, 6, 7 };
    Test("Test1", numbers, sizeof(numbers) / sizeof(int));
}
 
void Test2() {
    int numbers[] = { 2, 4, 6, 1, 3, 5, 7 };
    Test("Test2", numbers, sizeof(numbers) / sizeof(int));
}
 
void Test3() {
    int numbers[] = { 1, 3, 5, 7, 2, 4, 6 };
    Test("Test3", numbers, sizeof(numbers) / sizeof(int));
}
 
void Test4() {
    int numbers[] = { 1 };
    Test("Test4", numbers, sizeof(numbers) / sizeof(int));
}
 
void Test5() {
    int numbers[] = { 2 };
    Test("Test5", numbers, sizeof(numbers) / sizeof(int));
}
 
void Test6() {
    Test("Test6", NULL, 0);
}
 
int main(int argc, char** argv) {
    Test1();
    Test2();
    Test3();
    Test4();
    Test5();
    Test6();
 
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注