nbuoj1170 n个数据排序

这道题目的主要思路是使用快速排序算法，时间复杂度为O(nlogn)。

快速排序的基本思路是通过一次排序将待排序数组分成两部分，一部分小于基准值，一部分大于基准值，然后对这两部分分别进行快速排序，直到整个数组有序。

下面是代码实现：

#include <iostream>
#include <vector>
using namespace std;

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int i = left, j = right;
    int pivot = nums[left];
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        nums[i] = nums[j];
        while (i < j && nums[i] < pivot) i++;
        nums[j] = nums[i];
    }
    nums[i] = pivot;
    quickSort(nums, left, i - 1);
    quickSort(nums, i + 1, right);
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    quickSort(nums, 0, n - 1);
    for (int i = 0; i < n; i++) {
        cout << nums[i] << " ";
    }
    cout << endl;
    return 0;
}

其中，left和right表示待排序数组的左右边界，pivot表示基准值。在while循环中，i和j分别从左右两端向中间移动，当i指向的元素大于等于基准值时，停止移动；当j指向的元素小于基准值时，停止移动。然后将i和j指向的元素进行交换。最后，将基准值放到i指向的位置。然后，递归地对左右两部分分别进行快速排序。

最后，输出排序后的数组即可。