정렬 간단정리!

• 버블 정렬

이웃한 두 원소의 대소관계비교

O(n2)

• ​2.선택 정렬

가장 작은원소 찾아서 앞으로 가져오는것

O(n2)

​

• 삽입정렬

하나 선택해서 본인의 자리에 넣는거

O(n2)

​

• 이진삽입정렬

삽입정렬에 + 본인자리에 넣을때 이진탐색으로

​

• 셸정렬

n칸 떨어져있는 거끼리 정렬->더 적은 칸 정렬

n은 h*3+1 수열 사용

O(n1.25)

​

• 퀵정렬

하나 기준두고 오른쪽 왼쪽 보내기 반복

임의 3개꺼내서 중앙값고르는게 그나마 시간 덜걸림

O(nlogn)

​

• 병합정렬

다 나눠서 다시 다 합치는거

O(nlogn)

​

• 힙정렬

루트에서 시작해서 자신보다 큰 자식과 바꾸기

O(nlogn)