2.请实现非递归的快速排序算法。

好的，以下是非递归的快速排序算法实现：

void quickSort(int arr[], int low, int high) {
    int stack[high - low + 1]; // 定义栈
    int top = -1;
    stack[++top] = low;
    stack[++top] = high;
    while (top >= 0) {
        high = stack[top--];
        low = stack[top--];
        int pivot = partition(arr, low, high);
        if (pivot - 1 > low) {
            stack[++top] = low;
            stack[++top] = pivot - 1;
        }
        if (pivot + 1 < high) {
            stack[++top] = pivot + 1;
            stack[++top] = high;
        }
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

这个算法使用了一个栈来代替递归调用，可以避免递归调用时栈溢出的问题。其核心思想是利用 partition 函数将数组分成两部分，并将枢轴元素放在正确的位置上。然后对于左右两部分分别进行快速排序即可。