㈠ 把快速排序递归算法改成非递归
可以用栈把那些要排的东西记下来如，起始位置，结束位置，基准位置，再一个一个的排，直到栈为空
／／还有很多没有写你自己去填上
struct qq{
int frist;
int last;
}QQ[MAXSIZE];
int a[max];
struct qq dd,ff;
while(!empty(QQ)){
dd=pop(QQ);//不为空就出栈
qkOne(a[],dd->frist,dd->last);//把这一部分排好；
if(dd->frist<i){ ff->frist=dd-frist;ff->last=i-1;push(ff,QQ);}//这里改为入栈就可以了，下同
if(i<dd->last){ff->frist=i+1;ff->last=dd->last;push(ff,QQ);}
｝
}
void qkOne(int a[],int frist,int last)；//frist为起始位置，last为终止位置
{ int x,i,j;
i=frist;
j=last;
x=a[i];//将第一个值保存在x中,做基准值。
while(i!=j)
{
while(i<j && a[j]>=x)
; /*自右向左扫描*/
if(i<j)
{
;
i++;
}
while(i<j&&a[i]<=x)
i++; /*自左向右扫描*/
if(i<j)
{ a[j]=a[i];
;
}
}
;
㈡ java中有哪几种常用的排序方法
最主要的是冒泡排序、选择排序、插入排序以及快速排序
1、冒泡排序
冒泡排序是一个比较简单的排序方法。在待排序的数列基本有序的情况下排序速度较快。若要排序的数有n个，则需要n-1轮排序，第j轮排序中，从第一个数开始，相邻两数比较，若不符合所要求的顺序，则交换两者的位置；直到第n+1-j个数为止，第一个数与第二个数比较，第二个数与第三个数比较，......，第n-j个与第n+1-j个比较，共比较n-1次。此时第n+1-j个位置上的数已经按要求排好，所以不参加以后的比较和交换操作。
例如：第一轮排序：第一个数与第二个数进行比较，若不符合要求的顺序，则交换两者的位置，否则继续进行二个数与第三个数比较......。直到完成第n-1个数与第n个数的比较。此时第n个位置上的数已经按要求排好，它不参与以后的比较和交换操作；第二轮排序：第一个基轮州数与第二个数进行比较，......直到完成第n-2个数与第n-1个数的比较；......第n-1轮排序：第一个数与第二个数进行比较，若符合所要求的顺序，则结束冒泡法排序；若不符合要求的顺序，则交换两者的位置，然后结束冒泡法排序。
共n-1轮排序处理，第j轮进行n-j次比较和至多n-j次交换。
从以上排序过程可以桐汪看出，较大的数像气泡一样向上冒，而较小的数往下沉，故称冒泡法。
public void bubbleSort(int a[])
{
int n = a.length;
for(int i=0;i<n-1;i++)
{
for(int j=0;j<n-i-1;j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
2、选择排序
选择法的原理是先将第一个数与后面的每一个数依次比较,不断将将小的赋给第一个数,从而找出最小的,然后第二个数与后面的每一个数依次比较,从而找出第二小的,然后第三个数与后面的每一个数依次比较,从而找出第三小的.....直到找到最后一个数。
public void sort(int x[])
{
int n=x.length;
int k,t;
for(int i=0;i<n-1;i++)
{
k=i;
for(int j=i+1;j=n;j++)
{
if(x[j]>x[k])k=j;
if(k!=i)
{
t=x[i];
x[i]=x[k];
x[k]=t;
}
}
}
}
3、插入排序
插入排序的原理是对数组中的第i个元素，认为它前面的i-1个已经排序好，然后将它插入到前面的i-1个元素中。插入排序对少量元素的排序较为有效.
public void sort(int obj[])
{
for(int j=1;j<obj.length;j++)
{
int key=obj[j];
int i=j-1;
while(i>=0&&obj[i]>key)
{
obj[i+1]=obj[i];
i--;
}
obj[i+1]=key;
}
}
4、快速排序
快速排序是对冒泡排序搏蔽的一种改进。它的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此大道整个数据变成有序序列。
public void quickSort(int obj[],int low,int high)
{
int i=low;
int j=high;
int keyValue=obj[i];
while(i<j)
{
int temp=0;
while(i<j&&obj[j]>=keyValue)
{
j=j-1;
}
temp=obj[j];
obj[j]=obj[i];
obj[i]=temp;
while(i<j&&obj[i]<=keyValue)
{
i=i+1;
}
temp=obj[j];
obj[j]=ojb[i];
obj[i]=temp;
}
obj[i]=keyValue;
if(low<i-1)
{
quickSort(obj,low,i-1);
}
if(high>i+1)
{
quickSort(obj,i+1,high);
}
}
㈢ java排序算法中，快速排序慢好多，还容易爆栈，求指教
代码没问题
我今天也遇到一样的问题
猜测是因为快排递归创建了很多栈，当数据量过大时就栈溢出
我的解决方法是自己也写了一个快速排序非递归的方法
但是实际耗费的时间仍然不如其他算法
㈣ 快速排序的非递归实现
快速排序简单的说就是选择一个基准，将比起大的数放在一边，小的数放到另一边。对这个数的两边再递归上述方法。
如改烂本题
66 13 51 76 81 26 57 69 23，以66为基准，升序排序的话，比66小的放左边，比66大的放右边， 类似这种情况 13 。。。 66。。。69
具体快速排序的规则一般如下：
从右边开始查找比66小的数，找到的时候先等一下，再从左边开始找比66大的数，将这两个数借助66互换一下位置，继续这个核高漏过程直到两次查找过程碰头。
例子中：
66 13 51 76 81 26 57 69 23
从右边找到23比66小，互换
23 13 51 76 81 26 57 69 66
从左边找到76比66大，互换
23 13 51 66 81 26 57 69 76
继续从右边找到57比66小，互换
23 13 51 57 81 26 66 69 76
从左边查找，81比66大，互换
23 13 51 57 66 26 81 69 76
从右边开始查找26比66小，互换
23 13 51 57 26 66 81 69 76
从左边开始查找，发现已经跟右边查找碰头了，结念败束，第一堂排序结束
下面排序C语言的排序快速代码，参考一下
void sort(int *a, int left, int right)
{
if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];
while(i < j) /*控制在当组内寻找一遍*/
{
while(i < j && key <= a[j])
/*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/
{
j--;/*向前寻找*/
}
a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
a[left]，那么就是给key）*/
while(i < j && key >= a[i])
/*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
{
i++;
}
a[j] = a[i];
}
a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}
㈤ 编写 快速排序的非递归算法
终于编写出来了，我写了两种，你看看：下面是代码：
/*非递归算法1
递归算法的开销很大，所以在下编了一个非递归的，算法描述如下：
A non-recursive version of quick sort using stack:
There are 2 stacks, namely one which stores the start of
a subarray and the other which stores the end of the
subarray.
STEP 1: while the subarray contains more than one element
,i.e. from Do {
SUBSTEP 1. pivot=Partion(subarray);
SUBSTEP 2. keep track of the right half of the current
subarray i.e. push (pivot+1) into stackFrom, push (to) into stackTo
SUBSTEP 3. go on to deal with the left half of
the current subarray i.e. to=pivot-1
}
STEP 2: if(neither of the stacks is empty)
Get a new subarray to deal with from the stacks.
i.e. start=pop(stackFrom); to=pop(stackTo);
STEP 3: both stacks are empty, and array has
been sorted. The program ends.
*/*/
void UnrecQuicksort(int q[],int low,int high)
{stack s1;<br/>stacks2;<br/> s1.push(low);<br/> s2.push(high);<br/> int tl,th,p;<br/> while(!s1.empty() && !s2.empty())<br/> {tl=s1.top();th=s2.top();<br/> s1.pop();s2.pop();<br/> if(tl>=th) continue;<br/> p=partition(q,tl,th);<br/> s1.push(tl);s1.push(p+1);<br/> s2.push(p-1);s2.push(th);<br/> }
}
/*非递归算法2
要把递归算法改写成非递归算法，可引进一个栈，这个栈的大小取决于递归调用的深度，最
多不会超过n，如果每次都选较大的部分进栈，处理较短的部分，递归深度最多不超过log2n
，也就是说快速排序需要的附加存储开销为O（log2n）。
*/
void UnrecQuicksort2(int q[],int low,int high)
{int *a;<br/> int top=0,i,j,p;<br/> a=new int[high-low+1];<br/> if(a==NULL) return;<br/> a[top++]=low;<br/> a[top++]=high;<br/> while(top>0)<br/> {i=a[--top];<br/> j=a[--top];<br/> while(j {p=partition(q,j,i);<br/> if(p-j {//先分割前部,后部进栈<br/>a[top++]=p+1;<br/> a[top++]=i;<br/> i=p-1;<br/> }
else
{//先分割后部,前部进栈
a[top++]=j;
a[top++]=p-1;
j=p+1;
}
}
}
}
/*打印输出*/
void display(int p[],int len)
{for(int i=0;i cout<}
/*测试*/
int _tmain(int argc, _TCHAR* argv[])
{int a[]={49,65,97,12,23,41,56,14};
quicksort(a,0,7);
//UnrecQuicksort(a,0,7);
//UnrecQuicksort2(a,0,7);
display(a,8);
return 0;
}
㈥ 如何用java输出一个数组的全排列不能用递归，用递归的话，很快就内存溢出了！
我觉得吧，你输出一告凳个全排列用不了多少内存，怎么就能溢出呢？
首先，递归费不了多少内碰槐存，应该可以完成任务。
其次，你递归都干了些什么？别告诉我每层递归把数组复制一遍，你把位置递归一下就可以了。
如果不喜欢递归，可以自己弄个栈，其实袜吵旅差不多，速度略快，空间略小。
如果还是不明白，把全部源码贴出来看看。
㈦ 请大神帮我看一下 这个非递归快速排序 为什么在排待排数组含相同元素的时候会出错
左右比较的时候都没有把相当的情况考虑进去，当出现相等的时候，你的代码就会陷入死循环
㈧ 请问一下java快速排序源代码
快速排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class QuickSort implements SortUtil.Sort{
/* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
quickSort(data,0,data.length-1);
}
private void quickSort(int[] data,int i,int j){
int pivotIndex=(i+j)/岁橡2;
//swap
SortUtil.swap(data,pivotIndex,j);
int k=partition(data,i-1,j,data[j]);
SortUtil.swap(data,k,j);
if((k-i)>1) quickSort(data,i,k-1);
if((j-k)>悄雀庆1) quickSort(data,k+1,j);
}
/**
* @param data
* @param i
* @param j
* @return
*/
private int partition(int[] data, int l, int r,int pivot) {
do{
while(data[++l]<pivot);
while((r!=0)&&data[--r]>pivot);
SortUtil.swap(data,l,r);
}
while(l<r);
SortUtil.swap(data,l,r);
return l;
}
}
改进后的快速排序：
package org.rut.util.algorithm.support;
import org.rut.util.algorithm.SortUtil;
/**
* @author treeroot
* @since 2006-2-2
* @version 1.0
*/
public class ImprovedQuickSort implements SortUtil.Sort {
private static int MAX_STACK_SIZE=4096;
private static int THRESHOLD=10;
/启握* (non-Javadoc)
* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
*/
public void sort(int[] data) {
int[] stack=new int[MAX_STACK_SIZE];
int top=-1;
int pivot;
int pivotIndex,l,r;
stack[++top]=0;
stack[++top]=data.length-1;
while(top>0){
int j=stack[top--];
int i=stack[top--];
pivotIndex=(i+j)/2;
pivot=data[pivotIndex];
SortUtil.swap(data,pivotIndex,j);
//partition
l=i-1;
r=j;
do{
while(data[++l]<pivot);
while((r!=0)&&(data[--r]>pivot));
SortUtil.swap(data,l,r);
}
while(l<r);
SortUtil.swap(data,l,r);
SortUtil.swap(data,l,j);
if((l-i)>THRESHOLD){
stack[++top]=i;
stack[++top]=l-1;
}
if((j-l)>THRESHOLD){
stack[++top]=l+1;
stack[++top]=j;
}
}
//new InsertSort().sort(data);
insertSort(data);
}
/**
* @param data
*/
private void insertSort(int[] data) {
int temp;
for(int i=1;i<data.length;i++){
for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
SortUtil.swap(data,j,j-1);
}
}
}
}
㈨ java快速排序简单代码
.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px} 排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是快速排序算法：
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏誉渣宏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序梁灶通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒庆册泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n?)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症又犯了，查了 N 多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：
快速排序的最坏运行情况是 O(n?)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
1. 算法步骤
从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
2. 动图演示
代码实现 JavaScript 实例 function quickSort ( arr , left , right ) {
var len = arr. length ,
partitionIndex ,
left = typeof left != 'number' ? 0 : left ,
right = typeof right != 'number' ? len - 1 : right ;
if ( left