詳解分治算法

  分治算法，就是利用遞歸的思想，分而治之。核心思想是把一個問題，分解成n/2個子問題來解決。其中，歸并排序就是典型的運用。

   例如：我們把數組1,3,2,4,6,5,7,8,0,9 這十個數，用分治法做排序。

   如何利用分治思想，做排序呢。通過我們的觀察，我們發現，能對10個數排序，就能對5個數排序，也能對2 個數排序，極端一點，我們也可以對一個數進行排序。也就是說，對十個數進行排序，也了一個遞歸的問題。我們再想想，對10個數排序，我們分解成對2組5位數排序。然後再把已經排好序的2組數，做合并。這樣，我們把排序的問題就變成了先做分解，再做合并。

   第一步，我們先寫兩個數組合并的算法

  第二步，我們再寫把一個數組，用遞歸的思想分解的算法

   兩個數組合并的算法

我們把數組array1和array2合并成新的數組new_array

基于思路就是，有兩個指針指向兩個數組中的一個元素，然後比較大小 ，把小的那個元素放入新的數組中，移動指向較小的元素的指針。

void sort_array(int* array1, int size1, int* array2, int size2, int * new_array)
{
  int i = 0;
  int j = 0;
  int new = 0;
  int* new_array = (int*)malloc(size1 + size2);
  while (i < size1 && j < size2)
  {
    if (* (array1 + i ) <= * (array2 + j))
    {
      *(new_array + new) = *(array1 + i);
     ++new;
     ++i;
    } else {
      *(new_array + new) = *(array2 + j);
     ++new;
     ++j;

    }
  }
  if (i == size1) {
    while ( j < size2)
    {
      *(new_array + new) = *(array2 + j);
      ++new;
      ++j;
    }
  } else if (j == size2) {
    while ( i < size1)
    {
      *(new_array + new) = *(array1 + i);
      ++new;
      ++i;
    }

  }
  return new_array;
}
           

二 用遞歸的思想，把一個數組分解成n個

我們考慮一個極端的例子，把10個數折半分解，最終分解成10個數組，這10個數組隻有可憐的一個元素，但是，這一個元素，我們可以了解成它已經是有序的了。我們把10個有序的數組，用之前的合并算法，合成一個有序的數組。這樣就完成了我們的排序了。 

int* merge_sort(int* array, int first, int last)
{
  if (first < last)
  {
    int mid = (first + last)/2;
    int* result = (int*)malloc(last - first +1);
    int* left = merge_sort(array, first, mid); //left
    int* right = merge_sort(array, mid + 1, last); //right
    sort_array(left , mid - first + 1, right , last - mid, result);
    return result;
  } else {
    return array+first;
  }
}
           

下面給出main()方法的部分：

int main(char* argc, int argv) {

  int c[10] = {4,3,6,2,1,8,9,7,0,5};
  int* result = merge_sort(c, 0, 9);
  int p;
  for (p=0; p < 10; p++)
  {
    printf("%d\n", *(result + p));
  }
  return 0;
}