题解 | 最大公约数1 快排时间复杂度低

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

void gcd(int a, int b) {
    int c;
    c = a % b;
    while (c != 0) {
        a = b;
        b = c;
        c = a % b;
    }

    cout << b;
    return;
}

// 冒泡排序  时间复杂度太大了 O(n^2)
void bubbleSort(int data[], int n) {
    int temp;  // 暂存数组数据,交换数据
    for (int i = 0; i < n - 1; i++) { // n-1 轮排序
        bool flag = false;  // 一轮试探无乱序，直接跳过
        for (int j = n - 1; j > i; j--) {
            if (data[j - 1] > data[j]) { // 最多到i=1, i=0越界
                temp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = temp;
                flag = true;
            }
        }
        if (!flag) {
            return;
        }
    }
}

// 快速排序
int partition(int data[], int low, int high) {
    int pivot, temp;
    pivot = data[low]; // 最低元素作为枢轴元素
    while (low < high) {
        while ( low < high && data[high] >= pivot) {
            high--;
        }
        data[low] = data[high];
        while ( low < high && data[low] <= pivot) {
            low++;
        }
        data[high] = data[low];
    }
    data[low] = pivot; // 枢轴元素回归到正确的地方
    return low; // 返回已经排好序元素的下标
}

// 参数 不定大小 数组
void quickSort(int data[], int low, int high) {
    // 递归
    if (low < high) { // 跳出递归的条件
        int pivotpos = partition(data, low, high); // 划分数组 前半段 后半段
        quickSort(data, low, pivotpos - 1); // 前半段
        quickSort(data, pivotpos + 1, high); // 后半段
    }
}

int main() {
    int a, b, n;
    int* data;
    while (cin >> n) {
        data = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) {
            cin >> data[i];
        }
        // bubbleSort(data,n);  // 时间复杂度太高
        quickSort(data, 0, n - 1); // 快排 传递 int型指针 或者 int数组
        cout << data[0] << " " << data[n - 1] << " ";
        gcd(data[n - 1], data[0]);
        cout << endl;
        free(data);
    }
    return 0;
}