字典序法說明：
字典序列算法是一種非遞歸算法。而它正是STL中Next_permutation的實(shí)現(xiàn)算法。
它的整體思想是讓排列成為可遞推的數(shù)列，也就是說從前一狀態(tài)的排列，可以推出一種新的狀態(tài)，直到最終狀態(tài)。比如說，最初狀態(tài)是12345，最終狀態(tài)是54321。
1.最初狀態(tài)為12345，從最后面向前面比較，因?yàn)?>4,所以從4后面的序列中找出一個(gè)比4大，但是比在4后面的序列中最小的數(shù)，因?yàn)橹挥?，所有將4和5調(diào)換位置，結(jié)果為12354.
2.將原來4后面的序列進(jìn)行倒置，因?yàn)楝F(xiàn)在只有1個(gè)4，倒置后還是12354.
3.已12354為基礎(chǔ)，繼續(xù)上面的步驟進(jìn)行操作，下一序列的生成步驟如下：
12354(5>3) -> 12354(4,5序列中最小但是比3大的是4) -> 12453(調(diào)換4和3) -> 12435（將5,3倒置）

#include <stdio.h>
#include <ctype.h>
#include <malloc.h>
 
static void swapNum(int i, int j, int* intArray, int num);
static int getSmallestButGreatThanIndex(int* intArray, int num, int j, int i);
static void invertIntArray(int i, int* intArray, int num);
static void prtIntArray(int* intArray, int num);
 
int main(int argc,char* argv[]){
    int num = 0;
    int* intArray = NULL;
    int i = 0;
    int j = 0;
     
    //檢查參數(shù)，必須是2個(gè)
    if(argc != 2){
        printf("there must be one parameter!\n");
        goto FINALLY;
    }
     
    //檢查參數(shù)，參數(shù)必須是數(shù)字
    char* ptr = argv[1];
    while(*ptr != '\0'){
        if(isdigit(*(ptr++)) == 0){
            printf("please input a numble!\n");
            goto FINALLY;
        }
    }
     
    //將參數(shù)轉(zhuǎn)換成int型
    num = atoi(argv[1]);
    intArray = (int*)malloc(sizeof(int) * num);
    //初始化數(shù)組:1,2,3,4,5,6......
    for(i=0; i<num; i++){
        intArray[i] = i+1;
    }
     
    //打印下原始數(shù)組
    printIntArray(intArray, num);
    //從數(shù)組最后面往前比較
    for(i=num-1,j=num-2; i>=1 && j>=0; i--,j--){
        //如果右邊數(shù)的比左邊數(shù)的大
        if(intArray[i] > intArray[j]){
            //將左邊的數(shù)與右邊數(shù)組中最小但是比左邊的數(shù)大的數(shù)交換
            swapNum(i, j, intArray, num);
            //將左邊數(shù)右邊的數(shù)組序列倒置
            invertIntArray(i, intArray, num);
            //將整個(gè)數(shù)組打印
            printIntArray(intArray, num);
            //繼續(xù)從數(shù)組的最后面往前面比較
            i = num;
            j = num - 1;
        }
    }
     
FINALLY:
    if(intArray != NULL){
        free(intArray);
        intArray = NULL;
        }
    return 0;
}
 
static void swapNum(int i, int j, int* intArray, int num){
    int swapi = getSmallestButGreatThanIndex(intArray, num, j, i);
    int temp = intArray[j];
    intArray[j] = intArray[swapi];
    intArray[swapi] = temp;
}
 
static int getSmallestButGreatThanIndex(int* intArray, int num, int j, int i){
    int m = 0;
    int swapi = 0;
    int smallest = num + 1;
    for(m = i; m<num; m++){
        if(intArray[m] > intArray[j] && intArray[m] < smallest){
            swapi = m;
            smallest = intArray[m];
        }
    }
    return swapi;
}
 
static void invertIntArray(int i, int* intArray, int num){
    int m;
    int n;
    int temp;
    for(m=i, n=num-1; (m-n)<0; m++,n--){
        temp = intArray[m];
        intArray[m] = intArray[n];
        intArray[n] = temp;
    }
}
 
static void printIntArray(int* intArray, int num){
    int i;
    for(i=0; i<num; i++){
        printf("%d ",intArray[i]);
    }
    printf("\n");
}
 

標(biāo)簽： swap

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。