이 O (n) 정렬 방법이 이미 있습니까?

아이디어는 모든 값을 최종 배열의 부모 인덱스로 설정 한 다음 모든 null 값을 제거하는 것입니다. 그것은 단지 독특한 아닌 0 값을 정렬, 참고로이 O (n) 정렬 방법이 이미 있습니까?

int x[] = {9,3,4,2,1,12,5}; 
sortList(x) 

public static int[] sortList(int[] x){ 
    int[] y = new int[15]; 
    for (int i=0; i < x.length; i++){ 
     int value = x[i]; 
     y[value] = value; 
    } 
    return removeNull(y); 
} 
public static int[] removeNull(int[] array) { 
    return Arrays.stream(array).filter(i -> i != 0).toArray(); 
}

: 다음은 몇 가지 간단한 구현입니다. 배열을 통과 할 때 메소드가 수행하는 작업입니다.

배열 -> 9,3,4,2,1,5는 -> 0,1,2,3,4,5로 변환됩니다. 0,0,0,9,0,0 그리고 나서 -> 1,2,3,4,5,9 만약이 솔루션이 배열을 3 회 반복하고 y 크기를 저장 장치로 사용합니다. 이 정렬 방법이 이미 존재합니까?

출처

2017-12-21 joshLor

12 세는 어떻게 되었습니까? 한 번만 원래 배열을 반복하는 것처럼 보입니다. 코드가 x를 통해 초기 패스를 수행하여 y []의 범위와 크기를 설정하는 데 사용할 수있는 최소값과 최대 값을 결정합니다. 자바 태그를 추가하는 것이 좋습니다. 그 이유는 코드가 기반으로하는 것으로 보이기 때문입니다. 이 메소드는 고유 한 값 (x []의 최소값에서 최대 값까지의 범위에서 0 또는 1 인스턴스 값)으로 작업하는 것으로 제한된다는 점을 제외하고는 계산 유형과 유사합니다. – rcgldr

@rcgldr 예, 이미 최소값과 최대 값을 처리했지만 알고리즘을 조금 더 복잡하게 만들었 기 때문에 게시하지 않았습니다. 이게 효과가 없다고 말하는거야? 모든 값이 고유하다면 정렬을 세는 것보다 많은 정렬 문제에 대해보다 효율적인 해결책이되지 않겠는가? – joshLor

@ joshLor : 한 값이 4.3872 * 10^342이거나 값이 문자열 인 경우 어떻게합니까? 이것은 이름 정렬 알고리즘을받을 가치가있는 것으로 제한되어 있습니다. – Curd

이 알고리즘은 Counting Sort으로 알려져 있습니다. 여기

는 위키 백과의 설명입니다 :

컴퓨터 과학에서

정렬을 계산하는 작은 정수 키에 따라 개체의 컬렉션을 정렬하는 알고리즘이다; 즉 정수 정렬 알고리즘입니다. 각각의 구별 된 키 값을 가진 오브젝트의 수를 계산하고, 그 수에 대한 산술을 사용하여 출력 순서의 각 키 값의 위치를 판별하여 작동합니다. 실행 시간은 항목 수와 최대 및 최소 키 값의 차이에서 선형이므로 키의 변형이 항목 수보다 현저하게 크지 않은 상황에서 직접 사용하는 경우에만 적합합니다.

알고리즘에서 중복 된 내용은 무시됩니다. 계수 형은 각 키의 항목 수를 계산하여이 문제에 대한 해결책으로 이름을 얻습니다. 이 알고리즘은 실제로 선형이지만, 시간과 공간 모두에서 높은 상수 요소는 실제로 거의 사용되지 않습니다.

출처

2017-12-22 01:12:37

이 O (n) 정렬 방법이 이미 있습니까?

답변

관련 문제