찾기 와 정렬 의 기본 동작: 정렬 알고리즘 집합 찾기

중점
찾기 알고리즘 은 순서 찾기, 2 분 찾기, 해시 표 찾기, 2 차 정렬 트 리 찾기 에 중심 을 두 고 있 습 니 다.
정렬 알고리즘 은 거품 정렬, 삽입 정렬, 병합 정렬, 빠 른 정렬 에 중심 을 두 고 파악 합 니 다.
순서 찾기
알고리즘 설명
저장 구조 가 순서대로 저장 되 거나 링크 로 저장 되 는 선형 표를 순서대로 찾 습 니 다.
알고리즘 사상
순서 찾기 는 선형 찾기 라 고도 부 르 며 무질서 찾기 알고리즘 에 속 합 니 다.데이터 구조 선형 표 의 한 끝 에서 부터 순서대로 스 캔 하고 스 캔 한 노드 키 워드 를 주어진 값 k 와 비교 하 며 같 으 면 검색 성공 을 나타 낸다.검색 이 끝 났 는데 도 키워드 가 k 와 같은 결점 을 찾 지 못 하면 검색 에 실 패 했 음 을 나 타 냅 니 다.
알고리즘 구현

int sequenceSearch(int a[], int value, int len)
{
    int i;
    for(i=0; i)
        if(a[i]==value)
            return i;
    return -1;
}

알고리즘 분석
검색 에 성공 할 때의 평균 검색 길 이 는: (모든 데이터 요소 의 확률 이 같다 고 가정) ASL = 1 / n (1 + 2 + 3 +... + n) = (n + 1) / 2;검색 에 성공 하지 못 했 을 때 n + 1 번 비교 해 야 합 니 다. 시간 복잡 도 는 O (n) 입 니 다.그래서 순서대로 찾 는 시간의 복잡 도 는 O (n) 이다.
이분 찾기
알고리즘 설명
요 소 는 질서 가 있어 야 합 니 다. 순서 가 없 으 면 정렬 작업 을 먼저 해 야 합 니 다.
알고리즘 사상
반절 검색 이 라 고도 부 르 며 질서 있 는 검색 알고리즘 에 속 합 니 다.주어진 값 k 로 중간 노드 의 키워드 와 비교 하고 중간 노드 는 선형 표를 두 개의 서브 시트 로 나 누 어 같 으 면 찾 는 데 성공 합 니 다.같 지 않 으 면 k 와 이 중간 노드 키워드 의 비교 결과 에 따라 다음 단계 에 어떤 하위 표를 찾 는 지 확인 하고 재 귀적 으로 진행 합 니 다. 찾 거나 찾기 가 끝 날 때 까지 표 에 이러한 결점 이 없습니다.주: 반 으로 나 누 어 찾 는 전제 조건 은 질서 있 는 표 순서 로 저장 해 야 하 는 것 입 니 다. 정적 검색 표 에 대해 한 번 정렬 한 후에 변 하지 않 고 반 으로 나 누 어 찾 으 면 좋 은 효율 을 얻 을 수 있 습 니 다.그러나 삽입 이나 삭제 작업 을 자주 수행 해 야 하 는 데이터 세트 에 있어 서 질서 있 는 정렬 을 유지 하 는 것 은 적지 않 은 작업량 을 가 져 올 수 있 으 므 로 사용 하 는 것 을 권장 하지 않 습 니 다.
알고리즘 구현

//    ，   
int binarySearch1(int a[], int value, int len)
{
    int low, high, mid;
    low = 0;
    high = len-1;
    while(low<=high)
    {
        mid = low+(high-low)/2;    //    
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}
 
//    ，   
int binarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}

알고리즘 분석
최 악의 경우 키워드 비교 횟수 는 log 2 (n + 1) 이 므 로 시간 복잡 도 는 O (log2n) 이다.
 
거품 정렬
알고리즘 설명
교환 클래스 정렬 에 속 하여 안정 적 인 정렬
알고리즘 사상
인접 한 두 수의 크기 를 비교 하고 가장 큰 수 를 오른쪽 에 놓 으 며 계수기 i + +;
a [n - 2] 와 a [n - 1] 가 끝 날 때 까지 1 을 반복 합 니 다. 배열 a 에서 가장 큰 값 은 a [n - 1] 입 니 다.
정렬 을 진행 하 는 배열 의 길이 n 을 1 로 줄 이 고 1 과 2 를 반복 하 며 n 이 1 일 때 까지 정렬 이 완료 되 었 습 니 다.
알고리즘 구현

void bubbleSort(int* array, int length)
{
    for (int i = 0; i < length - 1; ++i)
    {
        //bool is_Swap=false;
        for (int j = 0; j < length - 1 - i; ++j)
        {
            if (array[j] > array[j + 1])
            {
                //is_Swap=true;
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                /*
                          
                a = a + b;
                b = a - b;
                a = a - b;
                          
                a=a^b;
                b=b^a;
                a=a^b;
                */
            }
        }
        //if(is_Swap==false)
            //return;
    }
}

알고리즘 분석
평균 시간 복잡 도: O (n ^ 2).가장 좋 은 상황: 정렬 을 기다 리 는 데이터 서열 이 정상 이면 거품 이 한 번 에 발생 하면 정렬 을 완성 할 수 있 습 니 다. 정렬 의 비교 횟수 는 n - 1 회 이 고 이동 하지 않 으 며 시간 복잡 도 는 O (n) 입 니 다.O (n) 의 복잡 도 를 실현 하려 면 코드 에 플래그 비트 (Bool 변수) 를 추가 해 야 합 니 다.최 악의 경우: 정렬 을 기다 리 는 데이터 서열 이 역순 이면 거품 정렬 은 n - 1 번 이 필요 하 다. 매번 n - i 번 정렬 의 비교 와 이동, 즉 비교 와 이동 횟수 가 모두 최대 치 에 달한다. 비교 횟수 = n (n - 1) / 2 = O (n ^ 2), 이동 횟수 는 비교 횟수 와 같 기 때문에 최 악의 시간 복잡 도 는 O (n ^ 2) 이다.
 
삽입 정렬
알고리즘 설명
 삽입 클래스 정렬 에 속 하고 정렬 이 안정 적 입 니 다.
알고리즘 사상
 정렬 할 배열 의 두 번 째 요 소 를 시작 으로 앞의 수 와 크기 를 비교 하여 적당 한 위 치 를 찾 아 모든 요소 가 삽 입 될 때 까지 삽입 합 니 다.
알고리즘 구현

void insertSort(int* array,int length) 
{
    int i = 0, j = 0, temp = 0;
    for (i = 1; i < length; ++i) 
    {
        //            ，              ，
        //                 。
        if (array[i] < array[i-1])
        {
            temp = array[i];
            for (j = i-1; temp < array[j] && j >= 0 ; --j) 
            {
                array[j+1] = array[j];
            }
            array[j + 1] = temp;
        }
    }
}

알고리즘 분석
 평균 시간 복잡 도: O (n ^ 2).가장 좋 은 상황: 정렬 대기 기록 이 질서 가 있 을 때 비교 해 야 할 횟수 는 n - 1 = O (n) 입 니 다.최 악의 경우: 정렬 대기 기록 이 역순 이면 가장 많은 비교 횟수 는 n * (n - 1) / 2 = O (n ^ 2) 입 니 다.
정렬
알고리즘 설명
 응용 이 넓 고 정렬 이 안정 적 입 니 다.
알고리즘 사상
병합 정렬 은 분 치 법의 전형 적 인 응용 으로 먼저 모든 하위 서열 을 질서 있 게 한 다음 에 모든 하위 서열 을 질서 있 게 한다.두 개의 질서 있 는 하위 서열 을 하나의 질서 있 는 표 로 합 쳐 2 번 병합 이 라 고 한다. 단계: 우선 질서 있 는 수열 을 1 분 2, 2 분 4 로 나 누 어....................................................................그리고 합병 을 진행 합 니 다. 매번 합병 은 질서 있 게 합 쳐 집 니 다.
알고리즘 구현
 

void MergeArray(int* array, int first, int mid, int last, int* temp)
{
    // a[first...mid] a[mid+1...last]  
    int i = first, j = mid + 1, k = 0;
    int lengthA = mid+1, lengthB = last+1;
    while (i < lengthA&&j < lengthB) 
    {
        if (array[i] < array[j])
            temp[k++] = array[i++];
        else
            temp[k++] = array[j++];
    }
    while (i < lengthA) 
    {
        temp[k++] = array[i++];
    }
    while (j < lengthB) 
    {
        temp[k++] = array[j++];
    }
    for (i = 0; i < k; ++i) 
    {
        array[first + i] = temp[i];
    }
}

void MergeSort(int* array, int first, int last, int* temp) 
{
    if (first >= last)
        return;
    int mid = (first + last) / 2;
    MergeSort(array, first, mid, temp);//    
    MergeSort(array, mid + 1, last, temp);//    
    MergeArray(array, first, mid, last, temp);//          
}

알고리즘 분석
평균, 최고, 최 악의 시간 복잡 도: O (n * log n)
이렇게 이해 할 수 있 습 니 다. 합병 은 O (log n) 단계 작업 이 필요 합 니 다. 모든 단계 에서 정렬 된 하위 서열 을 합병 하려 면 O (n) 의 작업 이 필요 합 니 다.그 시간 복잡 도 는 틀림없이 O (n * log n) 일 것 이다.
빠 른 정렬
알고리즘 설명
 교환 류 정렬 알고리즘 중에서 빠 른 배열 이 가장 빠르다.분 치 된 사상 을 채택 하여 불안정 하 게 순 위 를 매 긴 다.
알고리즘 사상
n 개의 요소 중에서 하나의 요 소 를 구역 의 기준 으로 선택 하고 보통 첫 번 째 요 소 를 선택한다.
이 원소 보다 작은 것 을 왼쪽 에 놓 고 이 원소 보다 큰 것 을 오른쪽 에 놓 으 면 중간 에 이 원 소 를 놓는다.
다시 좌우 서열 에 대해 1 과 2 를 반복 해서 각 서열 에 하나의 요소 만 있 고 정렬 이 끝 날 때 까지 한다.
알고리즘 구현
 

//  1
void QuickSort(int* array,int low,int high) 
{
    if (low >= high)
        return;
    int left = low;
    int right = high;
    int key = array[left];//             ，            。
    while (left != right)
    {
        while (left != right&&array[right] >= key)//    ，   key     key   
            --right;
        array[left] = array[right];
        while (left != right&&array[left] <= key)//    ，   key     key   
            ++left;
        array[right] = array[left];
    }
    array[left] = key;//  left  right

    //    ，    ，    。
    QuickSort(array, low, left - 1);
    QuickSort(array, left + 1, high);
}

알다 시 피 Partition 함 수 는 빠 른 정렬 에서 든 K 대 를 찾 는 문제 에서 든 모두 중요 한 위 치 를 차지 하기 때문에 따로 쓰 면 버 전 2 가 있다.

int Partition(int* array,int left,int right)
{
    int key = array[left];
    while (left != right)
    {
        while (left != right&&array[right] >= key)//    ，   key     key   
            --right;
        array[left] = array[right];
        while (left != right&&array[left] <= key)//    ，   key     key   
            ++left;
        array[right] = array[left];
    }
    array[left] = key;
    return left;//      
}

//     
void quicksort(int* arr, int left, int right)
{
    if(left< right)
    {
        int middle = mypartition(arr, left, right);
        quicksort(arr, left, middle-1);
        quicksort(arr, middle+1, right);
    }
}

알고리즘 분석
 
평균 시간 복잡 도: O (n * log n).원인: 빠 른 배열 은 배열 을 끝까지 나 누 는 것 이기 때문에 O (log n) 번 이 작업 이 필요 합 니 다. 매번 작업 할 때 n 번 을 정렬 해 야 하기 때문에 대부분의 경우 시간 복잡 도 는 O (n * log n) 입 니 다.가장 좋 은 상황: 매번 정렬 이 끝 난 후에 매번 에 두 개의 키 파일 의 길 이 를 대체적으로 같 게 하고 시간 복잡 도 는 O (n * log n) 이다.최 악의 경우: 정렬 대기 요소 가 정렬 되 어 있 습 니 다.n - 1 차 비 교 를 거 친 후 첫 번 째 요 소 는 위치 가 변 하지 않 고 n - 1 개 요소 의 하위 서열 을 얻 을 수 있 습 니 다.두 번 째 는 n - 2 차 비 교 를 통 해 두 번 째 요 소 를 원래 의 위치 에 위치 시 키 고 n - 2 개 요 소 를 포함 한 하위 서열 을 얻어 순서대로 유추 합 니 다. 이렇게 총 비교 횟수 는 n (n - 1) / 2 = O (n ^ 2) 입 니 다.
 
다음으로 전송:https://www.cnblogs.com/parzulpan/p/11258491.html