0과 1을 포함하는 바이너리 값의 목록이 다음과 같이 000111010110 인 경우이를 다음과 같이 정렬하고 싶습니다. 000000111111 이것을 알고 싶다면 이것을 가장 효율적으로 수행 할 수있는 방법은 무엇입니까? 목록 크기? 지금은 처음부터 끝까지리스트를 횡단하면서 0의 수를 세는 카운터가 하나 있다고 생각합니다. 다음 numberOfZeros에 의해 listSize 나누면 numberOfOnes 얻을. 그렇다면 0으로 시작하는리스트를 재정렬하는 대신에 새로운리스트를 만들 것입니다. 이것이 가장 효율적인 방법이라고 생각하십니까?2 진리스트 정렬하기
귀하의 알고리즘은 가장 기본적인 bucket sort 알고리즘의 기본 버전 (counting sort 구현)을 구현합니다. 범위를 알고 있고 (상대적으로) 작은 경우 숫자를 정렬하는 가장 빠른 방법입니다. 0과 1이 모두 있기 때문에 버킷 정렬에있는 카운터 배열이 필요하지 않습니다. 단일 카운터이면 충분합니다.
숫자 값이있는 경우 bitscan (x86 어셈블리의 BSF) 어셈블리 명령어를 사용하여 비트 수를 계산할 수 있습니다. "정렬 된"값을 만들려면 n + 1 비트를 설정 한 다음 1을 뺍니다. 그러면 모든 비트가 n + 1 비트의 오른쪽에 설정됩니다.
BSF는 첫 번째 비트 세트의 색인을 찾습니다. 그것은 설정된 비트 수를 세지 않습니다. –
두 번째 제안이 좋습니다. –
나는 POPCNT를 의미한다고 생각합니다. – hammar
버킷 정렬은 마치 정렬 알고리즘입니다.
그런 조작이 필요 없다고 생각합니다. 우리는 N * logN보다 빠른 정렬 알고리즘이 없다는 것을 알고 있습니다. 그래서 기본적으로 잘못되었습니다.
그리고 모두 당신이해야 할 일은 처음부터 말한 것입니다. 그냥 목록을 탐색하여 0 또는 1을 계산하면 O (n) 복잡성이 생깁니다. 다음과 같이 새 배열을 만듭니다. 카운트 된 0은 처음에 One '이옵니다. 그러면 N (0 + N)의 복잡성이 생겨서 O (n)의 복잡성을 갖게됩니다.
그리고 당신은 두 values.So 빠른 정렬 또는 컴퓨터 워드의 비트를 사용하는 경우에는 faster.There 더 빠른 NLog (N)
보다 정렬되어이 작업을 수행 할 수있는 다른 종류도이 때문 이잖아, http://graphics.stanford.edu/~seander/bithacks.html의 계산 비트 설정 섹션을 참조하십시오. –