非递归快速排序java（非递归快速排序 js）

今天给各位分享非递归快速排序java的知识，其中也会对非递归快速排序 js进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

微信号：cloud7591
如需了解更多，欢迎添加客服微信咨询。
复制微信号

本文目录一览：

• 1、编写 快速排序的非递归算法
• 2、如何用java输出一个数组的全排列？不能用递归，用递归的话，很快就内存溢出了！
• 3、求快速排序的非递归实现代码。
• 4、JAVA中对数组排序除了冒泡和直接遍历外还有没更好的方法？
• 5、java排序算法中，快速排序慢好多，还容易爆栈，求指教
• 6、快速排序的非递归实现

编写 快速排序的非递归算法

终于编写出来了，我写了两种，你看看：下面是代码：

/*非递归算法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(top0)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输出一个数组的全排列？不能用递归，用递归的话，很快就内存溢出了！

我觉得吧，你输出一个全排列用不了多少内存，怎么就能溢出呢？

首先，递归费不了多少内存，应该可以完成任务。

其次，你递归都干了些什么？别告诉我每层递归把数组复制一遍，你把位置递归一下就可以了。

如果不喜欢递归，可以自己弄个栈，其实差不多，速度略快，空间略小。

如果还是不明白，把全部源码贴出来看看。

求快速排序的非递归实现代码。

bool exchange(int array[], int begin, int end, int pos)

{

int pos_end = end;

int pos_begin = begin;

pos = begin;

if (begin = end)

return false;

while(pos_begin pos_end);

{

while (array[pos_end] array[pos]) pos_end--;

if (pos_end pos)

{

array[pos_end] = array[pos] + array[pos_end];

array[pos] = array[pos_end] - array[pos];

array[pos_end] = array[pos_end] - array[pos];

pos = pos_end;

}

while (array[pos_begin] array[pos]) pos_begin++;

if (pos_begin pos)

{

array[pos_begin] = array[pos] + array[pos_begin];

array[pos] = array[pos_begin] - array[pos];

array[pos_begin] = array[pos_begin] - array[pos];

pos = pos_begin;

}

}

return true;

}

struct Queue {

int begin;

int end;

struct Queue *next;

};

void QSort(int array[], int length)

{

struct Queue *head = (struct Queue *)malloc(sizeof(struct Queue));

struct Queue *tail = head;

int begin;

int end;

int pos;

head-begin = begin;

head-end = length - 1;

while (head != NULL)

{

struct Queue *tmp = head;

begin = head-begin;

end = head-end;

head-next = NULL;

if (exchange(array[], begin, end, pos))

{

tmp = (struct Queue *)malloc(sizeof(struct Queue));

tmp-begin = begin;

tmp-end = pos - 1;

tmp-next = NULL;

tail-next = tmp;

tail = tail-next;

tmp = (struct Queue *)malloc(sizeof(struct Queue));

tmp-begin = pos + 1;

tmp-end = end;

tmp-next = NULL;

tail-next = tmp;

tail = tail-next;

tmp = head;

head = tmp-next;

free(tmp);

}

}

}

JAVA中对数组排序除了冒泡和直接遍历外还有没更好的方法？

初级的排序方法有泡泡,插入和选择.高级的排序方法还有堆排序,希尔排序法,快速排序法. 快速排序法（quick sort）是目前所公认最快的排序方法之一（视解题的对象而定），虽然快速排序法在最差状况下可以达O(n2)，但是在多数的情况下，快速排序法的效率表现是相当不错的。 快速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边数列进行排序，而影响快速排序法效率的正是轴心的选择。 1. 将最左边的数设定为轴，并记录其值为 s 循环处理： 1. 令索引 i 从数列左方往右方找，直到找到大于 s 的数 2. 令索引 j 从数列左右方往左方找，直到找到小于 s 的数 3. 如果 i = j，则离开循环 4. 如果 i j，则交换索引i与j两处的值 5. 将左侧的轴与 j 进行交换 6. 对轴左边进行递归 7. 对轴右边进行递归 透过以下算法，则轴左边的值都会小于s，轴右边的值都会大于s，如此再对轴左右两边进行递归，就可以对完成排序的目的，例如下面的实例，*表示要交换的数，[]表示轴： [41] 24 76* 11 45 64 21 69 19 36* [41] 24 36 11 45* 64 21 69 19* 76 [41] 24 36 11 19 64* 21* 69 45 76 [41] 24 36 11 19 21 64 69 45 76 21 24 36 11 19 [41] 64 69 45 76 在上面的例子中，41左边的值都比它小，而右边的值都比它大，如此左右再进行递归至排序完成。 public class QuickSort { public static void sort(int[] number) { sort(number, 0, number.length-1); } private static void sort(int[] number, int left, int right) { if(left right) { int s = number[left]; int i = left; int j = right + 1; while(true) { // 向右找 while(i + 1 number.length number[++i] s) ; // 向左找 while(j -1 -1 number[--j] s) ; if(i = j) break; swap(number, i, j); } number[left] = number[j]; number[j] = s; sort(number, left, j-1); // 對左邊進行遞迴 sort(number, j+1, right); // 對右邊進行遞迴 } } private static void swap(int[] number, int i, int j) { int t; t = number[i]; number[i] = number[j]; number[j] = t; }}

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 为止*/

}

关于非递归快速排序java和非递归快速排序 js的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。