데이터 구조 학습 - 셸 정렬 의 C 언어 구현

<!--
p, li { white-space: pre-wrap; }
-->
셸 정렬:
이 정렬 의 이름 은 발명자 의 이름 으로 정렬 하 는 방법 과 글자 상의 관계 가 없다.그 러 니까 이름 때문에 어려워 하지 마.K & R 의 C 프로 그래 밍 언어 에서 책 은 몇 줄 의 코드 만 사용 하여 이 정렬 알고리즘 을 간결 하 게 실현 했다.그럼 이 정렬 이 어떻게 이 루어 졌 는 지 살 펴 보 자.
 
<!--
p, li { white-space: pre-wrap; }
-->
 
원리:
 
우 리 는 정렬 할 서열 (크기 는 n) 을 그룹 으로 나 눌 것 입 니 다. 그룹의 수량 은 보통 이 서열 의 크기 의 절반 으로 정의 할 수 있 습 니 다 (즉 d = n/2). 그리고 계속 반 으로 접 을 수 있 습 니 다. 그룹의 구성원 은 간격 이 d 인 수 를 한 그룹 으로 나 눌 수 있 습 니 다.예 를 들 어 여기 길이 가 8 인 숫자 서열 이 정렬 되 어야 한다 면 우 리 는 먼저 이 서열 을 d = 4 조로 나 눌 수 있다. 각 조 는 두 개의 숫자 가 있다. (이쪽 의 4 는 8 의 절반 이다.)이 네 조 는 (R1, R5), (R2, R6), (R3, R7), (R4, R8) 입 니 다. 그 다음 에 그룹 내 비교 입 니 다. 전자 가 크 면 그들의 위 치 를 교환 합 니 다.차례로 유추 하 다.프로그램 을 작성 할 때 우리 가 가 진 수 와 그 와 d 크기 의 위 치 를 비교 하 는 것 입 니 다.여기 서 첫 번 째 조 의 수 는 4 이다. 그러면 첫 번 째 수 와 그 사이 의 간격 을 4 로 비교 하 는 것 이다.첫 번 째 정렬 후에 우 리 는 이 간격 을 줄 이 는 것 은 바로 이전 그룹의 d 를 반 으로 접 는 것 이다.그럼 이번 팀 은 2 개 밖 에 없어 요.각 조 는 4 개의 수가 있 습 니 다. 똑 같이 위 와 같 습 니 다. 간격 이 d = 2 인 위치 상의 수 를 비교 합 니 다. (실제로 조작 은 이 렇 지만 우 리 는 그들 이 이미 한 조 안에 있다 고 생각 할 수 있 습 니 다. 그룹 내 비교 라 고 할 수 있 습 니 다)우 리 는 d 가 마지막 에 1 이 될 것 이라는 것 을 알 고 있다. 그 때 는 인접 한 두 개의 수 를 비교 하고 모든 숫자 는 정확 한 위치 에 놓 일 것 이다.원 리 는 기본적으로 이렇다.
 
<!--
p, li { white-space: pre-wrap; }
-->
 
실현:
 
우 리 는 원 리 를 알 게 되 었 습 니 다. 그러면 익숙 한 언어 로 작성 하 세 요. 우 리 는 C 언어 로 작 성 했 습 니 다.
 
<!--
p, li { white-space: pre-wrap; }
-->
 
우 리 는 상술 한 원리 에 따라 그것 을 한 걸음 한 걸음 실현 한다.
     

 1 //函数的参数包含两个，一个是要排序的数组，一个是数组的大小
 2 //函数不使用额外的空间，只用到数组本身。这就要求数组在输入时候保留出
 3 //R[0],R[0]就相当是一个temp。用于互换两个数时的一个临时数。
 4 void shellsort(int R[],int n)
 5 {
 6     int i,j,d;
 7     d = n/2;
 8     while(d >= 1)
 9     {
10         //注意i的起始和最后的那个“=，我们的第一个数是R[1],所以i-d要从1开始
11         for(i = d + 1;i <= n;i++)
12         {
13             j = i - d;
14             //将R[i]暂存
15             R[0] = R[i];
16             //这边的R[0]就是R[j+d]也就是R[i]
17             while(j>0 && R[j] > R[0])
18             {
19                 //将j位置的值给j+d位置
20                 R[j+d] = R[j];
21                 j -= d;
22             }
23             //这边就是对应着上面的j-=d，如果上面的while执行了，j
24             //位置的值已经给了j+d位置了，那么j+d的值也要给j位置，互换
25             //这就要求下标必须是对应的。所以要将j-d才能满足这边是R[j]
26             //如果while没有执行，那么还将原来的R[i]的值放到原来位置上
27             R[j+d] = R[0];
28         }
29         //d减半
30         d/=2;
31     }
32 }

 
    위 에서 말 한 원리 에 따라 이 루어 진 것 입 니 다. 코드 도 많 지 않 지만 좀 어 지 러 워 보 입 니 다. 그럼 개선 할 수 있 을까요?다음 에 오 네.
<!--
p, li { white-space: pre-wrap; }
-->
간소화:
우 리 는 일반적으로 프로그램의 읽 을 수 있 도록 프로그램 을 정교 하 게 만든다.이것 도 K & R 의 한 사상 이 죠.우 리 는 while 와 for 가 일정한 상황 에서 대체 할 수 있다 는 것 을 안다.그래서 우 리 는 상술 한 절 차 를 더욱 치밀 하 게 만 들 수 있다. 우 리 는 세 개의 for 순환 을 사용 하면 된다.다음은 간소화 후의 실현 이다.
 

 1 #include<stdio.h>
 2 
 3 #define N 100
 4 void shellsort(int *,int);
 5 
 6 int main(void)
 7 {
 8     int v[N];
 9     int n,i;
10 
11     printf("输入你数组的大小:");
12     scanf("%d",&n);
13 
14     printf("输入%d个数，空格隔开：
",n);
15     for(i = 0;i < n; i++)
16     {
17         scanf("%d",&v[i]);
18     }
19 
20     shellsort(v,n);
21     
22     printf("shell排序后：");
23     for(i =0;i < n;i++)
24     {
25         printf("%3d",v[i]);
26     }
27     
28     printf("
");
29     return 0;
30 }
31 
32 void shellsort(int v[],int n)
33 {
34     int i,j,temp,gap;
35 
36     for(gap = n/2;gap > 0;gap /=2)
37         for(i =gap ;i < n ;i++)
38         for(j = i - gap;j>=0 && v[j] >v[j+gap]; j-=gap)
39          {
40             temp = v[j];
41             v[j] = v[j+gap];
42             v[j+gap] = temp;
43         }
44 }

 
<!--
p, li { white-space: pre-wrap; }
-->
여기 서 나 는 완전한 프로그램 을 제 시 했 지만, 우 리 는 함수 의 실현 만 을 보 았 다.위의 함수 에서 첫 번 째 for 순환 은 비교 수 간 의 간격 을 제어 하 는 것 이 고 그룹의 근거 라 고 할 수 있 습 니 다.중간의 순환 은 원소 의 이동 위 치 를 제어 하 는 것 이다.마지막 순환 은 그룹 내 비교 이 며 순서 가 맞지 않 으 면 위 치 를 바 꾸 는 것 이다.첫 번 째 함수 에 있 는 while 를 for 로 통합 하면 프로그램 이 간단 해 보 입 니 다. 우 리 는 이해 에 있어 서 약간 막 힐 수 있 습 니 다. while 와 for 사이 의 전환 에 익숙 하면 많이 좋아 질 것 입 니 다.
 
보충:
     
    for (표현 식 1; 표현 식 2; 표현 식 3)
      문장
 
    while 와 같은 값 은:
 
    표현 식 1;
     while (표현 식 2)
　　{
문장
표현 식 3;
　　}