算法怎麼就這麼難---歸並排序和快速排序
最近學了幾天基礎的數據結構的知識，越學越為自己的智商捉急了，再看看好多大牛的一些關於算法的博客，真心覺得差距是這麼這麼大。好了，廢話不多少了，接下來我簡要講述一下兩個基本的排序：歸並排序和快速排序：
歸並排序
歸並排序的原理：歸並排序是將一個集合分成兩部分:part1和part2，分別對part1和part2進行排序(使用遞歸法，直到子集合的大小為1，則停止將集合拆分，此時因為子集合中只有一個元素，所以，這個子集合也就相當於已經拍好了順序)，最後將這兩部分排好順序的集合合並為一。
在編寫代碼的時候有幾個注意點：
如何將集合分成兩部分，各大小都為多少？
集合的第一部分為list.length/2;集合的第二部分為list.length-list.length/2;
集合的遞歸調用什麼時候停止？
當子集合的大小為1時，則停止對集合劃分，故在方法的一開始應該加上一個判斷
If(list.length > 1){
};
代碼實現：
public static void mergeSort(int[] list){
if(list.length > 1){
int[] half1 = new int[list.length/2];
int[] half2 = new int[list.length - list.length/2];
System.arraycopy(list, 0, half1, 0, half1.length); //將集合的前半部分復制到half1中
mergeSort(half1);
System.arraycopy(list, list.length/2, half2, 0, half2.length); //將集合的後半部分復制到half2中
mergeSort(half2);
int[] temp = merge(half1,half2); //將兩個集合合並
System.arraycopy(temp, 0, list, 0, temp.length);
}
}
上段代碼的merge方法的作用是將兩個集合合並為一個並返回。
代碼實現：
private static int[] merge(int[] list1, int[] list2){
int[] temp = new int[list1.length + list2.length];
int currentPosition1 = 0; //遍歷list1時使用的下標變量
int currentPosition2 = 0; //遍歷list2時使用的下標變量
int currentPositionTemp = 0; //合並兩個list時使用的下標變量
//將兩個集合中的元素copy到臨時變量中
while(currentPosition1 < list1.length && currentPosition2 < list2.length){ if(list1[currentPosition1] < list2[currentPosition2]){ //將小的元素放到前面。
temp[currentPositionTemp++] = list1[currentPosition1++];
}else
{
temp[currentPositionTemp++] = list2[currentPosition2++];
}
}
//運行到此處時，list1和list2中的至少其中一個list已經全部復制到臨時集合中，但有可能list1中元素的數量小於list2中元素
//的數量，因此，需要將list1或者list2中的剩余的數據復制到臨時集合中。
while(currentPosition1 < list1.length){
temp[currentPositionTemp++] = list1[currentPosition1++];
}
while(currentPosition2 < list2.length){
temp[currentPositionTemp++] = list2[currentPosition2++];
}
return temp;
}
測試代碼：
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list = {1,29,1,2,90,1,0};
mergeSort(list);
for(int temp : list){
System.out.print(temp + " ");
}
System.out.println();
}
運行結果：
快速排序
快速排序的原理：快速排序在數組中選擇一個稱為主元(pivot)的元素將數組分成兩個部分，使得第一部分的所有元素小於或等於主元（pivot），而第二部分的所有元素均大於主元（pivot）。然後對第一部分遞歸得應用快速排序算法，然後對第二部分遞歸得應用快速排序算法。
Pivot的英文意思為中心點，所以，快速排序可以理解為找中心點，然後根據中心點，將數組分成兩部分，一部分小於或等於中心點，另一部分大於中心點，然後按照此方法對兩個部分分別執行，最後就將數組排好了順序。
為了簡單起見，接下來我的代碼實現中，將數組的第一個元素作為中心點（pivot）。
代碼如下：
說明：此段代碼的功能是根據集合的第一個元素作為中心點(pivot)將集合分成兩個部分，返回中間點pivot的下標
private static int partition(int[] list, int first, int last){
//參數first和last用於指定，將集合的哪一段按照pivot分成兩部分。
int pivot = list[first]; //取第一個元素作為集合的中心點(pivot)
int low = first + 1;
int high = last;
while(high > low){
//找到從前向後數第一個大於pivot的元素，然後找到從後向前數第一個小於pivot的元素，將他們兩個互換
while(low <= high && list[low] <= pivot)
low++;
while(low <= high && list[high] > pivot){
high--;
}
if(high > low){
int temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}
//經過上面一個循環之後，下標小於low的元素均小於pivot，小標大於high的元素均大於pivot
//將high的下標從後向前遍歷，直到找到當前下標的值小於等於pivot為止
while(high > first && list[high] >= pivot){
high--;
}
if(pivot > list[high]){//if成立，表示pivot的值不是集合中最小的值，此時將pivot的值放到list[high]的位置上
list[first] = list[high];
list[high] = pivot;
return high;
}else{ //此種情況表示，pivot為集合中最小的元素，因此，pivot值的小標也就是first
return first;
}
}
quicksort()代碼如下：
private static void quickSort(int[] list, int first, int last){
if(last > first){
int pivotIndex = partition(list,first,last);
quickSort(list,first,pivotIndex -1);
quickSort(list,pivotIndex+1,last);
}
}
此時，定義一個只有一個集合作為參數的公共方法：
public static void quickSort(int[] list){
quickSort(list,0,list.length-1);
}
測試代碼：
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list = {12,3,2,1,5,2};
quickSort(list);
for(int temp : list){
System.out.print(temp + " ");
}
System.out.println();
}
