세 가지 전체 정렬 알고리즘 상세 설명
7229 단어 Algorithm
알고리즘 사고: 전체 배열 은 고정 전 i 비트 로 볼 수 있 고 i + 1 위 이후 의 것 을 모두 배열 할 수 있 습 니 다. 예 를 들 어 고정 1 위, 뒤에 n - 1 위의 전체 배열 을 따라 갑 니 다.그러면 n - 1 비트 요소 의 전체 배열 을 해결 하면 n 비트 요소 의 전체 배열 을 해결 할 수 있 고 이런 디자인 은 재 귀 로 쉽게 실현 할 수 있다.
코드 세그먼트 추가:
void permutation1(char* str,int sbegin,int send) //
{
if( sbegin == send) // sbegin = send
{
for(int i = 0;i <= send; i++) //
cout << str[i];
cout << endl;
}
else
{
for(int i = sbegin; i <= send; i++) // sbegin + 1
{
swap(str[i],str[sbegin]); // i sbegin
permutation1(str,sbegin + 1,send);
swap(str[i],str[sbegin]); //
}
}
}2. 전체 배열 의 재 귀 알고리즘
시퀀스 에 중복 되 는 문자 가 있 을 수 있 습 니 다. 출력 을 다시 배열 해 야 할 때 다음 과 같은 방법 을 사용 할 수 있 습 니 다. i 위 가 i + n 위 와 교 환 될 때 i 에서 i + n 위 에 i + n 위 와 같은 문자 가 있 을 수 없습니다 예 를 들 어 23560678 은 3 위 5 와 6 위 6 이 교환 할 때 중간 에 6 이 있 으 면 안 되 고 여기 6 이 있어 서 교환 하지 않 는 다.
코드 세그먼트 추가:
bool comparesub(char* str,int sbegin,int send) // ,[sbegin,send) send
{
for(int i = sbegin; i < send; i++)
if(str[i] == str[send])
return false;
return true;
}
void permutation2(char* str,int sbegin,int send) //
{
if(sbegin == send) // sbegin = send
{
for(int i = 0; i <= send; i++) //
cout << str[i];
cout << endl;
}
else
{
for(int i = sbegin; i <= send; i++)
{
if(comparesub(str,sbegin,i)) // sbeing i
{
swap(str[i],str[sbegin]); // i sbegin
permutation2(str,sbegin + 1,send);
swap(str[i],str[sbegin]); //
}
}
}
}3. 전체 배열 의 중복 제거 비 재 귀 알고리즘
알고리즘 사고: 먼저 정렬 하여 증가 하 는 순 서 를 얻 고 문자열 의 끝 에서 첫 번 째 인접 한 증가 문 자 를 찾 습 니 다. 앞의 수 를 교체 문자 라 고 부 르 고 문자 의 아래 표 지 를 교체 점 이 라 고 부 르 며 이 문자 뒤에서 교체 문자 보다 큰 최소 문 자 를 찾 습 니 다 (증가 관계 가 있 기 때문에 이 수 는 반드시 존재 합 니 다).그리고 교체 점 후의 문자열 을 역 설정 합 니 다.최대 정렬 까지 순환 한 후 역 설정 및 종료 알고리즘
예: 문자열 2568710 먼저 정렬 하여 0125678 에서 인접 한 증가 문 자 를 찾 았 습 니 다. 78. 그 다음 에 7 뒤의 문자 에서 알고리즘 에 맞 는 문 자 를 찾 았 습 니 다. 8. 문자열 0125687 로 교체 한 다음 에 7 뒤의 문자열 을 역 설정 하여 0125687 을 얻 었 습 니 다.
코드 세그먼트 추가:
void Reverse(char* a,char* b) //
{
while(a < b)
{
char tmp = *a;
*a = *b;
*b = tmp;
a++;
b--;
}
}
bool next_permutation3(char* str) //
{
int i;
int slen = strlen(str); //str
for(i = slen - 1; i >= 1; i--) //
{
if(str[i - 1] < str[i])
break;
}
if(!i) // i=0， ，
{
return false; //
}
else
{
char tmp = str[i - 1]; //
int pos = i; //
for(int j = i; j < slen; j++)
{
if(str[j] > tmp && str[j] <= str[pos]) //
pos = j;
}
str[i - 1] = str[pos];
str[pos] = tmp; //
char *p = str + i;
char *q = str + (slen - 1);
Reverse(p,q); //
return true; //
}
}
int qsortcmp(const void * pa,const void * pb) //
{
return *(char*)pa - *(char*)pb; // ，
}
void permutation3(char* str) //
{
qsort(str,strlen(str),sizeof(char),qsortcmp); //
do
{
for(int i = 0; i < strlen(str); i++) //
cout << str[i];
cout << endl;
}while(next_permutation3(str));
}4. 소스 코드
#include
#include
#include
using namespace std;
/*
： i ， i+1 ， ， n-1 。 n-1 n ， 。
*/
void permutation1(char* str,int sbegin,int send) //
{
if( sbegin == send) // sbegin = send
{
for(int i = 0;i <= send; i++) //
cout << str[i];
cout << endl;
}
else
{
for(int i = sbegin; i <= send; i++) // sbegin + 1
{
swap(str[i],str[sbegin]); // i sbegin
permutation1(str,sbegin + 1,send);
swap(str[i],str[sbegin]); //
}
}
}
/*
， ，
i i+n ，i i+n i+n
23560678, 5 6 ， 6， 6
*/
bool comparesub(char* str,int sbegin,int send) // ,[sbegin,send) send
{
for(int i = sbegin; i < send; i++)
if(str[i] == str[send])
return false;
return true;
}
void permutation2(char* str,int sbegin,int send) //
{
if(sbegin == send) // sbegin = send
{
for(int i = 0; i <= send; i++) //
cout << str[i];
cout << endl;
}
else
{
for(int i = sbegin; i <= send; i++)
{
if(comparesub(str,sbegin,i)) // sbeing i
{
swap(str[i],str[sbegin]); // i sbegin
permutation2(str,sbegin + 1,send);
swap(str[i],str[sbegin]); //
}
}
}
}
/*
： ， ， ， ， ( ， )， 。 ，
： 2568710 0125678 ，78， 7 8， 0125687， 7 ， 0125687
*/
void Reverse(char* a,char* b) //
{
while(a < b)
{
char tmp = *a;
*a = *b;
*b = tmp;
a++;
b--;
}
}
bool next_permutation3(char* str) //
{
int i;
int slen = strlen(str); //str
for(i = slen - 1; i >= 1; i--) //
{
if(str[i - 1] < str[i])
break;
}
if(!i) // i=0， ，
{
return false; //
}
else
{
char tmp = str[i - 1]; //
int pos = i; //
for(int j = i; j < slen; j++)
{
if(str[j] > tmp && str[j] <= str[pos]) //
pos = j;
}
str[i - 1] = str[pos];
str[pos] = tmp; //
char *p = str + i;
char *q = str + (slen - 1);
Reverse(p,q); //
return true; //
}
}
int qsortcmp(const void * pa,const void * pb) //
{
return *(char*)pa - *(char*)pb; // ，
}
void permutation3(char* str) //
{
qsort(str,strlen(str),sizeof(char),qsortcmp); //
do
{
for(int i = 0; i < strlen(str); i++) //
cout << str[i];
cout << endl;
}while(next_permutation3(str));
}
int main()
{
char str[] = "1223";
//
// permutation1(str,0,strlen(str) - 1);
// permutation2(str,0,strlen(str) - 1);
permutation3(str);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 수조를 깊이가 가장 낮은 두 갈래 나무로 바꾸다문제 정의: Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height. 생각: 이 문제는 비...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
