题目描述

给定一个数组arr， 和一个数num， 请把小于num的数放在数组的左边， 等于num的数放在数组的中间， 大于num的数放在数组的右边。

解法

测试结果及代码

#include <iostream>
#include <stdlib.h>
using namespace std;

const int num = 3;

void printArray(int a[], int N) {
    for (int i = 0; i < N; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
}

void Swap(int &x, int &y) {
    int t = x;
    x = y;
    y = t;
}

void compare(int a[], int N) {
    int cur = 0;
    int more = N - 1;
    int left = 0;
    while (cur <= more) {
        if (a[cur] < num) {
            Swap(a[cur++], a[left++]);
        } else if (a[cur] == num) {
            cur++;
        } else {
            Swap(a[cur], a[more--]);
        }
    }
}

void test(int a[], int N) {

}

int main (int argc, char* argv[]) {

    srand(time(NULL));
    const int size = 10;           // 随机生成的数组大小
    const int test_time = 30;      // 测试次数
    int a[size] = {0};             // 原始数组
    int tmp1[size] = {0};          // 测试数组
    int tmp2[size] = {0};          // 对比数组
    int tmp3[size] = {0};          // 展示数组

    for (int cnt = 0; cnt < test_time; ++cnt) {
        for (int i = 0; i < size; ++i) {
            a[i] = rand() % 4 + 2;
        }
        for (int i = 0; i < size; ++i) {
            tmp1[i] = a[i];
            tmp2[i] = a[i];
            tmp3[i] = a[i];
        }
        cout << "第 " << cnt << " 次生成:";
        printArray(tmp3, size);
        compare(tmp1, size);
        cout << "第 " << cnt << " 次对比:";
        printArray(tmp1, size);
        // test(tmp2, size);
        // cout << "第 " << cnt << " 次测试:";
        // printArray(tmp2, size);
        cout << endl;
    }

    return 0;
}