2) 快速排序非递归实现 实验要求： 将数组 23,45,17,11,13,89,72,26,3,17,11,13，利用非递归算法，用栈模拟快速排序递归算法，实现数组从小到大排序。

快速排序是一种常用的高效排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。非递归实现快速排序通常采用“分治”的策略，但这里我们将借助栈的数据结构来模拟递归过程。

以下是使用Python的非递归快速排序实现步骤：

1. 定义两个辅助函数：
- `partition(arr, low, high)`：选择一个基准值，将数组分为两部分，使得所有小于基准的元素都在左边，大于等于基准的在右边。
- `quick_sort_stack(arr, low, high)`：栈用于存储子问题的状态（起始下标、结束下标），开始时只有一个初始任务（low=0, high=len(arr)-1）。

2. 初始化栈并入队第一个子问题（[low, high]）：

   stack = [(low, high)]

3. 当栈不为空时，从栈顶取出一个子问题，处理完毕后将其相邻的子问题加入栈：

   while stack:
       low, high = stack.pop()
       if low < high:
           pivot_index = partition(arr, low, high)
           stack.append((low, pivot_index - 1))  # 左边子问题
           stack.append((pivot_index + 1, high))  # 右边子问题

4. 定义`partition`函数：
- 首先取最后一个元素作为基准（arr[high]），然后从左向右遍历找到第一个大于或等于基准的元素索引（i）。
- 然后交换基准值和这个索引对应的元素，最后返回基准值的新位置。

   def partition(arr, low, high):
       pivot = arr[high]
       i = low - 1
       for j in range(low, high):
           if arr[j] <= pivot:
               i += 1
               arr[i], arr[j] = arr[j], arr[i]
       arr[i+1], arr[high] = arr[high], arr[i+1]
       return i + 1

5. 给定的实验数据示例：

   arr = [23, 45, 17, 11, 13, 89, 72, 26, 3, 17, 11, 13]
   quick_sort_stack(arr, 0, len(arr) - 1)
   print("Sorted array:", arr)

完成以上步骤后，你会得到一个从小到大排序后的数组。