O(n) 시간으로 배열 정렬
1636 단어 devjournaljavashowdevalgorithms
This method only works with an array with numbers that meets some conditions. As I am not an alien from some other galaxy to prove the laws of mathematics wrong 👽!
전언
우리는 정렬수 그룹의 가장 빠른 알고리즘
O(n*log(n))
이 필요하다는 것을 알고 있다. 이것도 수학적으로 지원되는 것이다.하지만 금요일 저녁에 무엇을 하기 위해서, 왜 내 친구가 그들을 모임에 초대하지 않았는지 지나치게 생각하지 않았다😑, 나 이거 선택했어.
이 알고리즘은 MSB에 의해 숫자가 분산되는 조건에 기초를 두고 있으며 이는 모든 범위의 종류에 하나의 숫자만 있어야 한다는 것을 의미한다.즉
이 범위를 얻기 위해 우리는 원소의 가장 중요한 1위(왼쪽에서 처음 만나는 1)를 볼 것이다.이것은 사실상 그것이 도달할 수 있는 최고치를 설명한다.
우리는
bit manipulations
의 도움말 아래 발견할 수 있으며, 숫자의 MSB 위치에 따라 이 숫자가 수조에 있는 위치 (인덱스) 를 확정할 것이다.No Friends Sort
인코딩 주세요!나는 금요일 저녁에 집에 있었기 때문에, 그것이 분류한 모든 숫자는 매우 멀리 떨어졌다.
public void noFriendSort(){
int[] arr= {45, 1, 5, 150, 100, 3, 24, 11, 460};
int[] newarr=new int[9];
for(int v : arr) {
int temp=v;
int count=0;
for(int i=1; i<=9; i++) {
temp=temp>>1;
if(temp==0)
break;
count++;
}
newarr[count]=v;
}
}
이 코드는 511까지 값을 정렬할 수 있습니다. 비록 int의 범위까지 올라갈 수 있지만, 숫자가 높을수록 코드의 의미는 작아집니다.입력이 더욱 분산되어야 하기 때문이다.그래서 이 코드의 시간 복잡도는O(n*9)
, 즉O(n)
이다.그러나 모든 범위에서 단지 하나의 숫자만을 고려했기 때문에, 지금 나는 나의 금요일 저녁을 성공적으로 낭비했다고 말할 수 있다😶.
그런데 얘가 말한 걸 해냈어
sort array in O(n)
!구글, 전화 기다릴게.
Reference
이 문제에 관하여(O(n) 시간으로 배열 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/prateekbud/sort-array-in-o-n-time-1f8g텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)