iOS 算法-归并排序

2015-03-10

哈哈，最近后面下面还有一个基本的算法一一列出来进行讲述。

下面将要讲述归并排序具体实现原理和代码编码。

归并排序

归并排序实现思路

基本思路就是将数组分成二组A，B。如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。再将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。

归并排序的代码实现

void mergeArray(int a[], int first, int mid, int last, int temp[]) {
    int i = first, j = mid + 1;
    int m = mid,   n = last;
    int k = 0;
    
    while (i <= m && j <= n)
    {
        if (a[i] <= a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    
    while (i <= m)
        temp[k++] = a[i++];
    
    while (j <= n)
        temp[k++] = a[j++];
    
    for (i = 0; i < k; i++)
        a[first + i] = temp[i];
}

void mergeLeftRightSort(int a[], int first, int last, int temp[]) {
    if (first < last) {
        int mid = (first + last)/2;
        mergeLeftRightSort(a, first, mid, temp);//左边有序
        mergeLeftRightSort(a, mid + 1, last, temp);//右边有序
        mergeArray(a, first, mid, last, temp);//对左右两边合并
    }
}

void mergeSort(int *p, int length) {
    int *temp = new int[length];//申请 length 空间
    mergeLeftRightSort(p, 0, length-1, temp);//调用归并来进行整合
    delete [] temp;
}