# Java算法之 快速排序的实现

```public class BaseQuickSort implements QuickSortExecutor{

private int[] arrays;

@Override
public void executor() {
if(arrays == null || arrays.length == 0)
{
throw new IllegalArgumentException("array can not be null or length is zero");
}

quickSort(0,arrays.length - 1);
}

private void quickSort(int low,int high)
{

int key  = arrays[high];
int begin = low;
int end   = high;
int position  = high;
int temp ;

while(begin <  end){
if(position  == end){
if(arrays[begin] <= key)
begin++;
else {
temp = arrays[begin];
arrays[begin] = key;
arrays[position]  = temp;
position  = begin;
end--;
}
}else if(position == begin)
{
if(arrays[end] >= key)
{
end--;
}else{
temp  = arrays[end];
arrays[end] = key;
arrays[position]  = temp;
position  = end;
begin++;
}
}
}

if(low < position - 1)
quickSort(low, position - 1);

if(position + 1 < high)
quickSort(position + 1,high);
}

public int[] getArrays() {
return arrays;
}

public void setArrays(int[] arrays) {
this.arrays = arrays;
}

public static void main(String[] args) {
BaseQuickSort sort  = new BaseQuickSort();

int[] arrays = new int[]{128,137,1898989,55,532,99,12,3,1000,255};

sort.setArrays(arrays);

sort.executor();

for(int i  = 0;i< arrays.length ;i++)
{
System.out.print(arrays[i] + "  ");
}
}
}```

```public class NoStackQuickSort implements QuickSortExecutor{

int[] arrays;

@Override
public void executor() {

if(arrays == null || arrays.length == 0)
{
throw new IllegalArgumentException("array can not be null or length is zero");
}
int[] stack  = new int[arrays.length];

int stacktop  = 0;

stack[stacktop] = 0;
stacktop++;
stack[stacktop] = arrays.length-1;
stacktop++;
while(stacktop != 0)
{
stacktop--;
int uhigh  = stack[stacktop];
stacktop--;
int ulow   = stack[stacktop];

if(uhigh > ulow)
{
// 进行排序 获得mid值
int mid = spitArrays(ulow, uhigh);
if(mid - ulow > uhigh - mid)
{
stack[stacktop] = ulow;
stacktop++;
stack[stacktop] = mid - 1;
stacktop++;
if(uhigh > mid)
{
stack[stacktop] = mid+1;
stacktop++;
stack[stacktop] = uhigh;
stacktop++;
}
}else{
stack[stacktop] = mid + 1;
stacktop++;
stack[stacktop] = uhigh;
stacktop++;
if(mid > ulow)
{
stack[stacktop] = ulow;
stacktop++;
stack[stacktop] = mid - 1;
stacktop++;
}
}
}
}

}

private int spitArrays(int low,int high){

int key  = arrays[high];
int begin = low;
int end   = high;
int position  = high;
int temp ;

while(begin <  end){
if(position  == end){
if(arrays[begin] <= key)
begin++;
else {
temp = arrays[begin];
arrays[begin] = key;
arrays[position]  = temp;
position  = begin;
end--;
}
}else if(position == begin)
{
if(arrays[end] >= key)
{
end--;
}else{
temp  = arrays[end];
arrays[end] = key;
arrays[position]  = temp;
position  = end;
begin++;
}
}
}

return position;
}

public int[] getArrays() {
return arrays;
}

public void setArrays(int[] arrays) {
this.arrays = arrays;
}

public static void main(String[] args) {

//设置十万个随机数

int length  = 10 * 10000;

int[] arrays  = new int[length];

int[] copyArrays = new int[length];

int[] bubbleArrays  = new int[length];

//开始使用内存的算法

Random random  = new Random();

for(int i  = 0;i< length;i++)
{
arrays[i]  = random.nextInt(Integer.MAX_VALUE);
}

System.arraycopy(arrays, 0, copyArrays, 0, length);
System.arraycopy(arrays, 0, bubbleArrays, 0, length);

//初始化进行测试
for(int i = 0;i<length ;i++)
{
if(arrays[i]  != copyArrays[i])
throw new IllegalArgumentException();
}

for(int i = 0;i<length ;i++)
{
if(arrays[i]  != bubbleArrays[i])
throw new IllegalArgumentException();
}

BaseQuickSort stackExecutor = new BaseQuickSort();
NoStackQuickSort noStackExecutor  = new NoStackQuickSort();
BubbleSortExecutor  bubbleExecutor  = new BubbleSortExecutor();

stackExecutor.setArrays(arrays);
noStackExecutor.setArrays(copyArrays);
bubbleExecutor.setArrays(bubbleArrays);

long begin = System.currentTimeMillis();

stackExecutor.executor();

long end   = System.currentTimeMillis();

System.out.println("运行时间：使用栈：" + (end  - begin));
//--------------------------------------
begin = System.currentTimeMillis();

noStackExecutor.executor();

end   = System.currentTimeMillis();

System.out.println("运行时间:不使用栈:" + (end - begin));

//-------------------------------------
begin   = System.currentTimeMillis();

bubbleExecutor.executor();

end  = System.currentTimeMillis();

System.out.println("运行时间,冒泡:" + (end - begin));

//测试是否排序正确
for(int i = 0;i<length ;i++)
{
if(arrays[i]  != copyArrays[i])
throw new IllegalArgumentException();
}

for(int i = 0;i<length ;i++)
{
if(arrays[i]  != bubbleArrays[i])
throw new IllegalArgumentException();
}

}
}```