二路归并排序

//二路归并排序，时间复杂度O(nlog2n),空间复杂度O(n),稳定，与序列初始状态无关。 #include<iostream> using namespace std; void merge(int a[], int low, int mid, int high){//low...mid mid+1...high是两个有序序列，merge将两个有序序列合并成一个有序序列 int b[100]; int i, j, k; for (int k = low; k <= high; k++) b[k] = a[k]; for (i = low, j = mid + 1, k = i; i <= mid&&j <= high;){ if (b[i] < b[j]) a[k] = b[i++]; else a[k] = b[j++]; k++; } while (i <= mid) a[k++] = b[i++]; while (j <= high) a[k++] = b[j++]; } void mergeSort(int a[], int low, int high){ if (low >= high) return; int mid = (low + high) / 2; mergeSort(a, low, mid); mergeSort(a, mid + 1, high); merge(a, low, mid, high);//将low到mid,mid到high合并 } int main(){ int a[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 }; mergeSort(a, 0, 8); for (int i = 0; i <= 8; i++) cout << a[i] << endl; }