用非递归算法实现快速排序原理

快速排序的非递归实现可以使用栈来完成。首先将整个数组的左端点和右端点入栈。然后开始循环，每次从栈中弹出两个端点，对这两个端点所代表的子数组进行快排。这里可以使用双指针法，选取一个基准数，然后从左右两端开始扫描，将小于基准数的数放在基准数的左侧，将大于基准数的数放在基准数的右侧。这样一次扫描后，基准数所在的位置就是最终排定的位置。将排定位置的左右两侧端点入栈，继续进行循环，直至栈为空。

具体实现可以参考下面的代码：

void quickSortNonRecursive(int arr[], int left, int right) {
    stack<int> st;
    st.push(left);
    st.push(right);
    while (!st.empty()) {
        int r = st.top();
        st.pop();
        int l = st.top();
        st.pop();
        int i = l, j = r, x = arr[(l + r) / 2];
        while (i <= j) {
            while (arr[i] < x) i++;
            while (arr[j] > x) j--;
            if (i <= j) {
                swap(arr[i], arr[j]);
                i++;
                j--;
            }
        }
        if (l < j) {
            st.push(l);
            st.push(j);
        }
        if (i < r) {
            st.push(i);
            st.push(r);
        }
    }
}