递归实现归并排序思想
使用递归的方法来分元素使用临时数组来保存排好序的元素把临时数组中的元素拷贝给原数组
void mergeAdd(int arr[], int left, int mid, int right, int *temp){实现“治”int i = left;int j = mid + 1;int k = left;//临时下标while (i <= mid&&j <= right){if (arr[i] < arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}while (i <= mid){temp[k++] = arr[i++];}while (j <= right){temp[k++] = arr[j++];}//把temp中的内容拷给arr数组中//进行归并的时候，处理的区间是arr[left,right),对应的会把//这部分区间的数组填到tmp[left,right)区间上memcpy(arr + left, temp + left, sizeof(int)*(right - left+1));}void mergeSort(int arr[],int left,int right,int *temp){//实现“分”int mid = 0;if (left < right){mid = left + (right - left) / 2;mergeSort(arr, left, mid, temp);mergeSort(arr, mid + 1, right, temp);mergeAdd(arr, left, mid, right, temp);}}
测试代码
int main(){int arr[] = { 8,4,5,7,1,3,6,2};int len = sizeof(arr)/sizeof(arr[0]);int *temp = （int*)malloc(sizeof(int)*len);mergeSort(arr, 0, len - 1, temp);free(temp);for (int i = 0; i < len; i++){printf("%d ", arr[i]);}system("pause");return 0;}
递归归并排序性质
时间复杂度：O(NlogN)
空间复杂度：O（N）
稳定性：稳定排序
非递归实现归并排序
void mergeAdd1(int arr[], int left, int mid, int right, int *tmp){int i = left;int j = mid + 1;int k = left;//临时下标while (i <= mid&&j <= right){if (arr[i] < arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}while (i <= mid){temp[k++] = arr[i++];}while (j <= right){temp[k++] = arr[j++];}//把temp中的内容拷给arr数组中//进行归并的时候，处理的区间是arr[left,right),对应的会把//这部分区间的数组填到tmp[left,right)区间上memcpy(arr + left, temp + left, sizeof(int)*(right - left + 1));}void mergeSort2(int arr[], int len，int* tmp){if (len <= 1){return;}//定义一个步长gap，初始值为1，相当于每次只合并两个长度为1的元素int gap = 1;for (; gap <= len; gap *= 2){int i = 0;for (; i <= len; i += 2 * gap){int beg = i;int mid = (gap - 1) + i;if (mid >= len){mid = len;}int end = mid + gap;if (end >= len){end = len;}mergeAdd1(arr, beg, mid, end, tmp);}}}
测试代码同上。
