c++原地归并排序变形实例源码



c++原地归并排序变形。

题目：给出一个数组，数组中的两半都是已知顺序的，现要实现将这个数组有序化，要求空间复杂度为 O(1)，时间复杂度尽可能的小，编程实现！

 

 

  1. #include <iostream>
  3. using namespace std;
  4. int arr[10] = { 1,3,5,7,9,2,4,6,8,10};
  6. //交换数据
  7. int swaparr(int &a,int &b)
  8. {
  9.     a=a+b;
  10.     b=a-b;
  11.     a=a-b;
  12. }
  13. void reversearr(int a[],int n)  //数组起始地址，数组长度
  14. {
  15.     int i,b;
  16.     for(i=0,b=n-1;i<b;i++,b–)
  17.         swaparr(a[i],a[b]);
  18. }
  19. void leftshift(int a[],int n,int i)//数组以a[0]为起始地址，长度为n，循环左移i位
  20. {
  21.     reversearr(a,i);
  22.     reversearr(a+i,n-i);
  23.     reversearr(a,n);
  24. }
  25. void mergesort(int a[],int n,int s)//数组，总元素，第二段的起始地址
  26. {
  27.     int mid = s;//记录第一段数组的最后一位
  28.     int i,j;//两个移动指针
  29.     i=0;
  30.     j=s;
  31.     while(true)
  32.     {
  33.         while(a[i]<=a[j] && i<mid)
  34.             i++;
  35.         while(a[j]<a[i] && j<n)
  36.             j++;
  37.         if(i >= mid)  //  出口1
  38.             break;
  39.         ///针对 i~j-1 位置的几个数实现循环左移 j-s位
  40.         leftshift(a+i,j-i,mid-i);
  41.         i=j-mid+i;//重新计算出 i 的位置
  42.         //重新计算出mid的位置
  43.         mid=j;
  44.         if(mid>=n)        //出口2
  45.             break;
  46.     }
  47. }
  49. void print()
  50. {
  51.     int i=0;
  52.     for(i=0;i<10;i++)
  53.         cout<<arr[i]<<”  ”;
  54.     cout<<endl;
  55. }
  56. int main()
  57. {
  58.     cout << ”Hello world!” << endl;
  59.     print();
  60.     mergesort(arr,10,5);
  61.     print();
  62.     return 0;
  63. }

 

 


说明：

此处由于要求空间复杂度为O(1)，不能使用另开辟空间的归并排序实现，这里我们需要在原有数组中实现归并排序，原地归并排序；

首先，我们很容易理解到可以使用插入排序的方法将 数组后半段数据通过插入排序使整个数组归并在一起；这个最坏情况下的时间复杂度是O(n2)；

比如 {6，7，8，9，10，1，2，3，4，5}；这个数组将后5个使用插入排序的话时间复杂度为O(n2)；为了解决这种情况，次我们提出了更好的解法：

对于数组arr[10] ，两半的起始指针分别为 i，j；如上程序代码理解~~~