Change from: http://blog.csdn.net/qt_pixie/article/details/1361777
MergeSort and QuickSort are two comparatively similar sort methods, which are implemented through Divide and Conquer. You need to sort in a recursion fashion.
Their similarity lies in the principle. The first thing to do is to split N elements into two parts for sorting, each part will continue to be divided into two parts for sorting, until only two elements can be easily compared and sorted. This is how recursion is used. It belongs to the Divide section in Divide and Conquer. When N elements are sorted into many small parts, all you have to do is merge them together to form a sorted list. This is merge, or Conquer. Both Sorts require merge, but the details are different. Here's an analysis of the differences between the two kinds of sorts.
MergeSort's split is relatively simple, separating all elements in a binary way, that is to say, the number of elements on the left is equal to that on the right, or the difference is 1 (for example, when there are five elements in total, they are divided into three elements on the left and two elements on the right). The complexity of the divide process can only be calculated as 1. The Conquer(Merge) part of MergeSort is relatively complex. When all elements are sorted into many small parts, the elements in each small part are sorted in order, and then need to be sorted with the elements in another small part. Because the elements on the left and the right are binary-separated when splitting, there is no size relationship between the elements on the left and the elements on the right, so it is necessary to compare the elements on the left and the elements on the right one by one in the merging process and store them in a new list. Thus, the complexity of the merging process is N. The complexity of MergeSort is N+2T(N/2). (The first N here refers to the complexity of merge). The computational complexity is NlgN.
QuickSort's split is more complex and has many ways. One way is to use the first element as pivot, and then put all elements smaller than this pivot on the left and larger than his on the right, so that both left and arbitrary elements are smaller than any element on the right. Method 2: The pivot (Index ofBegin + Index ofEnd)/2 is the method of median value. The criterion for selecting pivot is to try not to be too small or too close to the middle element, so that the number of parts separated by the pivot will not differ too much. If the first method is used and the element in the list happens to be sorted, the number of divide s is very different and the algorithm complexity is very high, which is N*N. In general, the complexity of QuickSort's split is N. Assume that all small parts of QuickSort's split method are a,b,c... Then all elements in a are smaller than those in b, and all elements in B are smaller than those in C. So it's very simple to merge a,b,c... The elements are arranged in order, and then B is placed directly behind a. The complexity here is only 1. So the overall complexity of QuickSort is N+2T(N/2), where the first N refers to the complexity of split. The computational complexity is NlgN.
Overall, MergeSort's split is convenient for merge, while QuickSort's split is complex and simple for merge. After understanding the principle, we can choose different sorting methods according to different situations.
Code from: http://blog.csdn.net/dream_mushuang/article/details/71104076
Merge Sort:
package mergeSort;
import java.util.Random;
/**
* Array are rearranged with smallest item first
* @author
*
*/
public class MergeSort {
private static final int NUM_ITEMS = 30;
private static final Random rnd = new Random();
public static void main(String[] args) {
Integer[] a = new Integer[NUM_ITEMS];
for(int i=0; i<a.length; i++){
a[i] = i;
}
permute(a);
print(a);
System.out.println("Merge Sort");
mergeSort(a);
print(a);
}
private static void print(Integer[] a){
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
System.out.println("\ndone....\n");
}
public static <T extends Comparable<? super T>>
void insertionSort(T[] array, int left, int right){
for(int p= left+1; p<= right; p++){
T tmp = array[p];
int j;
for(j=p; j>left && tmp.compareTo(array[j-1])<0; j--){
array[j] = array[j-1];
array[j] = tmp;
}
}
}
public static <T extends Comparable<? super T>>
void mergeSort(T[] a){
@SuppressWarnings("unchecked")
T[] tmpArray = (T[]) new Comparable[a.length];
mergeSort(a, tmpArray, 0, a.length-1);
}
/**
* Internal method that makes recursive calls
* @param a an array of Comparable items
* @param tmpArray an array to place the merged result
* @param left the left-most index of the subarray
* @param right the right-most index of the subarray
*/
private static <T extends Comparable<? super T>>
void mergeSort(T[] a, T[] tmpArray, int left, int right){
if(left < right){
int center = (left + right)/2;
mergeSort(a, tmpArray, left, center);
mergeSort(a, tmpArray, center+1, right);
merge(a, tmpArray, left, center+1, right);
}
}
/**
* Internal method that merges two sorted halves of a subarray
* @param a
* @param tmpArray an array to place the merged result
* @param leftPos
* @param rightPos the index of the start of the second half
* @param rightEnd
*/
private static <T extends Comparable<? super T>>
void merge(T[] a, T[] tmpArray, int leftPos, int rightPos, int rightEnd){
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numEles = rightEnd - leftPos + 1;
//Merge
while(leftPos <= leftEnd && rightPos <= rightEnd){
if(a[leftPos].compareTo(a[rightPos])<=0){
tmpArray[tmpPos++] = a[leftPos++];
}else{
tmpArray[tmpPos++] = a[rightPos++];
}
}
//copy rest of first half
while(leftPos <= leftEnd){
tmpArray[tmpPos++] = a[leftPos++];
}
//copy rest of right half
while(rightPos <= rightEnd){
tmpArray[tmpPos++] = a[rightPos++];
}
//copy tmpArray back
for(int i=0; i<numEles; i++, rightEnd--){
a[rightEnd] = tmpArray[rightEnd];
}
}
public static void permute(Integer[] array){
int size = array.length;
for(int index = size-1; index>=0; index--){
//swap(rnd.nextInt(index+1), index);
int rndPos = rnd.nextInt(index+1);
int tmp = array[rndPos];
array[rndPos]= array[index];
array[index] = tmp;
}
}
}The most important thing is to choose proper pivot!!!
QuickSort:
import util.SortUtil;
public class QuickSort {
public static void main(String[] args) {
int[] a = new int[30];
for(int i=0; i<a.length; i++){
a[i] = i;
}
SortUtil.permute(a);
SortUtil.print(a);
quickSort(a);
SortUtil.print(a);
}
public static void quickSort(int[] array){
subQuickSort(array, 0, array.length-1);
}
public static void subQuickSort(int[] array, int start, int end){
if(array==null || (end-start+1)<2){
return;
}
int part = partition(array, start, end);
if(part==start){
subQuickSort(array, part+1, end);
}else if(part==end){
subQuickSort(array, start, part-1);
}else{
subQuickSort(array, start, part-1);
subQuickSort(array, part+1, end);
}
}
private static int partition(int[] array, int start, int end){
int value = array[end];
int index = start-1;
for(int i=start; i<end; i++){
if(array[i]<value){
index++;
if(index != i){
SortUtil.swap(array,index, i);
}
}
}
if((index+1)!=end){
SortUtil.swap(array, index+1, end);
}
return index+1;
}
}
package util;
import java.util.Random;
public class SortUtil {
private static final Random rnd = new Random();
public static
void swap(int[] array, int aPos, int bPos){
int temp = array[aPos];
array[aPos] = array[bPos];
array[bPos] = temp;
}
public static void print(int[] a){
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
System.out.println("\ndone....\n");
}
public static void permute(int[] array){
int size = array.length;
for(int index = size-1; index>=0; index--){
//swap(rnd.nextInt(index+1), index);
int rndPos = rnd.nextInt(index+1);
int tmp = array[rndPos];
array[rndPos]= array[index];
array[index] = tmp;
}
}
}