1.归并排序描述:将两个已经排序的的序列合并,采用分治法。
2，原理：将数组不断划分,化成两个或一个或,设置两个指针，分别指向数组左端和右端，比较两端数组元素大小，将小的元素放入合并空间，移动指针，重复步骤。
图解:
#include<iostream> #include<stdio.h> #include<Windows.h> using namespace std; void mergeSort(int arr[], int left, int mid, int right) { int *temp=new int[right-left+1]; int m = right; int i = left; int j =mid+1; int k = 0; while (i <= mid&& j <=m) { temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++]; } while (i <= mid)temp[k++] = arr[i++]; while (j <= m)temp[k++] = arr[j++]; for (int x = 0;x<k;x++)arr[left + x] = temp[x]; delete[]temp; } void Sort(int arr[], int left, int right) {//分治法 if (left >= right)return; //分成两半 int mid = left + (right - left) / 2; //左半边 Sort(arr, left, mid); //右半边 Sort(arr, mid + 1, right); mergeSort(arr, left, mid , right); } int main() { int arr[] = { 13,8,15,9,5,12,11 }; int len = sizeof(arr) / sizeof(int); Sort( arr,0,len-1); for (int i = 0;i < len;i++) { cout << arr[i] << " "; } }运行结果:
