已知一组记录的关键字序列为(56，39，81，23，67，34，12，45)，请选择一种排序方法，把关键字序列排为递增的序列。 (1)请写出所选用的排序方法的名字。 (2)请写出每一趟排序的结果。 (3)请写出您所选排序方法的排序算法。

(1) 所选用的排序方法是快速排序。

(2) 快速排序的每一趟排序的结果如下：

第1趟排序：以第一个元素56为基准，将小于56的元素放在其左边，大于等于56的元素放在其右边。序列变为(45, 39, 23, 34, 12, 56, 81, 67)。

第2趟排序：以序列的第一个元素45为基准，将小于45的元素放在其左边，大于等于45的元素放在其右边。序列变为(23, 34, 12, 39, 45, 56, 81, 67)。

第3趟排序：以序列的第一个元素23为基准，将小于23的元素放在其左边，大于等于23的元素放在其右边。序列变为(12, 23, 34, 39, 45, 56, 81, 67)。

第4趟排序：以序列的第二个元素23为基准，将小于23的元素放在其左边，大于等于23的元素放在其右边。序列不变。

第5趟排序：以序列的第三个元素34为基准，将小于34的元素放在其左边，大于等于34的元素放在其右边。序列变为(12, 23, 34, 39, 45, 56, 81, 67)。

第6趟排序：以序列的第三个元素34为基准，将小于34的元素放在其左边，大于等于34的元素放在其右边。序列不变。

第7趟排序：以序列的第四个元素39为基准，将小于39的元素放在其左边，大于等于39的元素放在其右边。序列变为(12, 23, 34, 39, 45, 56, 81, 67)。

第8趟排序：以序列的第五个元素45为基准，将小于45的元素放在其左边，大于等于45的元素放在其右边。序列不变。

第9趟排序：以序列的第六个元素56为基准，将小于56的元素放在其左边，大于等于56的元素放在其右边。序列变为(12, 23, 34, 39, 45, 56, 67, 81)。

(3) 快速排序的排序算法如下：

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

快速排序的基本思想是：选取一个基准元素，将小于基准元素的元素放在其左边，大于等于基准元素的元素放在其右边，然后递归地对左右两部分进行排序。在上述实现中，基准元素选取的是序列中的第一个元素，排序过程采用双指针法，i指针从左往右扫描，j指针从右往左扫描，找到需要交换的元素后交换它们的位置，最后将基准元素和j指针对应位置的元素交换即可。