고전 정렬 알고리즘 - 임 프 정렬 Gnome Sort

4060 단어 gnome
고전 정렬 알고리즘 - 임 프 정렬 Gnome Sort
가장 간단 한 정렬 알고리즘 이 라 고 불 리 며 한 층 의 순환 만 있 습 니 다. 기본 적 인 상황 에서 거품 이 나 고 거품 이 일다 상황 이 발생 하면 다시 튀 어 나 옵 니 다. 이 숫자 를 잘 놓 을 때 까지.
정렬 과정 을 직접 보고 배열 대기 그룹 [6, 2, 4, 1, 5, 9]
먼저 표지 i = 0 을 설계 한 다음 에 처음부터 판단 합 니 다. 언제 (i < 6) 가 성립 되 지 않 고 언제 정렬 이 끝 나 는 지,
그래서 i 의 값 을 어떻게 제어 하 느 냐 가 이 알고리즘 의 관건 이다.
예 를 들 어 대기 배열:
[6 2 4 1 5 9]
[0 1 2 3 4 5]
 
구체 적 인 정렬 과정 을 살 펴 보 겠 습 니 다.
[i = 0] 아무것도 하지 않 을 때 i 를 1 로 늘 리 고 1 이 되 어야 진정한 비 교 를 시작 합 니 다.
교환 전 [6, 2, 4, 1, 5, 9] [i = 0]
교환 후 [6 2 4 1 5 9] [i = 1]
 
[i = 1] 비교 6 과 2, 교환 발생, 교환 i 만 발생 하면 1 감소
교환 전 [6, 2, 4, 1, 5, 9] [i = 1]
교환 후 [2, 6, 4, 1, 5, 9] [i = 0]
 
[i = 0] 또 0 이 야. 아무것도 안 해.
교환 전 [2, 6, 4, 1, 5, 9] [i = 0]
교환 후 [2 6 4 1 5 9] [i = 1]
 
[i = 1] 2 와 6 을 더 비교 하고, 바 꾸 지 않 으 면 1 이 증가한다.
교환 전 [2, 6, 4, 1, 5, 9] [i = 1]
교환 후 [2 6 4 1 5 9] [i = 2]
 
[i = 2] 비교 6 과 4, 교환 발생, 교환 만 하면 1 감소
교환 전 [2, 6, 4, 1, 5, 9] [i = 2]
교환 후 [2, 4, 6, 1, 5, 9] [i = 1]
 
[i = 1] 비교 2 와 4, 교환 하지 않 고 교환 하지 않 으 면 1 증가
교환 전 [2, 4, 6, 1, 5, 9] [i = 1]
교환 후 [2, 4, 6, 1, 5, 9] [i = 2]
 
[i = 2] 4 와 6 을 비교 하고 교환 하지 않 으 면 1 이 증가한다.
교환 전 [2, 4, 6, 1, 5, 9] [i = 2]
교환 후 [2, 4, 6, 1, 5, 9] [i = 3]
 
[i = 3] 비교 6 과 1, 교환, 교환 만 하면 1 감소
교환 전 [2, 4, 6, 1, 5, 9] [i = 3]
교환 후 [2 4 1 6 5 9] [i = 2]
 
[i = 2] 비교 4 와 1, 교환, 교환 만 하면 1 감소
교환 전 [2, 4, 1, 6, 5, 9] [i = 2]
교환 후 [2 1 4 6 5 9] [i = 1]
 
[i = 1] 비교 2 와 1, 교환, 교환 만 하면 1 감소
교환 전 [2 1 4 6 5 9] [i = 1]
교환 후 [1, 2, 4, 6, 5, 9] [i = 0]
 
[i = 0] 아무것도 하지 않 을 때 i 를 1 로 늘 리 고 1 이 되 어야 진정한 비 교 를 시작 합 니 다.
교환 전 [1, 2, 4, 6, 5, 9] [i = 0]
교환 후 [1, 2, 4, 6, 5, 9] [i = 1]
[i = 1] 비교 1 과 2, 교환 하지 않 고 교환 하지 않 으 면 1 증가
[i = 2] 비교 2 와 4, 교환 하지 않 고 교환 하지 않 으 면 1 증가
[i = 3] 비교 4 와 6, 교환 하지 않 고 교환 하지 않 으 면 1 증가
[i = 4] 비교 6 과 5, 교환, 교환 만 하면 1 감소
교환 전 [1, 2, 4, 6, 5, 9] [i = 4]
교환 후 [1, 2, 4, 5, 6, 9] [i = 3]
[i = 3] 4 와 5 를 비교 하고 교환 하지 않 으 면 1 이 증가한다.
[i = 4] 비교 5 와 6, 교환 하지 않 고 교환 하지 않 으 면 1 증가
[i = 5] 비교 6 과 9, 교환 하지 않 고 교환 하지 않 으 면 1 증가
[i = 6] 표현 식 (i < n) 이 성립 되 지 않 습 니 다. 정렬 이 끝 났 습 니 다.
순차 출력 결과: [1, 2, 4, 5, 6, 9]
아래 코드 는 참고 로 제공 합 니 다.
        static void gnome_sort(int[] unsorted)
        {
            int i = 0;
            while (i < unsorted.Length)
            {
                if (i == 0 || unsorted[i - 1] <= unsorted[i])
                {
                    i++;
                }
                else
                {
                    int tmp = unsorted[i];
                    unsorted[i] = unsorted[i - 1];
                    unsorted[i - 1] = tmp;
                    i--;
                }
            }
        }

 
참고 http://blog.csdn.net/winark/article/details/5918944

좋은 웹페이지 즐겨찾기