快速排序法 (quick sort)是运用分治思想(divide and conquer)对一个数组进行排序的比较排序算法。它主要思想是:以某个数为轴,将这个数组划分成两部分:不大于这个轴的一部分和大于这个轴的一部分;然后在分别对剩下的两部分进行同样的操作;一直分下去,直到每部分只有一个元素位置为止。
如何划分成两部分?严蔚敏的《数据结构》和《算法导论》有两种不同的具体实现
【严】的描述如下:设置两个数组下标low,high,low从前向后移动,high从后往前移动,保证low之前的部分都是不大于轴,high之后的部分都是大于轴; 每次low找到一个大于轴的元素,high找到一个不大于轴的元素,交换这两个元素的位置。如果low等于high了,则把这个位置和轴所在地位置交换。
《算法导论》上的划分是这样的:也是给定两个数组下标i和j,i和j都从前往后移动; 保证i之前的部分都不大于轴,j之后的部分(包含j)都未知; j向后滑动中如果某个元素不大于轴,这把这个元素的位置和i交换,并且i向前移动一个位置. 当j到达末尾后,把轴的位置与i位置上的元素交换,i即为分界点。
如何非递归实现?一般书上的快速排序法都是用递归实现的,递归是编译器自动用栈来实现的。当递归层次比较深时,需要占用比较大的进程栈空间,还有进程栈溢出的危险。很多时候将递归转化为非递归算法,更省时间和空间。
其实原理很简单,即自己用栈来模拟递归的过程。每次从栈顶取出一部分做划分后,都把新的两部分的起始位置分别入栈。
c++算法实现如下(采用《算法导论》上的方法):
#ifndef MAX_STACK_DEPTH
#define MAX_STACK_DEPTH 1000
#endif
template <typename T>
void NonrecursiveQuickSort(T arr[], size_t size)
{
// typedef vector<int> Stack_t;
int stack[MAX_STACK_DEPTH];
int top = 0;
int low,high,i,j,pivot;
T temp;
//首先把整个数组入栈
stack[top++] = size-1;
stack[top++] = 0;
while(top != 0)
{
//取出栈顶元素,进行划分
low = stack[--top];
high = stack[--top];
pivot = high; //将最后一个元素作为轴
i = low; //保证i之前的元素的不大于轴
//j从前往后滑动
for(j=low; j < high; j++)
{
//如果碰到某个元素不大于轴,则与arr[i]交换
if(arr[j]<=arr[pivot])
{
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
}
}
//i为分界点,交换arr[i]和轴
if(i != pivot)
{
/*swap arr[i] and arr[pivot]*/
temp = arr[i];
arr[i] = arr[pivot];
arr[pivot] = temp;
}
//判断小于轴的部分元素如果多于一个的话, 则入栈
if(i-low > 1)
{
stack[top++] = i-1;
stack[top++] = low;
}
//判断大于轴的部分元素如果多于一个的话, 则入栈
if(high-i > 1)
{
stack[top++] = high;
stack[top++] = i+1;
}
}
}
分享到:
相关推荐
快速排序 非递归实现方式的完整源代码和测试结果。
利用栈来消除递归 模拟快速排序的过程 实现非递归的快速排序
两种方法: 传统的递归快速排序 采用非递归堆栈模拟
用栈实现的快速排序,避免了原来的递归算法
快速排序算法设计与分析总结 二叉树与树的转换前序、后序的递归、非递归算法,层次序的非递归算法的实现 二叉树与树的转换前序、后序的递归、非递归算法,层次序的非递归算法的实现,应包含建树的实现 实现树与...
快速排序一般用的是递归算法,利用系统的提供的栈结构,而此非递归算法没有利用栈,巧妙完成了排序,并提供人机交互界面
用非递归算法实现quicksort快速排序,高效
用C实现了快速排序的非递归算法. int quickpass ( sqlist &R, int low, int high ) { ... } void quicksort ( sqlist &r, int low, int high ) { ... }
此文档是快速排序的递归与非递归的具体实现代码
运用MATLAB实现的快速排序,作为自己的库函数,使用起来更为快速。
常见的四种排序算法是:简单选择排序、冒泡排序...其中的快速排序的优势明显,一般使用递归方式实现,但遇到数据量大的情况则无法适用。实际工程中一般使用“非递归”方式实现。实际工程中一般使用“非递归”方式实现。
详细解释了快速排序的java实现.里面有代码,还有注释说明
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速排序。其中的快速排序的优势明显,一般使用递归方式实现,但遇到数据量大的情况则无法适用。...本文搜集发布四种算法的源代码及非递归快速排序的代码。
非递归快速排序归并排序堆排序基数排序的实现 //快速排序 function quickSort ( arr ) { var parts = [ [ 0 , arr . length - 1 ] ] ; while ( parts . length ) { var part = parts . shift ( ) ; var l = part...
常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速排序。...本文搜集发布四种算法的源代码及非递归快速排序的代码。思路:从左到右,将相邻的进行比较,若前面数值大于后面数值,则交换,否则不交换。
常见的四种排序算法是:简单选择排序、冒泡排序、插入排序和快速...本文搜集发布四种算法的源代码及非递归快速排序的代码。思路:从左到右,从第二元素开始,与它前面的数比较,找到小于它的数就将数值插入元素前面。
(1) 冒泡排序和快速排序; (2) 插入排序和希尔排序; (3) 选择排序和堆排序; (4) 递归和非递归的归并排序。 2. 产生不同规模和分布的数据,以 Excel 生成算法执行时间 T(n)关于输入规模 n 的曲线的形式,...
常见的四种排序算法是:简单选择排序、冒泡...本文搜集发布四种算法的源代码及非递归快速排序的代码。算法思路:从左到右,以第一个元素作为基准数与后面的数作比较,找到比它小的数就交换。以此类推。直至循环结束。