O(n) 시간으로 배열 정렬

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)!
구글, 전화 기다릴게.

좋은 웹페이지 즐겨찾기