做城市分类信息网站好做吗/图片识别 在线识图

归并排序还是比較好理解的。

归并的含义是将两个或者两个以上的有序表组合成一个新的有序表。

详细方式是：如果初始序列含有n个记录。则能够看成是n个有序的子序列，每一个子序列的长度为1，然后两两归并，得到若干长度为2或者1的有序子序列，再两两归并。。。直至得到一个长度为n的有序序列为止，这就称之为2路归并排序。

复杂度：归并排序的最好最坏和平均时间复杂度都是O（n*logn），可是须要额外的长度为n的辅助数组。另外它是几个高效排序算法（高速排序、堆排序、希尔排序）中唯一稳定的排序方法。

实现：

/*
归并排序
by Rowandjj
2014/7/24
*/
#include<iostream>
using namespace std;
#define MAX 100
void Merge(int *list1,int *list2,int list1_size,int list2_size)
{int temp[MAX];//辅助数组int i,j,k;i = j = k = 0;//合并两个有序数组的操作，因为这里使用了辅助数组，故而能够从前向后复制//在之前的一篇文章中介绍合并有序数组採用的是从后向前复制。那是因为不使用辅助空间，并且数组1足够大while(i < list1_size && j < list2_size){if(list1[i] < list2[j]){temp[k++] = list1[i++];}else{temp[k++] = list2[j++];}}while(i < list1_size){temp[k++] = list1[i++];}while(j < list2_size){temp[k++] = list2[j++];}//将已经排好序的辅助数组元素拷贝到源数组上for(i = 0; i < list1_size+list2_size; i++){list1[i] = temp[i];}
}
void MergeSort(int arr[],int len)
{if(arr == NULL || len <= 1){return;}int *list1 = arr;int list1_size = len/2;int *list2 = arr+list1_size;int list2_size = len - list1_size;MergeSort(list1,list1_size);//对左側递归进行归并操作MergeSort(list2,list2_size);//对右側递归进行归并操作Merge(list1,list2,list1_size,list2_size);
}
int main()
{int arr[] = {9,8,5,3,7,2,1,0,4};MergeSort(arr,9);for(int i = 0; i < 9; i++){cout<<arr[i]<<" ";}cout<<endl;return 0;
}

版权声明：本文博主原创文章，博客，未经同意不得转载。