상용 정렬 알고리즘 비 재 귀적 편

그동안 거품, 삽입, 선택 등 간단 한 정렬 알고리즘 에 대해 서 는 잘 알 지 못 해 헷 갈 렸 다.저녁 에 시간 이 있 을 때 관련 정렬 알고리즘 을 회상 하고 기록 하 세 요.다음 에 말 한 정렬 알고리즘 은 모두 정수 에 대한 정렬 을 예 로 들 면:
      거품 정렬 의 실현 설명:
      1. 정렬 할 모든 정 수 를 배열 에 넣 기;      2. 배열 의 첫 번 째 숫자 부터 마지막 두 번 째 숫자 까지 하나씩 검 사 를 한다. 만약 에 특정한 사람의 정수 가 그의 다음 자리 보다 크 면 다음 자리 와 교환 한다.
      3. 다 시 는 교환 할 수 없 을 때 까지 2 번 절 차 를 반복 합 니 다.
      상기 알고리즘 에 따라 설명 을 하면 비교적 간단하게 코드 를 실현 할 수 있 습 니 다.

void bubble_sort(int *array, int length)
{
    int temp = 0;
    
    if (NULL == array || 0 == length)
    {
        return;
    }
    
    for (int i = length - 1; i >= 1 ; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (array[j] > array[j + 1])
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    
    return;
} 

 
      위의 알고리즘 설명 과 실현 에서 이 알고리즘 은 최적화 의 여지 가 있다 는 것 을 알 수 있다. 즉, 특정한 비교 과정 에서 한 번 의 교환 이 발생 하지 않 았 다 면 거품 정렬 이 이미 완성 되 었 다 고 볼 수 있다.최적화 결 과 는 다음 과 같다.

void bubble_sort(int *array, int length)
{
    int temp = 0;
    bool flag = false;
    
    if (NULL == array || 0 == length)
    {
        return;
    }
    
    for (int i = length - 1; i >= 1 ; i--)
    {
        flag = false;
        for (int j = 0; j < i; j++)
        {
            if (array[j] > array[j + 1])
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = true;
            }
        }
        
        if (!flag)
        {
            break;
        }
    }
    
    return;
} 

      정렬 에 대한 설명 삽입:
      1. 우선 빈 목록 을 새로 만 듭 니 다. 정렬 된 질서 있 는 수열 을 저장 하 는 데 사 용 됩 니 다. (우 리 는 '질서 있 는 목록' 이 라 고 부 릅 니 다.)      2. 원래 수열 에서 하나의 수 를 꺼 내 '질서 있 는 목록' 에 삽입 하여 질서 있 는 상 태 를 유지 합 니 다.      3. 원수 열 이 비어 있 을 때 까지 2 번 절 차 를 반복 합 니 다.
      상기 알고리즘 에 따라 설명 을 하고 구체 적 인 코드 는 다음 과 같다.

void insert_sort(int *array, int length)
{
    int temp = 0;
    int i, j;
    
    if (NULL == array || 0 == length)
    {
        return;
    }
    
    for (i = 1; i < length; i++)
    {
        temp = array[i]; 
        for (j = i - 1; j >= 0; j--)
        {
            if (temp < array[j])
            {
                array[j + 1] = array[j]; //       
            }
            else
            {
                break;
            }
        }
        array[j + 1] = temp; //     
    }
    
    return;
}

      코드 구현 을 보면 빈 목록 을 새로 만 들 지 않 고 원래 목록 에서 정렬 했 습 니 다.사실, 우 리 는 원래 목록 의 앞부분 (정렬 된 부분) 을 새 빈 목록 으로 볼 수 있 고, 뒷부분 (정렬 되 지 않 은 부분) 은 원래 목록 의 나머지 정렬 되 지 않 은 부분 으로 볼 수 있다.그렇다면 정렬 을 삽입 하 는 데 최적화 할 여지 가 있 을 까?우 리 는 모든 라운드 삽입 정렬 이 부분 정렬 의 결과 이 고 정렬 되 지 않 은 부분의 결 과 를 보장 할 수 없 기 때문에 거품 정렬 처럼 최적화 할 수 없다 는 것 을 알 수 있다.
 
      정렬 에 대한 설명 선택:
      1. 배열 에 n 개의 정렬 대기 정 수 를 놓 았 고 배열 아래 표 시 는 0 부터 n - 1 까지 입 니 다. i = 1;      2. 배열 의 i 번 째 요소 부터 n 번 째 요소 까지 가장 작은 요 소 를 찾 습 니 다.      3. 지난 단계 에 찾 은 최소 요소 와 i 위 요 소 를 교환 합 니 다.      4. i = n - 1 이 끝나 면 i + +, 2 단계 로 돌아 갑 니 다.
      상기 알고리즘 에 따라 설명 을 하고 구체 적 인 실현 코드 는 다음 과 같다.

void select_sort(int *array, int length)
{
    int temp = 0;
    int index = 0;
    
    if (NULL == array || 0 == length)
    {
        return;
    }
    
    for (int i = 0; i < length - 1; i++)
    {
        index = i;
        
        for (int j = i + 1; j < length; j++)
        {
            if (array[index] > array[j])
            {
                index = j;
            }
        }
        
        if (index != i)
        {
            temp = array[i];
            array[i] = array[index];
            array[index] = temp;
        }
    }
    
    return;
}

      힐 정렬 의 실현 설명:
      n 보다 작은 정수 d1 을 첫 번 째 증분 으로 하고 파일 의 모든 기록 을 (n 나 누 기 d1) 그룹 으로 나 눕 니 다.모든 거리 가 d1 인 배수 의 기록 은 같은 그룹 에 놓 여 있다.먼저 각 그룹 에 정렬 을 직접 삽입 합 니 다.그 다음 에 두 번 째 증 량 d2 < d1 을 취하 여 상기 그룹 과 정렬 을 반복 합 니 다. 취 하 는 증 량 dt = 1 (dt < dt - l <... < d2 < d1), 즉 모든 기록 을 같은 그룹 에 놓 고 정렬 을 직접 삽입 할 때 까지 합 니 다.
상기 알고리즘 에 따라 설명 을 하고 구체 적 인 실현 코드 는 다음 과 같다.

void shell_sort(int *array, int length)
{
    int temp = 0;
    int d, i, j;
    
    for (int d = length / 2; d >= 1; d /= 2)
    {
        for (int i = d; i < length; i++)
        {   
            temp = array[i];
            for (j = i - d; j >= 0; j -= d)
            {
                if (temp <array[j])
                {
                    array[j + d] = array[j];
                }
                else
                {
                    break;
                }
            }
            
            array[j + d] = temp;
        }
    }
    
    return;
}

      힐 의 정렬 에 대해 d 의 수치 추출 방법 은 상기 에 따라 매번 2 로 나 눌 필요 가 없다.예 를 들 어 매번 2 를 나 눈 후에 d 를 짝수 로 할 수 있 는 경우 d 는 1 을 더 할 수 있 지만 d 는 마지막 에 1 이 어야 한다.
      상기 정렬 알고리즘 이 똑 같이 곤 혹 스 럽 거나 헷 갈 리 기 쉬 운 친구 에 게 도움 이 되 기 를 바 랍 니 다.