You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
21 lines
586 B
21 lines
586 B
// 归并排序
|
|
void merge_sort(int q[], int l, int r)
|
|
{
|
|
if (l >= r) return;
|
|
|
|
int mid = l + r >> 1;
|
|
merge_sort(q, l, mid);
|
|
merge_sort(q, mid + 1, r);
|
|
|
|
int k = 0, i = l, j = mid + 1;
|
|
while (i <= mid && j <= r)
|
|
if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
|
|
else tmp[k ++ ] = q[j ++ ];
|
|
|
|
while (i <= mid) tmp[k ++ ] = q[i ++ ];
|
|
while (j <= r) tmp[k ++ ] = q[j ++ ];
|
|
|
|
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
|
|
}
|
|
//复杂度说明： 在各种情况下归并排序时间复杂度均为 o(nlogn).
|