제자리 정렬 inplace MergeSort, 공간 복잡 도 O (1)
//============================================================================
//@lgh
//============================================================================
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
void pr_arr(char* first,char*last)
{
while(first!=last)
{
printf("%c",*first++);
}
}
void swap(char*s1,char*s2)
{
if(*s1!=*s2)
{
char t=*s1;
*s1=*s2;
*s2=t;
}
}
// val
char* lower_bound(char*first,char*last,int val)
{
int len=last-first;
while(len>0)
{
int half=len>>1;
char*mid=first+half;
if(*mid < val)
{
first=mid+1;
len=len-half-1;
}
else
len=half;
}
return first;
}
// val 。
char* upper_bound(char*first,char*last,char val)
{
int len=last-first;
while(len>0)
{
int half=len>>1;
char* mid=first+half;
if(*mid<=val)
{
first=mid+1;
len=len-half-1;
}
else{
len=half;
}
}
return first;
}
// ,
int gcd(int m,int n)
{
while(n!=0)
{
int t=n;
n=m%n;
m=t;
}
return m;
}
//shift , ==mid-begin
void rotate_recyle(char*begin,char*end,char*initial,int shift)
{
char t=*initial;
int len=end-begin;
char *p1=initial; //p1
char *p2=p1+shift; //p2 p1 , p1+shift
while(p2!=initial)
{
*p1=*p2;
p1=p2;
p2=begin+(p2-begin+shift)%len; //p2 ,
}
*p1=t;
}
/* p2=begin+(p2-begin+shift)%len , STL
if(end-p2>shift) p2+=shift;
else p2=begin+(shift-(end-p2));
*/
void rotate(char*begin,char*mid,char*end) //
{
if(begin==mid || mid==end) return;
int n=gcd(mid-begin,end-begin);
while(n--)
{
rotate_recyle(begin,end,begin+n,mid-begin);
}
}
/* : : [13579,2468]
* 1 , 1 5, [2468] 5 6
* :[13,579][24,68] [579] > [24]
* [13,24]<=[579,68], ,[13,24]、[579,68] , OK
*PS: 2 , 。
*/
void inplaceMerge(char*first,char*mid,char*last)
{
int len1=mid-first,len2=last-mid;
if(0==len1 || 0==len2) return ;
if(len1+len2==2)// ,
{
if(*mid<*first) swap(first,mid);
return;
}
char *firstCut, *secondCut;
if(len1>len2) // 1> 2
{
firstCut=first+(len1>>1); // 1
secondCut=lower_bound(mid,last,*firstCut); //
}
else
{
secondCut=mid+(len2>>1); // 2
firstCut=upper_bound(first,mid,*secondCut); //
}
// [firstCut,mid)>[mid,secondCut), , 。
rotate(firstCut,mid,secondCut);
char* newMid=firstCut+(secondCut-mid); //
inplaceMerge(first,firstCut,newMid);
inplaceMerge(newMid,secondCut,last);
}
void inplaceMergeSort(char s[],int len)
{
if(s==NULL || len<=1) return;
inplaceMergeSort(s,len/2);
inplaceMergeSort(s+len/2,len-len/2);
inplaceMerge(s,s+len/2,s+len);
}
int main() {
char s[] ="0124683579";
int len = strlen(s);
inplaceMergeSort(s,len);
printf("%s
", s);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.