데이터 구조 (1): 찾기 와 정렬

1. 정렬 삽입
정렬 복잡 도 t = O (n 의 제곱) 를 삽입 하여 정렬 된 질서 표 에 기록 을 삽입 하여 새로운 길이 + 질서 표 의 구체 적 인 조작 을 합 니 다.

수 i 와 수 i - 1 비, 작 으 면 데이터 [0] 에 수 i 를 보초병

보초병 은 순서대로 수 i - 2 및 이전의 수 (수 j 로 표시) 에 비해 보초병 이 작 으 면 j 를 세 어 뒤로 이동 하고 그렇지 않 으 면 수 j 뒤의 위치 에 덮 인 다

.

주의, – j 가 0 까지 왔 을 때 data [0]

void insert_sort(int data[], int n) {//data[0]     
    int i, j;
    for (i = 2; i <= n; ++i) { // i 1  
        if (data[i] < data[i-1]) {
            data[0] = data[i];  //     
            for (j = i-1; data[0] < data[j]; --j) {  
                data[j+1] = data[j];  //　        
            }
            data[j+1] = data[0]; //               
        }
    }
}//insert_sort

2. 거품 정렬
복잡 도 t = O (n 의 제곱) 교환 서열 에 인접 한 두 정 수 를 기본 조작 으로 정렬 된 기록 배열 data [0. n - 1] 를 수직 으로 배열 하고 모든 기록 data [i] 를 기포 로 간주한다.가 벼 운 기포 가 무 거 운 기포 아래 있 으 면 안 된다 는 원칙 에 따라 위 에서 아래로 배열 data 를 스 캔 하여 무 거 운 사람 이 가라앉는다.이렇게 반복 하면 서 무 거 운 기포 가 순서대로 가라앉 아 마지막 까지 질서 가 있다.

void bubble_sort(int data[], int n) {  
    int i, j;  
    bool tag = true;  

    for (i = n-1; i > 0 && tag; --i) { //                 
        tag = false;  
        for (j = 0; j < i; ++j) {  
            if (data[j] > data[j+1]) {  
                swap(data[j], data[j+1]);  
                tag = true;  
            }  
        }  
    }  
}//bubble_sort 

3. 이분 찾기
질서 있 는 배열 을 2 분 검색 합 니 다.

/*         ，    return:               ，    -1 */  
int bsearch(int data[], int n, int key) {  
    int left = 0, right = n -1;  
    while (left <= right) {  
        int mid = (left + right) / 2;  
        if (data[mid] == key) {  
            return mid;  
        }  
        if (data[mid] > key) {  
            right = mid - 1;  
        } else {  
            left = mid + 1;  
        }  
    }  
    return -1;  
}  

//     
//data     
int bsearch(int data[], int left, int right, int key) {  
    if (left > right) {  
        return -1;  
    }  

    int mid = (left + right) / 2;  
    if (data[mid] == key) {  
        return mid;  
    }  
    if (data[mid] < key) {  
        return bsearch(data, mid, right, key);  
    }  
    return bsearch(data, left, mid, key);  
}  

4. 빠 른 정렬
복잡 도 최 악 O (n 의 제곱), 평균 O (nlogn) * * 보조 저장 소 O (logn).거품 을 일 으 키 는 개선 이자 정렬 사상 을 교환 하 는 것 이다. 한 번 의 정렬 을 통 해 배열 을 두 개의 독립 된 부분 으로 나 누 는데 그 중의 일부분 의 값 이 다른 부분 보다 작 으 면 이 두 부분 에 대해 전체 서열 이 질서 가 있 을 때 까지 계속 빠 른 정렬 을 한다.
구체 적 인 조작: 빠 른 배열 은 두 함수 로 구성 되 어 있 으 며, 하 나 는 파 티 션 이 중심 축 에 따라 데이터 data [] 를 파 티 션 하고, 다른 하 나 는 quick 입 니 다.sort, 먼저 파 티 션 을 호출 하여 한 번 구분 한 다음 에 앞 뒤 두 파 티 션 을 각각 quick 로 재 귀적 으로 호출 합 니 다.정렬

/*        ，      data[low...high] ，       ，             ，           */  
int partition(int data[], int low, int high) {  
    int pivot = data[low]; //   ，      ，         。 

    while (low < high) {  
        while (low < high && data[high] >= pivot) { //  high       ，     pivot    
            --high;   
        } //  data[high]<pivot 
        data[low] = data[high]; // data[high]  data[low] ，  data[high]    
        while (low < high && data[low] <= pivot) { // low    pivot ，    ++ 
            ++low;  
        } //  data[low]>pivot 
        data[high] = data[low]; // data[low]  data[high] 。  data[low]    
    }  
    //while   ，data[low]      

    data[low] = pivot;  
    return low; //   low     pivot         
}  
void quick_sort(int data[], int low, int high) {  
    if (low < high) {  
        int k = partition(data, low, high);  
        quick_sort(data, low, k-1);  
        quick_sort(data, k+1, high);  
    }  
}// quick_sort 

5. 힐 정렬
먼저 전체 대기 기록 을 몇 개의 하위 서열 로 나 눈 다음 에 정렬 을 직접 삽입 하고 전체 가 기본적으로 질서 가 있 을 때 전체 에 대해 직접 정렬 을 삽입 합 니 다 (하위 서열 요 소 는 서로 인접 하지 않 고 특정한 증 가 된 기록 으로 구 성 된 하위 서열 입 니 다)

void shell_insert(int data[], const int n, const int d) { // d    data[0]    
    int i, j, tmp;  

    //              
    for (i = d; i <= n; i++) {   
        data[0] = data[i];  
        for (j = i-d; (j > 0) && (data[0] < data[j]); j-=d) { //                       j>0，  j      d  ，         
            data[j+d] = data[j];  
        }  
        data[j+d] = data[0];  
    }  
}  
/* params: data :     ，    data[1...n] ，data[0]   ，     darr :    d     。               ，      1 len_data : data    len_darr : darr    */  
void shell_sort(int data[], int darr[], const int len_data, const int len_darr) {  
    for (int i = 0; i < len_darr; ++i) {  
        shell_insert(data, len_data, darr[i]);  
    }  
}//shell_sort 

6. 간단하게 정렬 선택
기본 사상: n - (i - 1) 개 기록 에서 가장 작은 기록 을 질서 있 는 서열 의 i 번 째 요소 로 선택 합 니 다.

void simple_select_sort(int data[], int n) {  
    int i, j, min_index;  

    for (i = 0; i < n; ++i) {  
        min_index = i; // min_index          。         ，              
        for (j = i+1; j < n; ++j) {   //   i+1 
            if (data[j] < data[min_index]) {  
                min_index = j;  
            }  
        }  
        if (i != min_index) {  
            swap_int(data[i], data[min_index]);  
        }  
    }  
} // simple_select_sort 

7. 쌓 기 정렬
최 악 = 평균 = O (nlogn), 보조 저장 이 필요 하지 않 습 니 다. data [0] 를 임시 저장 하지 않 고 무질서 한 서열 을 완전 이 진 트 리 에 넣 습 니 다.큰 더미 로 조정 (출력 할 때 큰 것 에서 작은 것 으로 출력 하고, 서열 은 꼬리 에서 앞으로 뻗 어 서열 이 있 는 것 으로) 출력 더미 로 조정 한 후, 다시 큰 더미 로 조정 합 니 다.
쌓 아 올 리 는 데 많은 시간 을 쓰 고 n 이 비교적 큰 상황 에 적용 한다.

/* heap_adjust  data      。   data[start...end]   data[start]          (             )       ，   data[start]          。     data[n/2+1...n-1]          (         ，    )。      start          ， n/2(n data   )，start    ，   0。 */  
void heap_adjust(int data[], int start, int end) {  
    //     ，          (    ，                 ，        ) 
    for (int child_index = start * 2; child_index <= end; child_index *= 2) {  
        if (child_index < end && data[child_index] < data[child_index+1]) {  
            ++ child_index;   
        }// i   data[start]         
        if (data[start] >= data[child_index]) {// data[start]           ；        ，     
            break;   
        }  
        swap_int(data[start], data[child_index]); //            
        start = child_index; //          
    }  
}  
/*           . */  
void heap_sort(int data[], int n) {  
    //        ，   data[0]     
    for (int i = n/2; i >= 0; --i) { // i            ，     
        heap_adjust(data, i, n-1);  
    } //  data     

    for (int i = n-1; i > 0; --i) {  
        swap_int(data[0], data[i]); //    ，data[i]           ， data[0...i-1] data[0]            
        heap_adjust(data, 0, i-1); // data[0]         (           )。    data[0...i-1]     。 
    }  
}// heap_sort 

8. 병합 정렬
최 악 = 평균 = O (nlogn), 보조 저장 소 O (n) 의 초기 서열 은 n 개의 질서 있 는 하위 서열 로 볼 수 있 으 며, 하위 서열 의 길 이 는 1 이 고, 그 다음 에 두 개 를 합 쳐 길이 가 2 인 질서 있 는 하위 서열 을 얻 을 수 있다.두 냥 더 합치 면...길이 가 n 인 서열 을 얻 을 때 까지 2 번 병합 정렬 이 라 고 합 니 다.
logn 병합 을 진행 하려 고 합 니 다.

void merge(int data[], int left, int mid, int right) {  
    //new        tmp  ,     tmp[left..mid] tmp[mid+1..right]      data[left...right] 

    int *tmp = new int[right - left + 1];  
    int i = left;   
    int j = mid + 1;   
    int k = 0;  
    while (i <= mid && j <= right) {  
        if (data[i] <= data[j]) {  
            tmp[k++] = data[i++];  
        } else {  
            tmp[k++] = data[j++];  
        }  
    }  
    while (i <= mid) {  
        tmp[k++] = data[i++];  
    }  
    while (j <= right) {  
        tmp[k++] = data[j++];  
    }  

    //      
    i = left;  
    k = 0;  
    while (i <= right) {  
        data[i++] = tmp[k++];  
    }  
    delete[] tmp;  
}  

void merge_sort(int data[], int left, int right) { //        data  
    if (left >= right) {  
        return;  
    }  
    int mid = (left + right) / 2;  
    merge_sort(data, left, mid);//           
    merge_sort(data, mid+1, right);//           
    merge(data, left, mid, right);//  ，            ，              。 
} //merge_sort