데이터 구조 - 알고리즘 (017) (n 개 수 를 어떻게 정렬 하 는 지, 시간 복잡 도 O (n), 공간 복잡 도 O (1) 를 요구 합 니 다.
제목:
n 개 수 를 어떻게 정렬 하 는 지, 시간 복잡 도 O (n), 공간 복잡 도 O (1) 를 요구 합 니 다.
제목 분석:
얼핏 보면 완성 할 수 없다.시간 복잡 도 는 n 이 고 모든 정렬 법 을 보면 이 단계 에 이 르 지 못 했다.
2. 유한 한 개수 배열 을 대상 으로 한다 면 표기 법 을 사용 하거나 hash 사상의 방법 이 라 고 할 수 있 으 며 큰 배열 hash [65536] 를 신청 할 수 있 습 니 다.
그리고 해당 위 치 를 표시 하고 중복 되 는 숫자 는 중첩 합 니 다.
예 를 들 면:
0----->hash[0]++;
5----->hash[5]++;
100--->hash[100]++;
알고리즘 구현:
#include <stdio.h>
static int hash[65536] = {0};
void hash_sort(int *array, int size)
{
int i=0;
for(; i<size; i++)
hash[array[i]]++;
}
int main(int argc, char *argv[])
{
int a[] = {1, 4, 1, 2, 5, 13, 4, 6, 8, 1000, 999, 9,};
//sort
int size = sizeof(a)/sizeof(int);
hash_sort(&a, size);
//print the array
int i = 0;
for(; i<65536 && size--; i++)
{
while(hash[i] != 0)
{
printf(" %d", i);
hash[i]--;
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
