C++알고리즘 힐 정렬 상세 및 인 스 턴 스

C++알고리즘 의 힐 정렬 알고리즘 상세 해석 및 실례
힐 정렬 알고리즘
정의:
          힐 정렬 은 정렬 을 삽입 하 는 일종 으로 증분 정렬 을 축소 하 는 것 이 라 고도 부 르 며 정렬 알고리즘 을 직접 삽입 하 는 더욱 효율 적 인 개선 버 전 입 니 다.
알고리즘 사상:
          힐 정렬 은 기록 을 아래 표 시 된 일정한 증분 에 따라 그룹 을 나 누 어 각 그룹 에 직접 정렬 알고리즘 을 삽입 하여 정렬 하 는 것 입 니 다.증분 이 점점 줄 어 들 면서 각 그룹 에 포 함 된 키워드 가 점점 많아 지고 증분 이 1 로 줄 어 들 때 전체 파일 은 마침 한 그룹 으로 나 뉘 어 알고리즘 이 종 료 됩 니 다.  
시간 복잡 도:
         O(N)
공간 복잡 도:
         O(1)
성능:
         힐 정렬 은 불안정 알고리즘(한 번 삽입 정렬 은 안정 적 이 며 같은 요소 의 상대 적 인 순 서 를 바 꾸 지 않 습 니 다.그러나 서로 다른 삽입 정렬 에서 같은 요 소 는 각자 의 삽입 정렬 에서 이동 하여 안정성 을 어 지 럽 힐 수 있 습 니 다)
우세:
        힐 정렬 은 대량의 보조 공간 이 필요 하지 않 고 정렬 시간 을 직접 삽입 하 는 것 보다 빠 르 며 코드 가 잘 이 루어 집 니 다.
단점:
        힐 정렬 은 직접 삽입 정렬 에 비해 최적화 되 어야 하지만 O(N)의 알고리즘 은 여전히 효율 이 높 지 않 고 힐 정렬 이 불안정 하 다.
코드 구현:

#include <iostream> 
#include <Windows.h> 
#include <assert.h> 
 
using namespace std; 
 
//    ,      
void ShellSort(int* arr, int len)  
{ 
  assert(arr); 
  int gap = 3;   //         ，gap 1          
  for (gap = 3; gap > 0; --gap)  //       ，  gap=1 
  { 
    for (int i = 0; i < len; ++i)    
    { 
      for (int j = i + gap; j < len; j = j + gap) 
      { 
        if (arr[j-gap] > arr[j]) 
        { 
          int temp = arr[j];  // arr[j]         
          arr[j] = arr[j-gap]; 
          arr[j-gap] = temp; 
        } 
      } 
    } 
  } 
} 

#include "ShellSort.h" 
 
void TestShellSort() 
{ 
  int arr[] = { 100, 2,888, 6, 10, 5, 3, 666, 78, 9, 10000, 45, 67, 33 }; 
  int len = sizeof(arr) / sizeof(arr[0]); 
  cout << "     ：" << ""; 
  for (int i = 0; i < len; ++i) 
  { 
    cout << arr[i] << "->"; 
  } 
  cout << endl; 
  ShellSort(arr, len); 
  cout << "     ：" << ""; 
  for (int j = 0; j < len; ++j) 
  { 
    cout << arr[j] << "->"; 
  } 
  cout << endl; 
} 
 
int main() 
{ 
  TestShellSort(); 
  system("pause"); 
  return 0; 
} 

읽 어 주 셔 서 감사합니다. 여러분 에 게 도움 이 되 기 를 바 랍 니 다.본 사이트 에 대한 여러분 의 지지 에 감 사 드 립 니 다!