C 에서 자주 사용 하 는 세 가지 정렬 방법 에 대한 정리 와 분석 을 깊이 있 게 연구한다.

정렬 은 프로 그래 밍 에서 매우 중요 한 내용 이다.그 기능 은 무질서 한 데 이 터 를 질서 있 는 데이터 서열 로 배열 하고 배열 한 데 이 터 를 큰 것 에서 작은 것 으로 배열 하거나 작은 것 에서 큰 것 으로 배열 하 는 것 이다.일반적으로 도 이 두 가지 상황 만 있다.    예 를 들 어 우리 가 반 학생 들 의 성적 을 통계 하면 보통 학 번 에 따라 통 계 를 하 는데 원래 성적 은 무질서 하 게 배열 되 어 있다.그러면 우리 가 성적 에 대한 조회 에 매우 적합 하지 않다.그러면 보통 우리 가 성적 조 회 를 하기 전에 먼저 순 위 를 매 긴 다.예 를 들 어 높 은 점수 에서 낮은 점수 로 순 위 를 매 기 면 본 반 의 최고 점수 와 최저 점 을 빨리 찾 을 수 있다.성적 과 비교 하여 앞 이나 뒤에 있 는 학생.정렬 에는 여러 가지 방법 이 있 습 니 다.자주 사용 하 는 세 가지 방법 이 있 습 니 다.거품 정렬,정렬 선택,정렬 삽입 등 이 있 습 니 다.다음은 이 세 가지 방법 에 대해 분석 과 비 교 를 해서 여러분 들 이 더욱 잘 이해 하고 응용 할 수 있 도록 하 겠 습 니 다.거품 정렬    1.거품 정렬 의 기본 사상:n 개 수 를 정렬(현재 가정 은 큰 것 에서 작은 것 으로 정렬 하고 아래 는 모두 이에 따라 진행)하고 인접 한 두 개의 수 를 순서대로 비교 하 며 큰 수 를 앞 에 놓는다.즉,첫 번 째 수 와 두 번 째 수 를 비교 하고 큰 수 를 앞 에 두 고 작은 수 를 두 고 두 번 째 와 세 번 째 수 를 비교 한 다음 에 큰 수 를 앞,작은 수 를 두 고그리고 차례대로 유추...1 차 비 교 를 거 친 후에 우 리 는 가장 작은 숫자 가 맨 아래 에 있 는 것 을 찾 았 다.그리고 다음 라운드 비 교 를 하면 마지막 숫자 는 더 이상 비교 에 참가 하지 않 아 도 되 기 때문에 이번 라운드 에서 한 번 적 게 비교 할 수 있다.분명 한 것 은 이중 순환 으로 이 문 제 를 디자인 해 야 한다.외층 순환 통제 가 진행 하 는 라운드 수,내부 순환 으로 매 라운드 의 비교 횟수 를 제어 해 야 한다.그러면 도대체 몇 라운드 가 필요 하고 매 라운드 가 몇 번 이 필요 한 지 우 리 는 하나의 사례 를 통 해 알 아 보 자.2.정렬 과정 예 를 들 어:
외부 순환
1 라운드
2 라운드
삼 륜
사 륜
내부 순환
다섯 개 수 를 네 번 비교 하 다
4 개 수 비교 3 회.
3 개 비교 2 회.
두 개 수 를 한 번 비교 하 다
7
5
8
6
9
 
1 회
두 번
세 번
네 번
1 회
두 번
세 번
1 회
두 번
1 회
7
5
8
6
9
7
8
5
6
9
7
8
6
5
9
7
8
6
9
5
8
7
6
9
5
8
7
6
9
5
8
7
9
6
5
8
7
9
6
5
8
9
7
6
5
9
8
7
6
5
 
가장 작은 수 는 5 가 라 앉 았 고,나머지 4 개 수 는 계속 비교 했다.
차 소수 6 가라앉 고 나머지 3 개 수
7.바닥 에 가라앉 고 나머지 2 개 수 비교
마지막 두 개 를 세 어 비교 하 다.
    그러면 이 정렬 과정 을 통 해 우 리 는 정렬 을 어떻게 하 는 지 알 게 되 었 다.그러면 누가 기포 인지 우 리 는 그 중에서 답 을 찾 을 수 있다.그러면 큰 것 부터 작은 것 까지 정렬 을 하고 큰 것 은 기포 이다.정렬 이 진 행 됨 에 따라 기포 가 점차 상승 하 다.    이 정렬 과 종 에서 알 수 있 듯 이 5 개의 수 는 실제 4 라운드 만 거치 면 된다.실천 에 의 하면 n 개의 수 는 최대 n-1 라운드 정렬 이 필요 하 다 는 것 을 증명 한다.
    3.거품 정렬 프로그램 은 다음 과 같 습 니 다.

for(i=0;i<10;i++)
for(j=0;j<10-i;j++)
     if(a[j]<a[j+1])
   {t=a[j];a[j]=a[j+1];a[j+1]=t;}
이 프로그램 세그먼트 에 입력 부분 과 프로그램 세그먼트 에 정렬 된 출력 을 추가 합 니 다.프로그램의 개선:
   4.알고리즘 개선:
위의 정렬 과정 을 통 해 알 수 있 듯 이 이미 정렬 된 그룹의 수 나 적은 라운드 수 를 거치 면 이 수 를 다 배열 할 수 있 지만 순환 은 계속 진행 해 야 한다.이렇게 디자인 된 프로그램 은 많은 시간 을 낭비 하기 때문에 이 알고리즘 을 우 리 는 다시 설계 할 수 있다. 수 정 된 과정 은 다음 과 같다.

for(i=0;i<10&&!swap;i++)
{
swap=1;
for(j=0;j<10-I;j++)
     if(a[j]<a[j+1])
       {t=a[j];a[j]=a[j+1];a[j+1]=t;swap=0;}
}
둘째,정렬 선택
    1.정렬 의 기본 사상:첫 번 째 숫자 부터 시작 하여 첫 번 째 숫자 와 다른 숫자 를 비교 하고 첫 번 째 숫자 보다 크 면 위 치 를 교환 합 니 다.그렇지 않 으 면 교환 하지 않 습 니 다.그러면 첫 번 째 비 교 를 통 해 우 리 는 최대 치 를 첫 번 째 위치 에 놓 은 다음 에 두 번 째 숫자 를 찾 을 수 있 습 니 다.이렇게 순서대로 내 려 가면 전체 수의 정렬 을 할 수 있 습 니 다.n 개 수 는 최대 n-1 라운드 정렬 이 필요 하 다 는 것 을 증명 합 니 다.        2.정렬 과정 예:
외부 순환
1 라운드
2 라운드
삼 륜
사 륜
내부 순환
다섯 개 수 를 네 번 비교 하 다
4 개 수 비교 3 회.
3 개 비교 2 회.
두 개 수 를 한 번 비교 하 다
7
5
8
6
9
 
1 회
두 번
세 번
네 번
1 회
두 번
세 번
1 회
두 번
1 회
7
5
8
6
9
8
5
7
6
9
8
5
7
6
9
9
5
7
6
8
9
7
5
6
8
9
7
5
6
8
9
8
5
6
7
9
8
6
5
7
9
8
7
6
5
9
8
7
6
5
 
가장 큰 수 는 9 를 찾 고,나머지 4 개 는 큰 수 를 찾는다.
차 대수 8 을 찾 고 나머지 3 개 를 찾 아 라.
7.찾 아 라,나머지 2 개 는 찾 아 라.
마지막 두 번 을 비교 해서 정렬 을 선택 하 는 것 은 거품 이 생기 는 것 보다 이해 하기 쉽 고 프로그램 작성 도 비교적 쉽다.

for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
     if(a[i]<a[j])
   {t=a[i];a[i]=a[j];a[j]=t;}
정렬 을 선택 하 는 것 에 대해 우 리 는 문 제 를 볼 수 있다.예 를 들 어 1 차 정렬 에서 우리 가 찾 아야 할 것 은 9 가 최대 치 이기 때문에 다른 교환 은 전혀 진행 할 필요 가 없다.다른 각 라운드 에 이런 상황 이 존재 하기 때문에 우 리 는 이런 상황 을 취소 할 방법 을 강구 할 수 있다.즉,우리 가 진정 으로 찾 은 최대 치 의 위 치 를 다시 교환 하 는 것 이다.

for(i=0;i<10;i++)
{ p=i;
for(j=i+1;j<10;j++)
     if(a[p]<a[j])
       p=j;
    if(p!=i)
{t=a[i];a[i]=a[j];a[j]=t;}
}
이러한 알고리즘 은 개선 을 거 친 후에 이 문 제 를 잘 해결 했다.
3.정렬 삽입
1.정렬 기본 사상 을 삽입 합 니 다.이 숫자 가 첫 번 째 숫자 에 비 교 된 것 이 확실 하 다 면 첫 번 째 숫자 앞 에 놓 아 라.그러면 일반적인 상황 에서 정렬 법 을 삽입 하여 정렬 하 는 한 그룹의 수 에 대해 먼저 첫 번 째 수 를 선택 하여 이미 정렬 된 그룹의 수로 할 수 있다.그 다음 에 두 번 째 를 정확 한 위치 에 두 고 프로그램의 작성 은 다음 과 같 습 니 다.

for(i=1;i<10;i++)//i 0 1 。 。
for(j=i;j>0;j--)
     if(a[j]<a[j-1])
   {t=a[j];a[j]=a[j-1];a[j-1]=t;}
이 프로그램 에 대해 서도 수정 해 야 할 부분 이 있 습 니 다.상기 프로그램의 정렬 도 실제 적 으로 교환 사상 을 바탕 으로 정렬 할 수 있 고 진정한 의미 의 정렬 도 할 수 있 습 니 다.즉,대기 순서 의 수 를 먼저 꺼 낸 다음 에 삽입 해 야 할 위 치 를 찾 아 찾 은 후에...삽입 할 위치 에 있 는 데 이 터 를 모두 뒤로 이동 시 키 고 원래 배열 할 데 이 터 를 임시 변수 에 꺼 냈 습 니 다.그리고 이 데 이 터 를 정확 한 여가 위치 에 삽입 하면 됩 니 다.그러면 교환 을 바탕 으로 하 는 삽입 정렬 에 대해 위 치 를 찾 지 못 하기 전에 교환 을 했 기 때문에 프로그램 개선 도 할 수 있 습 니 다.그러면 이 프로그램의 개선 은 교환 횟수 를 줄 일 수 없습니다.만약 에 위 치 를 찾 아서 교환 하면 원래 의 정렬 결 과 를 어 지 럽 혔 을 것 이라는 것 을 알 기 때문에 위 치 를 찾 고 위 치 를 비 우 며 요 소 를 넣 는 몇 가지 절차 만 찾 을 수 있 습 니 다.

main()
{
int i,j,t,a[]={12,11,2,3,6,67,89,0,1,3};
   for(i=1;i<10;i++)
   {t=a[i];
j=i-1;
while(j>=0&&t>a[i])
     {a[j+1]=a[j];
      j--;
}
    a[j+1]=t;  
 for(i=0;i<10;i++)
   printf("%d ",a[i]);
   printf("/n");
}
이상 은 몇 가지 정렬 방법 에 대해 연 구 했 습 니 다.정렬 문제 에 대해 프로그램 디자인 에서 매우 중요 한 내용 이기 때문에 에서 중요 한 내용 으로 깊이 있 는 설명 을 했 습 니 다.우 리 는 여기 서 간단 한 연 구 를 해서 C 언어 를 준비 하 는 초보 자 나 C 언어 프로 그래 밍 을 공부 하 는 애호가 들 이 사용 하고 있 습 니 다.

좋은 웹페이지 즐겨찾기