java快速排序非遞歸_Java實作遞歸與非遞歸的快速排序

挖坑法遞歸

void quicksort(int s[],int left,int right){

if(left

int temp,i=left,j=right;

temp=s[right];

while(i

//尋找左邊第一個大于基準值的下标

while(s[i]<=temp&&i

if(i

//尋找右邊第一個小于基準值的下标

while(s[j]>=temp&&i

if(i

}

s[i]=temp;

quicksort(s,left,i-1); //遞歸左邊部分數組

quicksort(s,i+1,right); //遞歸右邊部分數組

}

}

非遞歸(使用LinkedHashMap)

void quickSort1(int s[],int left,int right){

LinkedHashMap lhp=new LinkedHashMap<>();

//将0,n放入LinkedHashMap

lhp.put(left,right);

while(!lhp.isEmpty()){ //隻要有需要排序的段

//讀取left，right

Iterator> it=lhp.entrySet().iterator();

left=it.next().getKey();

right=lhp.get(left);

//并從LinkedHashMap中删除

lhp.remove(left,right);

if(left>=right)continue;

int i=left,j=right,temp=s[right];

while(i

while(s[i]<=temp&&i

if(i

while(s[j]>=temp&&i

if(i

}

s[i]=temp;

lhp.put(left,i-1);

lhp.put(i+1,right);

}

}