데이터 구조와 알고리즘 학습 2: 정렬 직접 선택

하나.정렬 방법
  • 배열된 그룹 데이터[0...n]는 현재 위치 i=0을 최소값으로position 표시하기;데이터 [i+1...n] 구간에 있는 모든 요소와 데이터 [position]를 비교하고 새position을 기록하며 마지막으로 데이터 [i]와 데이터 [position]를 교환합니다.이렇게 가장 작은 원소가 현재 위치에 이르렀다.
  • 현재 위치 i+1, 중복 1...

  •  
    둘.애니메이션 데모
          http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/zhijiexuanze.htm
     
    셋.Java 코드
         
    	public static int[] selectSort(int[] data) {
    		int temp = 0;
    		int position = 0;
    		int j = 0;
    		for (int i = 0; i < data.length - 1; i++) {			//i 
    			position = i;									//position 
    			j = i + 1;										
    			for (; j < data.length; j++) {					//j 
    				if (data[j] < data[position]) {
    					position = j;
    				}
    			}
    			if (position != i) {	
    				temp = data[i];
    				data[i] = data[position];
    				data[position] = temp;
    			}
    		}
    		return data;
    	}

     
     
    넷.시간 복잡성 및 안정성
  • 최적 시간 복잡도
  • 파일의 초기 상태가 양의 순서라면 필요한 키워드 비교 횟수 C와 기록 이동 횟수 M.
  • Cmin=n(n-1)/2=0(n2)
  • Mmin=0
  • 정렬을 직접 선택하는 가장 좋은 시간 복잡도는 O(n2)
  • 최악 시간 복잡도
  • 초기 파일이 역순일 경우 필요한 키워드 비교 횟수 C와 기록 이동 횟수 M.
  • Cmax=n(n-1)/2=O(n2)
  • Mmax=3(n-1)=O(n)
  • 정렬을 직접 선택하는 최악의 시간 복잡도는 O(n2)
  • 평균 시간 복잡도
  • O(n2)

  • 직접 선택 정렬은 현지 정렬이고 불안정합니다.반례[2,2,1].
  • 좋은 웹페이지 즐겨찾기