void QSort(int * a,int begin,int end)
{
if(begin < end)
{
int i = begin;
int j = end+1; //关键
int k = a[i],tmp;
while(i < j) //
{
i = i + 1;
while(a[i] < k)
i ++;
j = j - 1;
while(a[j] > k)
j --;
if(i < j)
{
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
tmp = a[begin]; //注意此时a[begin] 与 a[j] 交换
a[begin] = a[j];
a[j] = tmp;
QSort(a,begin,j - 1);
QSort(a,j + 1,end);
}
}
上是最简单的快速排序版本
/*
插入排序
*/
void insertSort(int * a,int begin,int end)
{
int tmp;
for(int j = begin + 1;j<= end;j++)
{
tmp = a[j];
int i = j -1;
//while(a[i] < a[j]) //不能这么写,因为a[i] 会被覆盖掉,此时的a[i]已不是彼时的a[i]
while(tmp < a[i])
{
a[i + 1] = a[i];
i --;
}
a[i + 1] = tmp;
}
}
/*
这个算法来自sgi stl
*/
int middle(int a,int b,int c)
{
if(a < b) //其实就是在这个大的条件下,依次return b ,c a
{
if(b < c) // a < b < c
return b;
else if(a < c) // a < b ; b > = c ; a < c
return c;
else // a < b ; a >= c
return a;
}
else {
if(b > c) // a > b > c
return b;
else if(a > c) // a > b ;b <= c;
return c;
else // a > b ; a < c
return a;
}
}
/*
首先,分划元素k 取得是a[begin],a[middel],a[end]的中值
其次,如果分得的子数组长度小于等于3,则调用insertSort
*/
void AdvancedQSort(int * a,int begin,int end)
{
if(begin >= end)
return ;
if(end - begin <= 3)
insertSort(a,begin,end);
else
{
int i = begin,j = end,k = middle(a[i],a[j],a[(i + i) / 2]),tmp;
while(i < j) //
{
i = i + 1;
while(a[i] < k)
i ++;
j = j - 1;
while(a[j] > k)
j --;
if(i < j)
{
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
tmp = a[begin]; //注意此时a[begin] 与 a[j] 交换
a[begin] = a[j];
a[j] = tmp;
AdvancedQSort(a,begin,j - 1);
AdvancedQSort(a,j + 1,end);
}
}
分享到:
相关推荐
快速排序 非递归实现方式的完整源代码和测试结果。
c++代码-递归-快速排序
利用栈来消除递归 模拟快速排序的过程 实现非递归的快速排序
可以用递归快速实现排序算法,简洁高效,算法复杂度比较合理
快速排序已经是很成熟的排序方法 递归的缺点就是当排序数据量大时,系统堆栈会溢出 递归的实质是在堆栈中不断保存现场,但是现场的数据量是很大的 网上给出了堆栈实现的伪码算法,但是这里面存在很多的BUG 这个程序...
使用递归的方法实现快速排序,简洁明了,避免了烦琐的考虑循环。
java 快速排序 折半查找的界面实现 (递归与分治法)
两种方法: 传统的递归快速排序 采用非递归堆栈模拟
插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
用栈实现的快速排序,避免了原来的递归算法
采用递归分治算法写的快速排序 这是为上机考试准备的,呵呵
快速排序一般用的是递归算法,利用系统的提供的栈结构,而此非递归算法没有利用栈,巧妙完成了排序,并提供人机交互界面
用C实现了快速排序的非递归算法. int quickpass ( sqlist &R, int low, int high ) { ... } void quicksort ( sqlist &r, int low, int high ) { ... }
C 排序 数据结构 链表 堆排序 希尔排序 快速排序 递归排序。详细解释了每个排序方法原理,并带有程序代码。是学习C语言的绝好资料
此文档是快速排序的递归与非递归的具体实现代码
以VC++6.0中MFC界面编写多项式相乘和快速排序算法,基于递归分治思想
C语言 C语言编程 排序法学习
快速排序快速排序(Quicksort)是对冒泡排序的一种改进。适用很广,高效的排序方法。
源程序给出了插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序等多种排序算法,其中有17处需要填空。