分治法排序，快速排序，归并排序

package com.comm.test;


import java.util.Collection;
import java.util.Collections;

import javax.swing.text.html.StyleSheet.ListPainter;

import oracle.net.aso.i;

import org.junit.Test;


//快速排序：最坏情况下运行时间O(n^2),平均运行时间O(nlogn),不需要辅助空间。不稳定的排序。
//归并排序：最好和最坏下，运行时间都为O(nlogn),需要辅助空间，稳定的排序。

public class SortTest {

public void mergeSort(int[] list,int x,int y,int[] temp){
int p,q,m,i=x;
if(y-x>1){//至少有2个元素
m=x+(y-x)/2;//求中间下标
p=x;
q=m;
mergeSort(list, x, m, temp);//排序前半段
mergeSort(list, m, y, temp);//排序后半段

while(p<m||q<y)//表示前半部分序列和后半部分序列只要有一个没有遍历完
{
if (q>=y||(p<m&&list[p]>list[q]))
{
temp[i++] = list[p++];//复制前半部分
}
else
{
temp[i++] = list[q++];//复制后半部分
}
}

    for(i=x;i<y;i++)
    list[i] = temp[i];//把临时空间的值复制到原数组
   
}

}

//快速排序  由于最先是hoare提出的所以叫hoare sort
public void HoareSort(int[] list,int left,int right){
int x=left;
int y=right;
while(x<y){
//以第一个元素为基数，  首先从最右边与基数比较，如果比基数小则 退出while
将它与基数交换。
//如果等于或大于基数 则y--  向左移动 ，直到找到一个比基数小的数为止
while(list[y]>=list[x]&&y>x){
y--;
}
if(y>x){
int temp=list[y];
list[y]=list[x];
list[x]=temp;
x++;
}
//交换一次之后，从左边往右边开始查找 找到一个比基数大的数为止，然后交换。
//如此循环 直到 x>y  ， 就已经完成一轮。 已经 按 基数 分成两个部分，
//左边比基数小 右边比基数大，
while(list[x]<=list[y]&&y>x){
x++;
}
if(y>x){
int temp=list[y];
list[y]=list[x];
list[x]=temp;
y--;
}

}
//然后递归调用，将左边部分 和右边部分,继续快速排序。

if(x==y){
HoareSort(list, left, x-1);
HoareSort(list, x+1, right);
}



}

@Test
public void sort(){
int[] list={2,5,1,8,4,7,2,0,1,2,6};
int[] temp=new int[11];

mergeSort(list,0, list.length, temp);
for (int i : list) {
System.out.print(i+",");
}

list=new int[] {2,5,1,8,4,7,2,0,1,2,6};

HoareSort(list, 0, list.length-1);
System.out.println();
for (int i : list) {
System.out.print(i+",");
}

}

}