R15 - 데이터 구조

데이터 구조
1. 해시, 해시, 모든 만족 key: value 는 해시, 추상 적,
예 를 들 어 배열, 대상 은 모두 하 쉬 a = [7,3,2,,8,4,7,73,1] 가 거품 이 나 거나 순 서 를 선택 하면 적어도 한 번 은 비교 하고 정렬 하 는 시간 복잡 도의 한 계 를 비교 하 며 가장 빠 르 고 빠 르 면 nlogn 이 필요 하 다.

a = {
  "0": 0,
  "1": 6,
  "2": 2,
  "6": 8,
  "9": 3,
  "22": 76,
  "66": 23,
  "length": 66   //   length          +1,
                 //            ？
}

2. 계수 정렬

a = [7,1,2,6,6,3,5,9,0]  //  

var index;  //  
var hash=[]  //  hash

for(var i=0; i

복잡 도: O (n + max), 빠 른 줄 보다 빠 른 단점: hash 를 계산 하 는 도구 로 소수 와 음수 정렬 이 불가능 해 야 합 니 다 (0 부터)
3. 통 정렬, 계수 정렬 과 유사
그런데 계산 순 서 는 한 통 에 숫자 를 넣 는 거 예요.

hash:{
  "1": 1,
  "2": 1,
  "3": 1,
  "4": 1,
  "7": 1,
  "76": 1
}
                   
hash:{
  "1": [0,6,2,8,3],  // 10     
  "2": [],         // 20  
  "3": [],
  "4": [],
  "5": [],
  "6": [],
  "7": [],
  "8": [76]  // 80  
}

통 순 서 는 2 차 순 서 를 해 야 한다. 장점 은 공간 을 단축 시 키 는 것 이다. 8 개의 통 만 사 용 했 고 계산 순 서 는 76 개의 통 을 사용 했다. 공간 을 낭비 하 는 나 쁜 점 은 시간 을 낭비 하 는 것 이다. 계산 순 서 는 시간 순 서 를 절약 했다. 즉, 공간 을 낭비 하거나 시간 을 낭비 하거나 언제 통 으로 순 서 를 매 길 것 인가? 예 를 들 어 수 능 점수 순 서 는 100 점 이하 의 통 이다. 700 점 이하 의 통 이다.이렇게 7 개의 통 만 사용 하고, 계수 순 서 는 700 개의 통 이 필요 하 며, 매 점 마다 하나의 통 으로 순 서 를 매 기 는 것 은 계수 정렬 의 업그레이드 이다.
4. 기수 정렬
엄 청 큰 숫자 에 적응 할 수 있어 요. 구체 적 으로 보면...https://visualgo.net/bn/sorting
계수 정렬: 통 을 낭비 합 니 다. 배열 하 는 횟수 는 한 번 에 들 어가 고 한 번 에 정렬 합 니 다. 통 의 개 수 는 당신 이 정 합 니 다. 몇 통 을 원 하면 몇 통 이 고 한 번 에 들 어가 서 한 번 을 내야 합 니 다. 그러나 다시 정렬 해 야 합 니 다. 어 지 러 우 므 로 그 다음 에 어떻게 정렬 하 는 지 상황 기수 정렬 을 봅 니 다. 통 의 개 수 는 고정 적 이 고 10 개 (0 ~ 9) 만 있 습 니 다. 배열 하 는 횟수 는 수치의 자릿수 에 의 해 정 합 니 다.네 자리 수 는 네 번 해 야 돼 요.
5. 대기 열 queue (추상 적 인 개념)
먼저 나 가 (없어, 이것 이 바로 대열) 현실 생활 에서 의 예: 줄 을 서 는 것 은 배열 로 이 루어 질 수 있다. 예 를 들 어

var q=[];
q.push("alice")  //   q["alice"]
q.push("ben")    // q["alice","ben"]
q.push("jack")   // q["alice","ben","jack"]
//   
q.shift()     //alice    q["ben","jack"]
q.shift()     //ben      q["jack"]
q.shift()     //jack     q[]

무슨 소 용이 있 습 니까?만약 당신 이 12306 의 줄 서기 시스템 을 만 들 려 고 한다 면, 대열 을 이용 하여 먼저 표를 사 는 사람 이 먼저 표를 냅 니 다.
6. 창고 스 택
먼저 들 어가 서 나 와 도 배열 로 이 루어 질 수 있어 요.

var stack = []
stack.push(" 1 ")   // stack[" 1 "]
stack.push(" 2 ")   // stack[" 1 "," 2 "]
stack.push(" 3 ")   // stack[" 1 "," 2 "," 3 "]
stack.pop()   //  3  stack[" 1 "," 2 "]
stack.pop()   //  2  stack[" 1 "]
stack.pop()   //  3  stack[]

7. 링크 목록
배열 은 중간 항목 을 직접 삭제 할 수 없습니다. 연결 표 는 해시 (js 에서 대상 으로 해시 표시) 로 링크 를 실현 할 수 있 습 니 다.

//     ，       ，        
var a = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: undefined
    }
  }
}
a.value  //1
a.next.value  // 2
a.next.next.value  //3
//   a.next       a.next.next
//           a.next,    2    
a.next =  a.next.next
a.next  // 3
a.next.next  // undefiend

링크 조회 가 느 립 니 다. 예 를 들 어 위의 a. next. next 는 많 으 면 필요 합 니 다. next 가 멈 추 지 않 고 배열 이 빠 릅 니 다. 예 를 들 어 n 번 째 를 찾 으 려 면 a [n - 1] 만 있 으 면 됩 니 다. 배열 조회 가 빠 릅 니 다. 링크 삭제 가 빠 르 면 링크 는 2 개의 개념 head 와 node 가 있 습 니 다. 예 를 들 어 위의 예 를 들 어 원래 의 예 입 니 다.

var a3={
  value: 3,
  next: undefined
}
var a2={
  value: 2,
  next: a3
}
var a = {
  value: 1,
  next: a2
}

a. 바로 이 링크 의 표 두, 즉 head 입 니 다. 표 두 를 찾 으 면 뒤의 모든 항목 을 찾 을 수 있 습 니 다. 다른 것 은 노드 이 고 표 두 도 노드 입 니 다. node
8. 트 리 트 리 (링크 의 업그레이드, 전체 화살 표 는 링크 입 니 다. 중간 에 갈 라 지면 트 리 입 니 다)
당신 이 등급 이 있 으 면 나 무 를 사용 해 야 합 니 다. 예 를 들 어 우리 가 쓴 홈 페이지 는 나무 dom 도 나무 개념 입 니 다. - 층수, 예 를 들 어 html 는 1 층 이 고 head 와 body 는 2 층 - 깊이 입 니 다. 모두 몇 층 - 노드 갯 수 입 니까? 모든 hash 는 하나의 노드 입 니 다. 예 를 들 어 위 에 html 는 하나 이 고 head 는 하나 입 니 다. body 는 아들 이 없 는 노드 를 잎 노드 라 고 합 니 다.잎 에 천 은 다시 잎 이 자란 다.
이 진 트 리 는 매번 최대 두 개의 포크 로 나 누 어 하나의 포크 로 나 눌 수 있다.

                     html{
                       tag:html,
                       children:[head,body]
                     }
head{                                    body{
  tag: head,                              tag: body,
  children: [meta1, meta2]                children: [h1,h2]
}                                        }
meta1{         meta2{                  h1{            
  tag:meta1     tag:meta2               tag:h1         
}              }                       }              
    
        ，      ，          ，      
                     html{
                       tag:html,
                       children:[head,body]
                     }
head{                                    body{
  tag: head,                              tag: body,
  children: [meta1, meta2]                children: [h1,h2]
}                                        }
meta1{         meta2{                  h1{             h2{
  tag:meta1     tag:meta2               tag:h1         tag:h2
}              }                       }               }
   
  i                                  
0           1       2^0            1(2^1-1)        0
1           2       2^1            3(2^2-1)        1~2
2           4       2^2            7(2^3-1)        3~6
3           8       2^3            15(2^4-1)       7~14
4           16      2^4            31(2^5-1)       15~30
5           32      2^4            63(2^6-1)       31~62

이 진 트 리 의 i 층 은 많아야 2 ^ (i - 1) 개의 노드 수 를 가지 고 깊이 가 k 인 이 진 트 리 는 많아야 모두 2 ^ (k + 1) - 1 개의 노드 수 (정의 근 노드 가 있 는 깊이 k0 = 0) 가 있다.
그리고 총 노드 수가 일치 하 는 것 을 '만 이 진 트 리' 라 고 부 르 고 깊이 는 k 에 n 개의 노드 가 있 는 이 진 트 리 이다. 그 중의 모든 노드 만 똑 같은 깊이 k 의 만 이 진 트 리 와 대응 할 수 있 고 번호 가 1 에서 n 인 노드 가 1 대 1 로 대응 할 때 '완전 이 진 트 리' 라 고 부른다.유형 이 진 트 리 는 뿌리 가 있 는 나무 이 고 각 노드 는 최대 2 개의 키 노드 가 있다.깊이 가 k 이 고 2 ^ (k + 1) - 1 개의 노드 가 있 는 이 진 트 리 를 만 이 진 트 리 (Full Binary Tree) 라 고 합 니 다.
한 개의 이 진 트 리 중에서 마지막 층 을 제외 하고 나머지 층 이 꽉 차 있 고 마지막 층 이 꽉 차 있 거나 오른쪽 에 몇 개의 노드 가 부족 하면 이 이 진 트 리 는 완전 이 진 트 리 (Complete Binary Tree) 의 깊이 가 k 인 완전 이 진 트 리 로 적어도 2k 개의 노드 가 있 고 많아야 2 (K + 1) - 1 개의 노드 가 있다.예 를 들 어 깊이 가 4 인 완전 이 진 트 리 는 최소 8 개의 노드 가 있 고 최대 15 개의 노드 가 있다.
완전 이 진 트 리 와 만 이 진 트 리 는 배열 로 이 루어 질 수 있다.

a = [0,  1,2,  3,4,5,6,   7,8,9,10,11,12,13,14]
//  1   2    3         4 
                    0
               1          2
            3     4    5     6
           7 8 9  10 11 12 13 14
             
a[2^2-1]  // 3
a[2^3-1]  // 7         
a[2^2-1+3]// 6         
            n   m   ，
         ，        

다른 나 무 는 해시 (대상) 로 구현 할 수 있 습 니 다.
더미 정렬http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/ 최대 더미 조정