排序算法——快速排序算法

快速排序的基本思想：
通过一趟排序将待排记录分隔成独立的两部分，一部分记录的关键字比基准值小，一部分记录的关键字比基准值大，然后再对这两部分进行同样操作。
1、快速排序递归算法

//快速排序,递归
int Parition(int* ar, int left, int right)
{assert(ar != nullptr);int tmp = ar[left];while (left < right){while (left < right && ar[right] > tmp) --right;ar[left] = ar[right];while (left < right && ar[left] <= tmp) ++left;ar[right] = ar[left];}ar[left] = tmp;return left;
}void QuickPass(int* ar, int left, int right)
{if (left < right){int pos = Parition(ar, left, right);QuickPass(ar, left, pos - 1);QuickPass(ar, pos + 1, right);}
}void QuickSort(int* ar, int n)
{QuickPass(ar, 0, n);
}

对于划分函数，可以进行优化，进行随机划分

int RandParition(int* arr, int left, int right)
{int index = rand() % (right - left + 1) + left;std::swap(arr[left], arr[index]);return Parition(arr, left, right);
}

但是程序栈空间的大小是会有上限的。所以递归的算法永远无法应用到大规模的数据上，毕竟栈空间有限。我们下面尝试用非递归算法实现快速排序 。
2、快速排序非递归算法（使用队列）

void QuickSort(int* ar, int len)
{int left = 0;int right = len;std::queue<int> qu;int mid = Parition(ar, left, right);if (mid > 1){qu.push(left);qu.push(mid - 1);}if (mid < right - 1){qu.push(mid + 1);qu.push(right);}while (!qu.empty()){left = qu.front(); qu.pop();right = qu.front();qu.pop();mid = Parition(ar, left, right);if (left < mid - 1){qu.push(left);qu.push(mid -1);}if (mid + 1 < right){qu.push(mid + 1);qu.push(right);}}}

3、快速排序的非递归算法（使用栈）

void QuickSort(int* ar, int len)
{std::stack<int> st; // 用栈保存每一个待排序子串的首尾元素下标int left = 0;int right = len - 1;int mid = Parition(ar, left, right);if (mid > 1){st.push(0);st.push(mid - 1);}if (mid < right - 1){st.push(mid + 1);st.push(right);}while (!st.empty()) {int right = st.top();st.pop();int left = st.top();st.pop();mid = Parition(ar, left, right);if (left < mid - 1){st.push(left);st.push(mid - 1);}if (right > mid + 1){st.push(mid + 1);st.push(right);}}
}

非递归快排中，队或者栈的思想是一模一样的，只不过注意一下出栈（队）的顺序就行了。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！