快排递归非递归

我记得曾经 有一个大师说过这么一句话&＃xff0c;大概的意思是说如果你懂得了编程&＃xff0c;那么请你给我用非递归表达你的思想。我想非递归隐藏的东西恰恰应该是程序员应该注意的东西。因为递归的隐藏&＃xff0c;让我们其实没有真正的理解实现的具体细节。今天我想用非递归的方式去做一下快排。

大家都应该知道快排&＃xff1a;

1、不稳定排序

2、时间复杂度&＃xff1a;O(nlogn)。糟糕的时候时间复杂度是O(n*n)

思想是

1借用一个元素为flag 让数组左面的数组小于该flag&＃xff0c;右面的数大于该flag。

2左右分割区域继续找flag递归1步骤。

非递归的思想更能够清楚的描述快排的思想。

1、设置两个栈区&＃xff0c;分别记录前后区域的初始位置和结束为止。&＃xff08;开始为数组的0位置和终止位置len-1&＃xff09;

2、用快排思想找到flag。然后判断前后区域是否为空&＃xff0c;如果有一个不为空说明还有需要排序的数据。否则排序过程结束。

package example;

import java.util.Stack;

/**
* Created by Administrator on 2015/11/29.
*/
public class QuickSort {

public static void main(String[] args){
int[] a &＃61;new int[]{1,11,4,23,2,78,54,99,102,100,22,34};

       Stack start &＃61;new Stack();
       Stack end &＃61;new Stack();

       start.push(0);
       end.push(a.length-1);

while(!start.isEmpty()){
int start1&＃61; start.pop();
int end1 &＃61; end.pop();
int   priot&＃61;partition(a,start1,end1);
if(priot>start1&＃43;1){
               start.push(start1);
               end.push(priot-1);
           }
if(priot<&＃61;end1-1){
               start.push(priot&＃43;1);
               end.push(end1);
           }
       }
for(int i&＃61;0;i            System.out.println(a[i]);
       }


   }

private static int partition(int[] a, int start1, int end1) {
int priot &＃61; a[start1];
int start &＃61;start1;

while(start1 while(a[start1] while (a[end1]>priot)  end1--;
swap(a,start1,end1);
        }
       a[start1]&＃61;priot;
return start1;

   }

private static void swap(int[] a, int start1, int end1) {
int tmp&＃61;a[start1];

       a[start1]&＃61;a[end1];
       a[end1]&＃61;tmp;
   }


}

2016年8月3日

递归今天写了下&＃xff0c;还是总犯错啊&＃xff01;&＃xff01;&＃xff01;&＃xff0c;贴出代码吧&＃xff0c;继续学习

/**递归快排* &＃64;author hassop* &＃64;Description* &＃64;date 2016/8/3 0003* To change this template use File | Settings | File Templates.*/
public class QuickSearch {/*** 非递归* &＃64;param a*/static void quick(int[] a,int begin,int end){//终止条件if(begin&＃61;&＃61;end){return;}int i&＃61;begin&＃43;1;int j&＃61;end;int k &＃61;a[begin];//排序过程while(ik){j--;}while(a[i]&＃61;begin){quick(a,begin,i-1);}else {quick(a,begin,begin);}if((i&＃43;1)>&＃61;end){quick(a,end,end);}else{quick(a,i&＃43;1,end);}}static void sweap(int[] a,int i, int j) {int tmp &＃61;a[i];a[i]&＃61; a[j];a[j]&＃61;tmp;}/*psvm*/public static void main(String[] args) {int[] a &＃61;{2,1,3,4,19,5,6,8,39,21,65};quick(a, 0, a.length - 1);for(int i&＃61;0;i}