Sorting Algorithm-Shell Sort

셸 Sort - 힐 정렬
Algorithm：
힐 정렬 은 D. L. Shell 이 1959 년 에 제기 한 정렬 알고리즘 이다. 그 전에 정렬 알고리즘 의 시간 복잡 도 는 기본적으로 O (n ^ 2) 였 고 힐 정렬 알고리즘 은 이 시간의 복잡 도 를 돌파 한 첫 번 째 알고리즘 중 하나 이다.
특정한 '증 량' 과 떨 어 진 기록 을 하나의 하위 서열 로 구성 해 야 하위 서열 에서 각각 정렬 을 직접 삽입 한 후에 얻 은 결 과 는 부분 적 인 질서 가 아니 라 기본 적 인 질서 가 있 음 을 확보 할 수 있다.
Ex：
49，38，65，97，76，13，27，49，55，04
처음: 보폭 5
제1 조: 49, 13
제2 조: 38, 27  
제3 조: 65, 49
제4 조: 97, 55
제5 조: 76, 04
각 그룹 에 정렬 을 직접 삽입 한 후   13，27，49，55，04，49，38，65，97，76
두 번 째: 보폭 2
제1 조: 13, 27, 49, 55, 04
제2 조: 49, 38, 65, 97, 76
각 그룹 에 정렬 을 직접 삽입 한 후   04，13，27，49，55，38，49，65，76，97
세 번 째: 보폭 은 1 (마지막 보폭 은 1 이 어야 함)
최종 결과: 04，13，27，38，49，49，55，65，76，97
Code：

void Shell_Sort(vector<int> &v)  //   n/2...  
   {
	int gap =(v.size()/2);  //    
	while (gap > 0)   //    1
	{
		for (int i = gap; i < v.size(); i++)
		{
			int j = i-gap;
			int key = v[i];
			while (j>=0 && v[j]>key)
			{
				v[j+gap] = v[j];
				j = j - gap;
			}
			v[j+gap] = key;
		}
		gap /= 2;
	}	
   }

Analysis：
힐 정렬 의 관건 은 마음대로 조 를 나 눈 후에 각자 정렬 하 는 것 이 아니 라 특정한 '증분' 의 기록 을 하나의 키 서열 로 구성 하여 점프 식 이동 을 실현 하여 정렬 의 효율 을 향상 시 키 는 것 이다.
이곳 의 '증 량' 에 대한 선택 은 매우 관건 적 이다. 아직 은 수학 문제 이기 때문에 지금까지 가장 좋 은 증 량 서열 을 찾 은 사람 이 없다.그러나 대량의 연구 에 따 르 면 증분 서열 이 dlta [k] = 2 ^ (t - k + 1) - 1 (0 < = k < = [log 2 (n + 1)] 일 때 좋 은 효 과 를 얻 을 수 있 고 그 시간 복잡 도 는 O (n ^ 1.5) 이 며 직접 정렬 O (n ^ 2) 보다 좋다.주의해 야 할 것 은 증분 서열 의 마지막 증 가 는 반드시 1 과 같 아야 한 다 는 것 이다.또한 기록 은 점프 식 이동 이기 때문에 힐 정렬 은 안정 적 인 정렬 알고리즘 이 아니다.
힐 알고리즘 의 발명 으로 인해 우 리 는 느 린 속도 로 정렬 하 는 시대 (시간 복잡 도 를 O (n ^ 2) 를 넘 어 섰 고 그 후에 더욱 효율 적 인 정렬 알고리즘 도 연이어 나 타 났 다.
unstable sort