对一个整型数组A[n]设计一个排序算法

对一个整型数组A[n]进行排序，我们可以选择多种经典的排序算法，如冒泡排序、插入排序、选择排序、快速排序、归并排序等。这里我们以快速排序为例，它是一种常用的高效排序算法。

**快速排序算法步骤：**
1. **选择基准元素**：通常从数组的第一个元素开始，也可以随机选取。
2. **划分过程**（Partition）：
- 定义两个指针，i从0开始，j从数组尾部开始。
- 比较A[i]和A[j]，如果A[i]小于基准（或大于），则交换A[i]和A[j]的位置，然后i向前移动一位；否则，j向后移一位。
- 当i >= j时，停止比较。此时，A[i]就是新的基准位置，并将所有比它小的数放在左边，比它大的数放在右边。
3. **递归排序**：分别对基准左右两侧的子数组递归应用上述过程，直到整个数组有序。

**伪代码示例**：

function quicksort(A[], low, high):
    if low < high:
        pivot_index = partition(A[], low, high)
        quicksort(A[], low, pivot_index - 1)  // 左侧子数组
        quicksort(A[], pivot_index + 1, high)  // 右侧子数组

function partition(A[], low, high):
    pivot = A[low]
    i = low + 1
    for j = low + 1 to high:
        if A[j] <= pivot:
            swap(A[i], A[j])
            i = i + 1
    swap(A[low], A[i])  // 将基准移到正确的位置
    return i