네 가지 기본 알고리즘

2680 단어

8가지 기본 알고리즘과 코드 설명(기본값은 작은 것부터 큰 것까지 정렬)


거품 정렬은 무질서한 구역에서 서로 인접하여 키 간의 비교와 위치를 기록하는 교환을 통해 키의 가장 작은 기록을 기포처럼 점차적으로 위로'수면'까지 떠오른다.
- 시간 복잡도가 가장 좋은 경우: 순서가 정연하면 n회만 비교할 수 있다.그러므로 O(n)의 최악의 경우: 역순으로 질서정연하면 비교(n-1)+(n-2)+...+1이 필요하기 때문에 O(N*N) 코드를 보여 준다.
public void Merge(int[] str)  //    
    {
        int temp;
        for(int i=1;istr[j+1])
                {
                    temp=str[j];
                    str[j]=str[j+1];
                    str[j+1]=temp;
                }
            }
        }
    }

선택 정렬
먼저 정렬되지 않은 서열에서 가장 작은 원소를 찾아 정렬 서열의 시작 위치에 저장한 다음, 나머지 정렬되지 않은 원소에서 가장 작은 원소를 계속 찾은 다음 정렬 서열의 끝에 놓는다.모든 요소가 정렬될 때까지 이렇게 유추합니다.구체적인 방법은 가장 작은 요소와 정렬되지 않은 부분의 첫 번째 교환을 선택하여 서열의 앞부분을 질서정연하게 하는 것이다.시간의 복잡도가 가장 좋은 경우: 0번을 교환하지만 매번 가장 작은 요소를 찾아야 하기 때문에 대략 NN번을 반복해야 하기 때문에 O (NN) 이다.교환 횟수 감소!최악의 경우 평균: O(N*N) 코드 데모
public void selectMerge(int[] str)
    {
        for(int i=0;istr[j])
                {
                    temp=str[min];
                    str[min]=str[j];
                    str[j]=temp;
                }
            }
        }
    }

3 정렬 직접 삽입(정렬 삽입)
한 번에 하나의 요소 K를 선택하여 이전에 순서가 정해진 부분 A[1.i]에 삽입할 때마다 삽입 과정에서 K는 순서대로 A[1.i]의 요소와 뒤로 비교됩니다.만약에 A[x]>=K를 발견하면 K를 A[x]의 뒤에 삽입하고 삽입하기 전에 원소-시간 복잡도가 가장 좋은 경우: 순서가 질서정연하고 n회만 비교하고 이동할 필요가 없다.따라서 시간 복잡도가 O(n)의 최악의 경우: 역순서가 질서정연하다. 그러면 모든 원소는 n번을 비교해야 한다. 모두 n개의 원소가 있기 때문에 실제 복잡도는 O(n)이다.­2) 평균: O(n)­2) 코드 데모
void insertmerge(int[] arr)
    {
        for(int i=1;i=0 && arr[j]>temp)   //                    
            {
                arr[j+1]=arr[j];
                j--;        
            }
            arr[j+1]=temp;
        }
    }

4빠른 정렬
그것의 기본 사상은 한 차례의 정렬을 통해 정렬할 데이터를 독립된 두 부분으로 분할하고 그 중 일부의 모든 데이터는 다른 부분의 모든 데이터보다 작다는 것이다. 그리고 이 방법에 따라 이 두 부분의 데이터를 각각 신속하게 정렬하면 전체 정렬 과정은 돌아가며 전체 데이터가 질서정연한 서열이 될 수 있다.간단하게 말하면 기준수를 찾는 것이다. 만약에 첫 번째라면 데이터의 양쪽 끝에서부터 두루 훑어본다. 만약에 한쪽이 기준서보다 크고 다른 한쪽이 기준수보다 작다면 이 두 데이터를 바꾸면 양쪽이 마주칠 때 완전한 두루 훑어보기를 끝낸다.
코드 데모
void quicksort(int left,int right) 
{ 
    int i,j,t,temp; 
    if(left>right) 
       return; 

    temp=a[left]; //temp         
    i=left; 
    j=right; 
    while(i!=j) 
    { 
                   //     ,         
                   while(a[j]>=temp && i

좋은 웹페이지 즐겨찾기