JZ-C-14

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