C. 빠 른 배열 알고리즘 실현

학교 다 닐 때 배 운 빠 른 배열 알고리즘 은 제대로 보지 도 않 고 언어 로 이 루어 지지 도 않 았 다.지금 마침 알고리즘 을 보충 하려 고 스스로 실현 을 썼 다.그의 기본 사상 은 한 번 의 정렬 을 통 해 정렬 할 데 이 터 를 독립 된 두 부분 으로 나 누 는 것 이다. 그 중에서 일부분 의 모든 데 이 터 는 다른 부분의 모든 데이터 보다 작다. 그 다음 에 이 방법 에 따라 이 두 부분의 데 이 터 를 각각 신속하게 정렬 하고 전체 정렬 과정 을 거 쳐 재 귀적 으로 진행 하여 전체 데 이 터 를 질서 있 는 서열 로 바 꿀 수 있다.
제 가 사용 한 제자리 정렬 은 코드 가 짧 고 논리 가 간단 하 며 주석 도 많이 추 가 했 습 니 다.(코드 나 주석 에 문제 가 있 는 것 을 발견 하면 알려 주세요) 코드 가 이렇게 길 어서 놀 라 지 마 세 요. 사실 그 중 2 / 3 은 주석 입 니 다.

#include "stdio.h"
/*
 *     
 *    begin   end            。
 *  ,    13, 17, 12      :
 * show(array, 3, 0, 2);
 * show(array, 3, 1, 2);
 * show(array, 3, 1, 1);
 *     :
 * 13 17 12
 * 17 12
 * 17
 */
void show(int array[], long maxlen, int begin, int end)
{
    int i = 0;

    /*               */
    for(i=0; i<begin; i++)
        printf(" ");

    for(i=begin; i<=end; i++)
        printf("%4d", array[i]);

    printf("
");
}
/*
 *        。
 *     1         。
 *     0               。
 *                    。
 */
int swap(int *i, int *j)
{
   int temp;

    if(*i == *j)
        return 0;

    temp = *i;
    *i = *j;
    *j = temp;

    return 1;
}

/*
 *       
 *       begin  (  begin ) end(  end)          
 */
void quicksort(int array[], int maxlen, int begin, int end)
{
    int i, j;

    if(begin < end) {
        /*               ，           begin+1    */
        i = begin + 1;
        j = end;

        /*
         *       ：array[begin]      array[begin+1]   array[end]
         *           ，             
         *
         *     while(i != j)     ，       i<=j    i j 
         *        1        i>j   
         */
        while(i < j) {
            /*         array[begin]，       j      ,    j      */
            if(array[i] > array[begin]) {
                if(swap(&array[i], &array[j]) == 1)
                    show(array, maxlen, begin, end); /*    begin   end        */
                j--;
            }
            /*    i       ,        。*/
            else
                i++;
        }
        /*
         *    : i=j, array         
         *   array[begin+1] ~ array[i-1]     array[begin]
         *   array[i+1] ~ array[end]     array[begin]
         *
         *   :   array[begin]   array      
         *       array           ,
         *       array[begin]          。
         *
         *    array      array[begin]，   array[begin]    i  
         *      array[begin]   i      
         */
        if (array > array[begin])
            i--;

        /*   array[begin]    i       */
        if(swap(&array[begin], &array[i]) == 1)
            /*    begin   end        */
            show(array, maxlen, begin, end);

        /*         i        */
        quicksort(array, maxlen, begin, i);
        quicksort(array, maxlen, j, end);
    }
}
int main(int argc, char* argv[])
{
    int array[10] = {49, 38, 65, 97, 48, 13, 27, 11, 56, 45};
    int maxlen = sizeof(array) / sizeof(int);

    show(array, maxlen, 0, maxlen-1); /*        */
    quicksort(array, maxlen, 0, maxlen-1);
    show(array, maxlen, 0, maxlen-1); /*        */
    getchar();

    return 0;
}