정렬 을 삽입 하 는 세 가지 방법

1. 직접 정렬 삽입 1. 평균 시간 복잡 도 는 O (n ^ 2) 2. 가장 좋 은 상황 은 O (n) 이다. 3. 최 악의 경우 O (n ^ 2) 4. 공간 복잡 도 는 O (1)
알고리즘 구현:

/*
 *      
 */

#include

#define MaxSize 100

/*
 *a       ，length     
 */
void inSort(int a[] , int length) ;

/*
 *         
 */
void displayArray(int a[] , int length) ;

void main()
{
    int a[MaxSize] , length , i ;
    printf("Please input the length of the array : 
") ;
    scanf("%d" , &length) ;

    //         
    for(i = 0 ; i < length ; i++)
    {
        scanf("%d" , &a[i]) ;
    }

    printf("Before sort... 
") ;
    displayArray(a , length) ;

    inSort(a , length) ;

    printf("After sort... 
") ;
    displayArray(a , length) ;
}

void inSort(int a[] , int length)
{
    //      
    int temp ;
    int i , j ;             
    for(i = 1 ; i < length ; i++)
    {
        temp = a[i] ;
        j = i - 1 ;
        while(temp < a[j] && j >= 0)
        {
            a[j + 1] = a[j] ;           
            j-- ;
        }
        a[j + 1] = temp ;
    }
}

void displayArray(int a[] , int length)
{   
    int i ;
    for(i = 0 ; i < length ; i++)
    {
        printf("%4d ", a[i]);
    }
    printf("
") ;
}

2. 반절 삽입 정렬 1. 평균 시간 복잡 도 는 O (n ^ 2) 2. 가장 좋 은 상황 은 O (nlogn) 이다. 3. 최 악의 경우 O (n ^ 2) 4. 공간 복잡 도 는 O (1)
알고리즘 구현:

/*
 *      
 */

#include

#define MaxSize 100

/*
 *a       ，length     
 */
void binSort(int a[] , int length) ;

/*
 *         
 */
void displayArray(int a[] , int length) ;

void main()
{
    int a[MaxSize] , length , i ;
    printf("Please input the length of the array : 
") ;
    scanf("%d" , &length) ;

    //         
    for(i = 0 ; i < length ; i++)
    {
        scanf("%d" , &a[i]) ;
    }

    printf("Before sort... 
") ;
    displayArray(a , length) ;

    binSort(a , length) ;

    printf("After sort... 
") ;
    displayArray(a , length) ;
}

void binSort(int a[] , int length)
{
    int i , j , mid , low , high , temp ;
    for(i = 1 ; i < length ; i ++)
    {
        low = 0 ;
        high = i - 1 ;
        temp = a[i];
        while(low <= high)
        {
            mid = (low + high) / 2 ;
            if(temp < a[mid])
            {
                high = mid - 1 ;
            }else{
                low = mid + 1 ;
            }
        }
        for(j = i - 1 ; j >= low ; j--)
        {
            a[j + 1] = a[j] ;
        }
        a[low] = temp ;
    }   
}

void displayArray(int a[] , int length)
{   
    int i ;
    for(i = 0 ; i < length ; i++)
    {
        printf("%4d ", a[i]);
    }
    printf("
") ;
}

3. 힐 정렬 1. 평균 시간 복잡 도 는 O (n ^ 1.5) 4. 공간 복잡 도 는 O (1)
알고리즘 구현:

/*
 *    
 */

#include

#define MaxSize 100

/*
 *      
 *a      ，lengh     ，delta     ，length1        
 */
void shellSort(int a[] , int lengh , int delta[] , int length1) ;

/*
 *        
 */
void shellInsert(int a[] , int length , int delta) ;

/*
 *       
 */
void displayArray(int a[] , int length) ;

void main()
{
    int a[MaxSize] , length , i ;
    int delta[MaxSize] , length1 ;

    printf("Please input the length of the array : ") ;
    scanf("%d" , &length) ;

    //         
    for(i = 0 ; i < length ; i++)
    {
        scanf("%d" , &a[i]) ;
    }

    //         
    printf("Please input the delta's length : ") ;
    scanf("%d" , &length1) ;

    //         
    for(i = 0 ; i < length1 ; i++)
    {
        scanf("%d" , &delta[i]) ;
    }

    printf("Before sort... 
") ;
    displayArray(a , length) ;

    shellSort(a , length , delta , length1) ;

    printf("After sort... 
") ;
    displayArray(a , length) ;
}

void shellSort(int a[] , int length , int delta[] , int length1)
{
    int i ;
    for(i = length1 - 1 ; i >= 0 ; i--)
    {
        shellInsert(a , length , delta[i]) ;
    }
}

void shellInsert(int a[] , int length , int delta)
{
    int i , j , temp ;
    for(i = delta ; i < length ; i++)
    {
        temp = a[i] ;
        j = i - delta ;
        while(temp < a[j] && j >= 0)
        {
            a[j + delta] = a[j] ;
            j -= delta ;
        }
        a[j + delta] = temp ;
    }
}   

void displayArray(int a[] , int length)
{   
    int i ;
    for(i = 0 ; i < length ; i++)
    {
        printf("%4d ", a[i]);
    }
    printf("
") ;
}

정렬 을 삽입 하 는 세 가지 방법

좋은 웹페이지 즐겨찾기