데이터 구조와 알고리즘 학습1: 거품 정렬

1814 단어 데이터 구조와 알고리즘
하나.정렬 방법
  • 는 배열된 수조 데이터[0...n]를 수직으로 배열하고 각 원소 데이터[i]는 하나의 기포로 간주하며 기포의 무게는 데이터[i]의 값이다.
  • 맨 밑에 있는 기포 데이터[n]부터 스캐닝하여 이전 기포 데이터[n-1]와 무게를 비교하고 데이터[n]<데이터[n-1]는 교환한다.그리고 데이터[n-1]와 데이터[n-1-1]를 비교해서...한 바퀴가 떨어지자 가장 가벼운 기포가 맨 위에 있는 데이터[0]의 위치로 달려갔다.
  • 2과정을 반복하여 두 번째 가벼운 기포를 데이터[1]의 위치로 이동시킨다.다시 반복...

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

     
     
    넷.시간 복잡성 및 안정성
  • 최적 시간 복잡도
  • 파일의 초기 상태가 정렬된 경우 한 번 스캔하면 정렬이 완료됩니다.필요한 키워드 비교 횟수 C와 레코드 이동 횟수 M이 모두 최소값에 도달했습니다.
  • Cmin=n-1=O(n)
  • Mmin=0
  • 거품 정렬이 가장 좋은 시간 복잡도는 O(n)
  • 최악 시간 복잡도
  • 초기 파일이 반차례일 경우 n-1차례 정렬이 필요합니다.매 정렬은 n-i회 키워드의 비교(1≤i≤n-1)를 진행하고 매번 비교할 때마다 세 번 기록을 이동하여 교환 기록 위치에 도달해야 한다.이 경우 비교와 이동 횟수가 모두 최대치에 달한다.
  • Cmax=n(n-1)/2=O(n2)
  • Mmax=3n(n-1)/2=O(n2)
  • 거품 정렬의 최악의 시간 복잡도는 O(n2)
  • 평균 시간 복잡도
  • O(n2)

  • 거품 정렬은 현지 정렬이고 안정적이다.

    • 오.알고리즘 최적화
  • exchange 로고를 설정합니다.설정하지 않으면 Cmin=n (n-1)/2=O (n2)
    • jquerymobile listview 부분 리셋
    예전에 제가 만든 사이트에 댓글을 달아보도록 하겠습니다.

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage