[정렬] 예제: 샤 오 흥 책 사기 (통 정렬, 거품 정렬, 빠 른 정렬)

문제: n 개의 정 수 를 입력 하여 무 게 를 제거 하고 작은 것 부터 큰 것 까지 정렬 하여 출력 합 니 다.운행 시간 을 1 초 로 제한 하 다.
해: 첫 번 째 방법: n 개의 도서 의 ISBN 번 호 를 다시 한 다음 에 작은 것 부터 큰 것 까지 정렬 하고 출력 합 니 다. 예 를 들 어 통 정렬 등 입 니 다.
배럴 정렬
사상: 배열 로 나타 난 도서 번 호 를 기록 하고 존재 하 는 것 은 1 이 며 출력 배열 의 중간 값 이 1 인 배열 아래 에 표 시 됩 니 다.
실현:

#include
int a[101],n; //      ，              

void QuickSort(int low, int high)
{
    int i,j,pviot;
    if(low>high)
        return;
    pviot=a[low];i=low;j=high;
    while(i!=j)
    {
        while(i=pviot)j--;
        a[i]=a[j];
        while(i

시간 복잡 도: O (M + N)
두 번 째 방법: 작은 것 부터 큰 것 까지 정렬 하고 출력 할 때 무 거 운 것 을 제거 합 니 다.
1. 거품 정렬 을 사용 하여 출력 할 때 이 수 a [i] 가 앞의 a [i - 1] 과 같 는 지, 다 르 면 출력 합 니 다.
실현:

#include

int main()
{
    int a[1000],i,j,n,t,x,y=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&t);
        a[i]=t;
    }

    for(i=1;ia[j+1])
            {
                x=a[j];
                a[j]=a[j+1];
                a[j+1]=x;
            }
        }
    }

    printf("%d ",a[1]);
    for(i=2;i<=n;i++)
        if(a[i]!=a[i-1])
        {
            y++;
            printf("%d ",a[i]);
        }

    printf("
%d ",y+1);
}

시간 복잡 도: O (n)²）
2. 빠 른 정렬 사용

//      ，    

#include

int a[1000];

void Quicksort(int low,int high)
{
    int i=low,j=high,pviot=a[low];
    if(i>j)
    {
        return;
    }
    while(i!=j)
    {
        while(i=pviot) j--;
        a[i]=a[j];
        while(i

시간 복잡 도: O (NLogN)
요약: 통 정렬 이 가장 빠르다.