교환 정렬 - 버블 정렬(Bubble Sort)
- 高洛峰원래의
- 2016-12-19 14:04:001390검색
교환 정렬은 주로 정렬 대상 레코드의 키 코드를 쌍으로 비교하여 정렬 대상 레코드의 키 코드가 발생하는 경우 정렬 요구 사항에 어긋나는 경우 교환합니다. 먼저 열 정렬의 버블링 과정을 살펴보겠습니다. 1
의 버블 방법은 다음과 같습니다.
i=1; //첫 번째 레코드부터 쌍 비교를 설정합니다.
i≥j이면 A 버블링 여행이 끝났습니다.
r[i].key와 r[i+1].key를 비교하여 r[i].key≤r[i+1].key이면 교환하지 말고 ⑤로 이동
r[i].key>r[i+1].key일 때, r[0]=r[i] r[i]=r[i+1]=r; [ 0]; r[i] 및 r[i+1]
i=i+1; 다음 두 레코드의 쌍 비교를 조정하고, ②
로 이동합니다. 버블 정렬 방법: n 레코드 테이블의 경우 첫 번째 버블은 가장 큰 키 코드를 갖는 레코드 r[n]을 얻는 것입니다. 두 번째 버블은 n-1 레코드 테이블에 대한 것이고 다른 레코드는 가장 큰 키 코드를 갖는 레코드입니다. 레코드 r[n-1]을 얻고 n개의 레코드가 키 순서 테이블에 있을 때까지 이를 반복합니다.
[알고리즘 10.6]
j=n; //n개의 레코드 테이블에서 시작
j
i=1; //버블링 1회, 첫 번째 레코드부터 쌍 비교를 설정합니다.
i≥j이면 버블링 1회가 종료됩니다. j=j-1; 레코드 수가 -1이면 ②
로 이동하여 r[i].key와 r[i+1].key를 비교합니다(r[i].key≤r[i+1].key인 경우). 교환하지 마세요. ⑤
r[i].key>r[i+1].key일 때 r[i]r[i+1]; i] and r [i+1] Exchange
i=i+1; 다음 두 레코드의 쌍별 비교를 조정하고 ④
[효율 분석]공간 효율성: 보조 장치는 하나만 사용됩니다.
시간 효율성: 총 n-1개의 버블링 작업이 필요합니다. j 레코드가 있는 테이블에 대해 한 번의 버블링 작업에는 j-1 키 코드 비교가 필요합니다.
