归并排序实现

算法原理:归并排序的思想是分治,将一个带排序的数组分成两个较小的数组,然后分别进行排序,组后将两个排好序 的较小的数组合并起来,就得到了原来数组的排序后的结果。应该注意的是这种将两个排好序的数组合并有一个较好的算法,时间复杂度是O(n1+n2)的。 n1、n2分别是两个小数组的长度。
算法代码:

#include <iostream>

 using namespace std;

 void merge_sort(int *arr,int start,int end,int *temp)
 {
     if(end > start+1)
     {
         int mid = start + (end - start) / 2;
         merge_sort(arr,start,mid,temp);
         merge_sort(arr,mid,end,temp);
         int i = start , j = mid , k = start;
         while(i < mid || j < end)
         {
             if(j >= end || (i < mid && arr[i] <= arr[j]))
             {
                 temp[k++] = arr[i++];
             }
             else
             {
                 temp[k++] = arr[j++];
             }
         }
         for(i = start ; i < end ; ++i)
         {
             arr[i] = temp[i];
         }
     }
 }


 int main()
 {
     int temp[8];
     int arr[]  = {2,1,4,3,8,7,5,6};
     merge_sort(arr,0,8,temp);
     for(int i = 0 ; i < 8 ; ++i)
     {
         cout<<arr[i]<<" ";
     }
     cout<<endl;
     return 0;
 }

小结:归并排序时稳定的排序,但是不属于原地排序,因为用了额外的O(n)的空间,时间复杂度降到了O(n*log n),并且对任意的数组进行排序时间复杂度都能控制在O(n*logn)。

 

上一篇:PDFCrack 0.11 Windows 版本发布


下一篇:算法笔记--归并排序