并归排序

zzy198772

package huawei.com;

/**
* @author zKF41185
*
*/
public class MergeSort {

/**
* @param args
*/
public static void main(String[] args) {

String a = "abc";
String b = "abc";
String ab = "ab";
String c = ab + "c";
String d = "ab"+"c";

System.out.println( a==b );
System.out.println( a==c );
System.out.println( a==d );



int[] arr = new int[1000000];
for (int i = 0; i < 1000000; i++) {
if(i>20000) {
arr[i] = i-((int)(Math.random()*1000));
}else{
arr[i] = i;
}
}

int[] arr2 = new int[1000000];
for (int i = 0; i < 1000000; i++) {
if(i>20000) {
arr2[i] = i-((int)(Math.random()*1000));
}else{
arr2[i] = i;
}
}

//long mergeSortTime3 = System.currentTimeMillis();
//bubbleSort(arr2);
//long mergeSortTime4 = System.currentTimeMillis();
//System.out.print("冒泡排序==");
//System.out.println(mergeSortTime4-mergeSortTime3);

long mergeSortTime1 = System.currentTimeMillis();
mergeSort(arr);
long mergeSortTime2 = System.currentTimeMillis();
System.out.print("归并排序==");
System.out.println(mergeSortTime2-mergeSortTime1);

System.out.println(flagCount);
}

private static int[] merge(int[] list1, int[] list2) {
int[] temp = new int[list1.length + list2.length];
int current1 = 0;
int current2 = 0;
int current3 = 0;
while (current1 < list1.length && current2 < list2.length) {
if (list1[current1] < list2[current2]) {
temp[current3++] = list1[current1++];
} else {
temp[current3++] = list2[current2++];
}
}
while (current1 < list1.length) {
temp[current3++] = list1[current1++];
}
while (current2 < list2.length) {
temp[current3++] = list2[current2++];
}
return temp;
}

static int flagCount = 1;

public static void mergeSort(int[] list) {
flagCount ++;
if (list.length > 1) {

int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);

int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);

int[] temp = merge(firstHalf, secondHalf);
System.arraycopy(temp, 0, list, 0, temp.length);
}
}

public static void bubbleSort(int[] list) {
boolean needNextPass = true;
for (int k = 1; k < list.length && needNextPass; k++) {
needNextPass = false;
for (int i = 0; i < list.length - k; i++) {
if (list[i] > list[i + 1]) {
int temp = list[i];
list[i] = list[i + 1];
list[i + 1] = temp;
needNextPass = true;
}
}
}
}
}