정렬 의 거품 정렬 과 쌓 기 정렬

4171 단어 algorithm
최근 에 leetcode 를 닦 고 있어 서 몇 편의 알고리즘 을 동시에 업데이트 한 글 입 니 다.우선 서열 편 이다. 대학 에서 서열 에 익숙 한 난 롯 불 을 푸 르 게 만 들 었 는데 지금 은 갑자기 잊 어 버 렸 다.내 가 다시 주 워 올 게.이 편 은 주로 줄 을 서서 순 서 를 매 기 는 것 으로, 거품 이 매우 고전적 이 니, 가 는 김 에 한 번 써 보 자.거품 이 일어 나 는 사고방식 은 이중 순환 이다. 첫 번 째 순환 은 그 중에서 가장 크 거나 가장 작은 수 를 마지막 에 놓 고 두 번 째 순환 은 그 중에서 두 번 째 크 거나 두 번 째 작은 수 를 두 번 째 로 찾 아서 두 번 째 순환 이 끝 날 때 까지 정렬 을 완성 한다.
//     
void sort(int[] nums){
    int temp=0;
    for(int i=0;ilength;i++){
        for(int j=0;jlength-1;j++){
            if(nums[j]>nums[j+1]){
                temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }

        }
    }

}

시간 복잡 도 O (n2)
쌓 기 정렬: 여기 큰 쌓 기 를 소개 합 니 다. 작은 쌓 기 는 비슷 합 니 다.이 진 트 리 의 구 조 를 이용 하여 매번 가장 큰 수 를 뿌리 노드 위치 에 놓 은 다음 에 마지막 숫자 와 뿌리 노드 위치의 숫자 를 바 꾼 다음 에 마지막 위 치 를 한 자리 앞으로 옮 겼 다.
void adjustHeap(int[] nums,int parent,int length){
    int child = parent*2+1;//   
    while (child < length){
        if(child+1<length && nums[child]1]){//            ，           
            child++;//           
        }
        if(nums[parent]//        ，     
            int temp = nums[parent];
            nums[parent] = nums[child];
            nums[child] = temp;
            parent = child;
            child = parent*2+1;
        }else{//          ，    
            break;
        }

    }

}


void heapSort(int[] nums){
    for(int i = nums.length/2;i>=0;i--){
        //          
        adjustHeap(nums,i,nums.length);
    }   

    for(int i = nums.length-1;i>0;i--){
        //  nums.length-1 ，         
        //            
        int temp = nums[i];
        nums[i] = nums[0];
        nums[0] = temp;
        //    
        adjustHeap(nums,0,i);
    }
}

손 으로 두 개의 순 서 를 썼 는데 갑자기 쌓 인 순서 와 거품 이 약간 비슷 하 다 는 것 을 느 꼈 다. 단지 쌓 은 순 서 는 이 진 트 리 의 구 조 를 이용 하여 매번 에 비교 하 는 것 은 log 2n 회 에 불과 하 다. 그 다음 에 모두 n 회 를 실 행 했 기 때문에 시간 복잡 도 는 n * log 2n 이 고 공간 복잡 도 는 두 개 모두 n 이다.
커스텀 프로토콜 핸들러와 URI 스킴 만들기! - 1 부
금 산 쾌속 반 개발 (4)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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