알고리즘 빠 른 필기 (3): 정렬 의 원리 와 실현 을 선택 하 십시오.

1. 원리 소개
정렬 을 선택 하 는 것 은 간단 한 정렬 입 니 다. 생각 은 주로 정렬 을 기다 리 는 집합 을 여러 번 옮 겨 다 니 며 매번 최대 / 작은 값 을 팝 업 하고 새로운 집합 을 넣 습 니 다. 원본 집합 이 비어 있 을 때 까지.예 를 들 어:
가설 은 A = [1, 2, 5, 9, 3] 을 오름차 순 으로 정렬 하고 절차 와 결 과 는 다음 과 같다.

A 에서 최대 치 를 찾 아 pop 을 B 에 넣 고 실행 한 결 과 는 다음 과 같다.

A=[2,5,9,3]
B=[1]

1 부 중복 집행

A=[5,9,3]
B=[1,2]

1 부 중복 집행

A=[5,9]
B=[1,2,3]

1 부 중복 집행

A=[9]
B=[1,2,3,5]

1 부 중복 집행

A=[]
B=[1,2,3,5,9]

이때 A 가 비어 B

로 돌아 갑 니 다.
2. 운행 시간 분석
위의 과정 을 통 해 알 수 있 듯 이 A 를 정렬 하려 면 N 라운드 작업 을 해 야 하고 매 라운드 작업 은 목록 의 모든 요 소 를 검사 해 야 한다.정렬 이 진행 되면 서 매번 검사 해 야 할 요소 수가 점점 줄 어 들 고 마지막 으로 검사 해 야 할 요 소 는 하나 입 니 다.검사 할 때마다 평균 원소 수 는 1 / 2 이다.× n, 따라서 실행 시간 은 O (n) 입 니 다.× 1/2 × n) 그러나 대 O 표현법 은 1 / 2 와 같은 상 수 를 생략 하기 때문에 간단하게 O (n) 를 쓴다× n) 또는 O (n ^ 2).
3. 코드 구현
Go 언어 구현 과정 은 다음 과 같 습 니 다.

//  int       
func SelectSort(items []int) []int {
	result := make([]int,len(items))
	for i:=0;i< len(result);i++{
		tmpIndex := getMinItemIndex(&items)
		result[i]=items[tmpIndex]
		//               
		items = append(items[:tmpIndex], items[tmpIndex+1:]...)
	}
	return result
}

//       ，       
func getMinItemIndex(ints *[]int) int {
	//                
	min := (*ints)[0]
	smallestIndex :=0
	for index,item := range *ints {
		if item < min {
			min = item
			smallestIndex =index
		}
	}
	return smallestIndex
}

4. 총화

정렬 을 선택 하 는 시간 복잡 도 는 O (n ^ 2)

이다.