흔들기 정렬!?
내 모든 독자들은 오늘의 문제의 이름이 매우 재미 있다는 것을 알았을 것입니다. 그러나 다양한 범위의 개념에 대한 우리의 이해를 테스트하는 것은 매우 현명한 문제입니다.
더 이상 혼동하지 않고 문제로 바로 넘어 갑시다.
차례
예
당신은 배열이 있습니다
입력 : [1,5,1,6,4]
예상 출력 : [1,6,4,1,5]
어떻게?
흔들림도 정렬 :
배열의 요소는 다음과 같이 정렬되어야합니다. arr[0]<arr[1]>arr[2]<arr[3] 등등 흔들림 정렬에서.
접근
가장 쉬운 방법으로 갈 것입니다. 다음 예를 고려하여
배열 : [1,5,1,1,6,4]
해당 배열의 복사본을 만들어 정렬하겠습니다.
파란색 : 원래 배열 빨간색 : 정렬 됨 배열 복사
어레이 길이 : 6
복사 배열의 작은 요소를 원래 배열에 배치하겠습니다.
작은 요소를 복사 한 후 원래 배열
지금. 남은 부분에 더 큰 요소를 배치하겠습니다.
짜잔. 배열이 흔들려 정렬되었습니다!
홀수 요소를 포함하는 배열에 대해 패스를 약간 변경합니다.
살펴 보겠습니다.
두 번째 마지막 요소 대신 마지막 요소에서 시작합니다.
첫 번째 패스 후
이제 더 큰 요소를
A 비슷한 문제 우리는 좋은 이해를 얻기 위해 우리와 함께 확인할 수 있습니다.
이제 우리는 그것을 이해했습니다. 코드를 살펴 보자
흔들기 정렬을위한 Java 코드
class Solution
{
int index=0;
public void assemble(int[] nums,int copy[],int start)
{
//The assemble function
for(int i=start;i>-1;i=i-2)
{
nums[i]=copy[index];
index++;
}
}
public void wiggleSort(int[] nums)
{
int copy[]=new int[nums.length];
for(int i=0;i<nums.length;i++)
copy[i]=nums[i];
Arrays.sort(copy);
if(nums.length%2==0)
{
assemble(nums,copy,nums.length-2);
assemble(nums,copy,nums.length-1);
}
else
{
assemble(nums,copy,nums.length-1);
assemble(nums,copy,nums.length-2);
}
}
}
흔들기 정렬을위한 C ++ 코드
class Solution
{
public:
int index=0;
public:
void assemble(vector<int>& nums,vector<int>& copy,int start)
{
int i=0;
for(i=start;i>-1;i=i-2)
{
nums[i]=copy[index];
index++;
}
}
public:
void wiggleSort(vector<int>& nums)
{
vector<int>copy(nums);
sort(copy.begin(), copy.end());
if(nums.size()%2==0)
{
assemble(nums,copy,nums.size()-2);
assemble(nums,copy,nums.size()-1);
}
else
{
assemble(nums,copy,nums.size()-1);
assemble(nums,copy,nums.size()-2);
}
}
};
흔들기 정렬을위한 복잡성 분석
위 문제에 대한 시간 복잡성 = O (n log n)
위의 방법으로 Wiggle 정렬을위한 공간 복잡성 = O (n)
어떻게?
- 사용 된 정렬 작업은 시간 복잡도가 O (n logn) 인 내장 병합 정렬입니다.
- 어셈블 함수에 대한 각 호출에서
- 우리는 대체 요소를 살펴보고 그에 따라 사본에서 원래 배열로 배치합니다.
- 따라서 요소가 모두 제자리에 배치 될 때까지 배열의 모든 요소를 살펴 봅니다.
- 배열로 이동하면 시간 복잡도가 O (n)
- 그러나이 경우 정렬 작업은 시간 복잡도를 O (n logn)로 가져 오는 더 많은 비용이 드는 것으로 나타났습니다.
- 요소로 복사 배열을 만들었을 때 공간 복잡성은 O (n), 즉 선형
