프로그래머 원 요리 닭 학습 일지 (5 - 데이터 구조 편)

데이터 구조 지식 점 복습
삽입 형 정렬 알고리즘
1. 직접 삽입 (안정, 특히 입력 개 수 를 알 고 입력 하면 서 정렬 하 는 데 적합)

#include
#include
using namespace std;

int main(){
    int n,tag,temp;
    while(cin>>n){
        //InsertSort seems like the best choice
        int num[n];
        for(int i=0; i<n; i++){
            cin>>num[i];
            tag = i;
            while(tag>0){
                if(num[tag]<num[tag-1]){
                    temp = num[tag-1];
                    num[tag-1] = num[tag];
                    num[tag] = temp;
                    tag--;
                }else
                    break;
            }
        }
        
        for(int i=0; i<n; i++)
            cout<<num[i]<<" ";
        
        cout<<endl;
    }
}

2. 반절 삽입 (불안정)
교환 형 정렬 알고리즘

거품 정렬 사상: 거품 이 일어 날 때마다 최대 (또는 최소) 요 소 를 마지막 에 놓는다.예제 코드 (Java) (Ps: 거품 이 간단 하기 때문에 이전 큰 프로그램 에서 하 나 를 파 냈 습 니 다. 이번 에는 가장 작은 것 을 맨 끝 에 두 었 습 니 다)

for(i=0;i<SymNum-1;i++)
         //    
         for(j=0;j<SymNum-1-i;j++) {
            //     SymNum-1-i，                   
                if(p[j]<p[j+1]){
                    tempFlo = p[j];
                    p[j] = p[j+1];
                    p[j+1] = tempFlo;
                    }
          }
}               

빠 른 정렬 사상: 하나의 요 소 를 중심 원 으로 하고 다른 요 소 를 비교 한 다음 에 좌우 두 부분 으로 나 눈 다음 에 부분 집합 내부 에서 순서대로 돌아 가 최종 적 으로 질서 가 있다.일반적으로 빠 른 정렬 은 세 가지 실현 방식 이 있다. (가장 간단) 매번 맨 앞 (또는 맨 뒤에) 의 요 소 를 중심 으로 하지만 미리 정렬 한 데이터 에 있어 O (n * n) 의 시간 복잡 도 에 달 할 수 있다.(대가 가 비교적 높다) 매번 에 무 작위 로 하나의 중추 원 이 생 긴 다. 그러면 매번 최 악의 상황 이 되 지 는 않 지만 무 작위 수가 발생 하 는 비용 도 매우 크다.(상용) 세 개의 중간 값 분할 법 은 배열 의 첫 번 째 요소, 마지막 요소, 중간 요소 의 중간 값 을 중심 으로 한다.첫 번 째 요 소 를 허브 인 스 턴 스 코드 로 (자바)

int tagPos(int num[], int low, int high){
    int tag = num[low];
    while(low<high){
        while(low<high && num[high]>tag)
            high--;
        num[low]=num[high];
        while(low<high && num[low]<tag)
            low++;
        num[high]=num[low];
    }
    num[low]=tag;
    return low;
}

void QuickSort(int num[], int low, int high){
    if(low<high){
        int tl;
        tl = tagPos(num,low,high);
        QuickSort(num,low,tl-1);
        QuickSort(num,tl+1,high);
    }
}

세 개의 중간 값 추출 허브 예제 코드 (Java) (Ps: 현재 본인 은 지침 을 쓸 줄 모 릅 니 다...........................................................................

    int getBigger(int a,int b){
        if(a>b)
            return a;
        else
            return b;
    }

    int getSmaller(int a,int b){
        if(a<b)
            return a;
        else
            return b;
    }

    int getPoint(int array[]){
        if(getBigger(array[0],array[array.length/2])< array[array.length-1])
            return getBigger(array[0],array[array.length/2]);
        else
            return getBigger(getSmaller(array[0],array[array.length/2]),array[array.length-1]);
    }

    int getNode(int array[],int a){
        if(array[0] == a)
            return 0;
        else if(array[array.length - 1] == a)
            return array.length - 1;
        else
            return array.length/2;
    }

선택 형 정렬 알고리즘
1. 간단 한 선택
전재 가 필요 하 시 면 출처 를 밝 혀 주 십시오.
장기 갱신