데이터 구조와 알고리즘 학습 3: 정렬 직접 삽입

하나.정렬 방법
기본 사상: 배열된 그룹 데이터 [0...n].처음에 데이터[0]는 하나의 질서 구역을 형성하고 무질서 구역은 데이터[1..n]이다.i=1부터 i=n까지 차례대로 데이터[i]를 현재 질서구 데이터[0.i-1]에 삽입하여 n개의 기록을 포함하는 질서구를 생성한다.
  • 삽입할 요소 데이터[i]를 오른쪽에서 왼쪽으로 순서대로 질서구역에 기록된 데이터[j](j=i-1, i-2,...,0)와 비교한다.
  • 데이터[j]가 데이터[i]보다 크면 데이터[j]를 한 위치로 옮깁니다.
  • 데이터[j]가 데이터[i]보다 작거나 같으면 검색 과정이 끝나고 j+1은 데이터[i]의 삽입 위치입니다.

  •  
    둘.애니메이션 데모
         http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/insertsort.htm
     
    셋.Java 코드
         
    	public static int[] insertSort(int[] data) {
    		int temp = 0;
    		for (int i = 1; i < data.length; i++) {
    			if (data[i - 1] > data[i]) {
    				temp = data[i];
    				int j = i - 1;
    				for (; j >= 0 && data[j] > temp; j--) {
    					data[j + 1] = data[j]; //  
    				}
    				data[j + 1] = temp;
    			}
    		}
    		return data;
    	}
     
    넷.시간 복잡성 및 안정성
  • 최적 시간 복잡도
  • 파일의 초기 상태가 양의 순서라면 필요한 키워드 비교 횟수 C와 기록 이동 횟수 M.
  • Cmin =n-1=0(n)
  • Mmin =0
  • 정렬에 직접 삽입하는 가장 좋은 시간 복잡도는 O(n)
  • 최악 시간 복잡도
  • 초기 파일이 역순일 경우 필요한 키워드 비교 횟수 C와 기록 이동 횟수 M.
  • Cmax =(n+2)(n-1)/2=O(n2 )
  • Mmax =(n-1)(n+4)/2=O(n2 )
  • 정렬에 직접 삽입하는 최악의 시간 복잡도는 O(n2)
  • 평균 시간 복잡도
  • O(n2 )

  • 알고리즘의 공간 복잡도: 알고리즘에 필요한 보조 공간은 감시 초소이고 보조 공간 복잡도 S(n)=O(1)이다.현지 정렬입니다.
  • 직접 삽입 정렬은 안정적입니다.

  •  

    좋은 웹페이지 즐겨찾기