기본 정렬 알고리즘 - 병합 정렬
9887 단어 데이터 구조와 알고리즘
병합 정렬
1 알고리즘 사상
수조를 중간에서 두 개의 서브수조로 나누고, 줄곧 귀속된 서브수조를 더 작은 서브수조로 나누며, 서브수조 안에 원소가 하나밖에 없을 때까지.차례대로 돌아오는 순서에 따라 순서를 배열한 하위 그룹을 끊임없이 합병하여 마지막에 전체 그룹의 순서를 배열한다.
2 코드 구현
public class MergeSort {
public static void main(String[] args) {
int[] nums = new int[]{9,8,7,6,5,4,3,2,1};
sort(nums,0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
public static void sort(int[] nums, int lo, int hi) {
if (lo >= hi) { //
return;
}
int mid = lo + (hi - lo) / 2; //
sort(nums, lo, mid); //
sort(nums, mid + 1, hi); //
merge(nums, lo, mid, hi);
}
public static void merge(int[] nums, int lo, int mid, int hi) {
int[] copy = nums.clone();
int k = lo, i = lo, j = mid + 1; // i ，j
while (k <= hi) {
if (i > mid) { // ， copy
nums[k++] = copy[j++];
} else if (j > hi) { // ， copy
nums[k++] = copy[i++];
} else if (copy[j] < copy[i]) { //
nums[k++] = copy[j++];
} else { //
nums[k++] = copy[i++];
}
}
}
}
3 알고리즘 분석
시간 복잡도: O(nlogn) 공간 복잡도: O(n). n개의 원소를 합병하려면 n의 크기를 가진 추가 수조를 분배해야 하기 때문에 합병이 완료되면 이 수조의 공간이 방출됩니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
두 갈래 나무의 깊이가 두루 다니다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
