C++实现快速排序非递归算法
时间: 2024-01-07 20:22:59 浏览: 54
以下是C++实现快速排序非递归算法的示例代码:
```cpp
#include <iostream>
#include <stack>
using namespace std;
void quickSortNonRecursive(int* arr, int low, int high) {
stack<int> st;
st.push(low);
st.push(high);
while (!st.empty()) {
int end = st.top();
st.pop();
int start = st.top();
st.pop();
int pivot = arr[end];
int i = start - 1;
for (int j = start; j <= end - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[end]);
int pivotIndex = i + 1;
if (pivotIndex - 1 > start) {
st.push(start);
st.push(pivotIndex - 1);
}
if (pivotIndex + 1 < end) {
st.push(pivotIndex + 1);
st.push(end);
}
}
}
int main() {
int arr[] = {9, 5, 2, 7, 1, 8, 3};
int n = sizeof(arr) / sizeof(arr[0]);
quickSortNonRecursive(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```