Skip to content

Instantly share code, notes, and snippets.

@XcqRomance
Created November 13, 2018 14:13
Show Gist options
  • Save XcqRomance/051f918fd5a176572edd7242a702185e to your computer and use it in GitHub Desktop.
Save XcqRomance/051f918fd5a176572edd7242a702185e to your computer and use it in GitHub Desktop.
归并排序 时间复杂度:O(n·logn); 空间复杂度:O(n) 稳定排序 分治法: 1.分解 2.解决 3.合并
// 归并排序 arr带排序的数组 ,p开始index,q为中间切割index,r为数组末尾index
void mergeSortUnit(int *arr,int p,int q, int r) {
int n1 = q-p+1; // 子数组1的个数n1
int n2 = r-q; // 子数组2的个数n2
// 最后一位用来存饭哨岗值正无穷大
int *leftArr = malloc((n1+1) * sizeof(int));
for (int i = 0; i < n1; i++) {
leftArr[i] = arr[p + i];
}
int *rightArr = malloc((n2+1) * sizeof(int));
for (int i = 0; i < n2; i++) {
rightArr[i] = arr[q+i+1];
}
// 最后一位用来存饭哨岗值正无穷大
leftArr[n1] = INT_MAX;
rightArr[n2] = INT_MAX;
int i = 0;
int j = 0;
for (int k = p; k <= r; k++) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i += 1;
} else {
arr[k] = rightArr[j];
j += 1;
}
}
}
void mergeSort(int *arr,int p,int r) {
if (p >= r) { // 数组只有一个元素
return;
}
int q = (p + r) / 2;
mergeSort(arr, p, q);
mergeSort(arr, q+1, r);
mergeSortUnit(arr, p, q, r);
}
// 测试用例
int arr[] = {5,2,7,4,1,2,3,6};
int count = 8;
mergeSort(arr, 0, count-1);
for (int i = 0; i < count; i++) {
NSLog(@"i:%d,arr[i]:%d",i,arr[i]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment