归并排序算法

      归并排序采用分治的思想，现将数组分裂成更小的单元，将小单元的先进性排序，然后逐次合并，启时间复杂度nlogn，由于需要另加一个辅助数组空间复杂度为O(n）

 1、分裂

/*** 分裂操作*/
void  merge_sort(int* arr,int left, int right){if (left >= right)return;int mid = (left + right) / 2;// 分裂操作merge_sort(arr, left, mid);merge_sort(arr, mid + 1, right);// 合并操作int* temp = (int*) malloc((right-left)* sizeof(int));merge(arr,temp,left,mid,right);free(temp);
}

2、合并 

/*** 合并操作*/void merge(int *arr,int* temp,  int left, int mid, int right){printf("合并索引： left=%d,mid=%d,right=%d\n", left, mid, right);int i = left;int j = mid + 1;int k = 0;// 合并两个有序数组到temp数组中while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 把左边剩余元素填充进temp数组中for (; i <= mid; i++) {temp[k++] = arr[i];}// 把右边剩余元素填充进temp数组中for (; j <= right; j++) {temp[k++] = arr[j];}
// 把temp数组中的元素拷贝回原数组中k = 0;int tempLeft = left;while (tempLeft <= right) {arr[tempLeft++] = temp[k++];}
}

3、测试

    int arr[] = {11,15,3,5,9,80,90,73,50,66};int len = sizeof(arr)/sizeof(arr[0]);merge_sort(arr, 0, len-1);