快速排序与归并排序

快速排序的原理：

   选一个数组中的第一个元素作为参照物，把所有小于参照物的元素都放在参照物的左边，将所有大于参照物的元素都放在右边。在递归的各自的子数组。

   定义两个指针，分别从前遍历和从后遍历，向前遍历时，如果小于参照物，交换他们的位置，向后遍历时，如果大于参照物，交换他们的位置。直到两个指针相遇。

 

package calc;

 

public class QuickSort {

 

/**

* @param args

*/

public static void main(String[] args) {

        int data[] = {110,305,65,57,90,120,110,8,79,44};

        int min = 0;

        int max = 9;

        quickSort(data,min,max);

        for(int temp : data)

        System.err.println(temp);

}

public static void quickSort(int[] data,int min,int max){

int indexofpartition;

if(max>min){

//core

indexofpartition = findPartition(data,min,max);

quickSort(data,min,indexofpartition-1);

quickSort(data,indexofpartition+1,max);

}

}

public static int findPartition(int[] data,int min,int max){

int left,right,partitionIndex;

int temp,partitionelement;

partitionelement=data[min];

left=min;

right=max;

partitionIndex=min;

while(left<right){

 

            while(data[right]>partitionelement&&left<right)

             right--;

 

            temp = data[right];

            data[right] = data[partitionIndex];

            data[partitionIndex] = temp;

            partitionIndex = right;

 

            while(data[left]<=partitionelement&&left<right)

             left++;

 

            if(left<right){

           temp = data[left];

           data[left] = data[partitionIndex];

           data[left] = temp;

           partitionIndex = left;

            }

 

}

return partitionIndex;

}

}

归并排序

将一个数组分成两个数组，两个子数组再分两个子数组，直到每个子分组的元素个数都是1个，在将两个分组合并

左分组的元素和右分组元素比较，如果左的小就用左的，如果右的小就用右的。如果左分组或右分组有多余的元素，就直接添加到后面。

package calc;

public class MergeSort {

    

private static int count = 0 ;

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

   int[] data = {110,305,65,57,90,120,110,8,79,44};

mergeSort(data,0,9);

for(int temp:data)

System.err.println(temp);

}

public static void mergeArray(int[] data,int left,int mid,int right){

int leftstart=left,leftend=mid;

int rightstart=mid+1,rightend=right;

int k = 0;

int size = right-left+1;

int[] temp = new int[size];

while(leftstart<=leftend&&rightstart<=rightend){

if(data[leftstart]>data[rightstart]){

temp[k++] = data[leftstart++];

}else{

temp[k++] = data[rightstart++];

}

}

while(leftstart<=leftend)

temp[k++] = data[leftstart++];

while(rightstart<=rightend)

temp[k++] = data[rightstart++];

for(int i=0;i<k;i++){

data[left+i] = temp[i];

}

}

public static void mergeSort(int[] data,int left,int right){

if(left<right){

int middle = (left+right)/2;

System.err.println((++count)+"次调用,middle:"+middle);

mergeSort(data,left,middle);

mergeSort(data,middle+1,right);

mergeArray(data,left,middle,right);

}

}

}