C++기본 알고리즘 거품 법,교환 법,선택 법,코드 집합 실현

1.거품 법:
이것 은 가장 원시 적 이 고 모두 가 알 고 있 는 가장 느 린 알고리즘 이다.그의 이름 의 유래 는 그것 의 일이 거품 처럼 보이 기 때문이다.

#include <iostream.h> 
void BubbleSort(int* pData,int Count) 
{ 
int iTemp; 
for(int i=1;i<Count;i++) { 
for(int j=Count-1;j>=i;j--) {
if(pData[j]<pData[j-1]) { 
iTemp = pData[j-1]; 
pData[j-1] = pData[j]; 
pData[j] = iTemp;
}
}
} 
} 
void main() { 
int data[] = {10,9,8,7,6,5,4}; 
BubbleSort(data,7); 
for (int i=0;i<7;i++) 
cout<<data<<" ";
cout<<"
"; 
} 

역순(최 악의 경우)1 차:10,9,8,7->10,9,9,7,8->10,7,9,8->7,9,8->7,9,9,8(교환 3 차)2 차:7,10,9,9,8->7,8,9->7,8,10,9(교환 2 차)1 차:7,8,10,9->7,9,8,8,8,9,9,10(교환 1 차)순환 횟수:6 차 교환 횟수:6 차 기타:1 차:1 차:8,10,7,7,7,9->8,7,9-9(교환 2 차)1 차:7,7,7,7,7,10,10,9,9,9,9,10(교환 1 차)순환 횟수:6 회)2 차:7,8,10,9->7,8,10,9->7,8,10,9(교환 0 회)1 차:7,8,10,9->7,8,9,10(교환 1 회)순환 횟수:6 차 교환 횟수:3 차 위 에서 우 리 는 프로그램 세그먼트 를 제 시 했 는데 지금 우 리 는 이 를 분석 했다.여기 서 우리 알고리즘 성능 에 영향 을 주 는 주요 부분 은 순환 과 교환 이다.분명히 횟수 가 많 을 수록 성 에너지 가 떨어진다.위의 프로그램 에서 우 리 는 순환 의 횟수 가 1+2+...+n-1 이라는 것 을 알 수 있다.공식 으로 쓰 면 1/2*(n-1)*n.지금 주의 하 세 요.우 리 는 O 방법의 정 의 를 내 립 니 다.상수 K 와 출발점 n0 이 존재 하면 n>=n0 이 있 을 때 f(n)<=K*g(n)이 있 으 면 f(n)=O(n)가 있 습 니 다.지금 우 리 는 1/2*(n-1)*n,K=1/2,n0=1,g(n)=n*n 을 볼 때 1/2*(n-1)*n<=1/2*n*n=K*g(n).그래서 f(n)=O(g(n)=O(n*n).그래서 우리 프로그램 순환 의 복잡 도 는 O(n*n)입 니 다.다시 보고 교환 해.프로그램 뒤에 있 는 시 계 를 보면 두 가지 상황 의 순환 이 같 고 교환 이 다르다 는 것 을 알 수 있다.사실 교환 자체 와 데이터 소스 의 질서 정 도 는 매우 큰 관 계 를 가진다.데이터 가 역순 에 있 을 때 교환 횟수 는 순환 과 같다(매번 순환 판단 할 때마다 교환).복잡 도 는 O(n*n)이다.데이터 가 정렬 되면 교환 이 없 을 것 입 니 다.복잡 도 는 O(0)이다.무질서 할 때 중간 상태 에 있다.바로 이런 이유 로 우 리 는 보통 순환 횟수 를 통 해 알고리즘 을 비교 합 니 다.2.교환 법:교환 법의 절차 가 가장 뚜렷 하고 간단 하 며 매번 현재 의 요소 로 그 후의 요소 와 비교 하고 교환 합 니 다.

#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData)
{
iTemp = pData;
pData = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data<<" ";
cout<<"
";
}

역순(최 악의 경우)1 라운드:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(교환 3 회)2 라운드:7,10,9,8->7,9,10,8->7,8,10,9(교환 2 회)1 라운드:7,8,10,9->7,8,9,9,9,9,10(교환 1 회)순환 횟수:6 회 교환 횟수:6 회
기타:1 라운드:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(교환 1 회)2 라운드:7,10,8,9->7,8,10,9->7,8,10,9(교환 1 회)1 라운드:7,8,10,9->7,8,9,9,10,10(교환 1 회)순환 횟수:6 회 교환 횟수:3 회
실행 중인 표를 보면 교환 은 거의 거품 처럼 엉망 이 었 다.사실은 그렇다.순환 횟수 는 거품 과 마찬가지 로 1/2*(n-1)*n 이기 때문에 알고리즘 의 복잡 도 는 여전히 O(n*n)이다.우 리 는 모든 상황 을 제시 할 수 없 기 때문에 그들 이 교환 에 있어 서도 마찬가지 로 나쁘다 는 것 을 직접 알려 줄 수 밖 에 없다.p\#부제\#e\#
3.선택 방법:
이제 우 리 는 마침내 한 가지 희망 을 볼 수 있다.선택 법,이런 방법 은 약간의 성능 을 향상 시 켰 다.(어떤 경우)이런 방법 은 우리 의 인위적인 정렬 습관 과 유사 하 다.데이터 에서 가장 작은 것 과 첫 번 째 값 을 교환 하고 절약 하 는 부분 에서 가장 작은 것 과 두 번 째 교환 을 선택 하여 이렇게 반복 한다.

#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i<Count-1;i++)
{
iTemp = pData;
iPos = i;
for(int j=i+1;j<Count;j++)
{
if(pData[j]<iTemp)
{
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData;
pData = iTemp;
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data<<" ";
cout<<"
";
}

역순(최 악의 경우)1 차:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(교환 1 차)2 차:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(교환 1 차)1 차:7,8,9,10->(iTemp=9)7,8,9,10(교환 0 차)순환 횟수:6 차 교환 횟수:2 차
기타:1 차:8,10,7,9->(iTemp= 8)8,10,7,9->(iTemp= 7)8,10,7,9->(iTemp=7)7,10,8,9(교환 1 차)2 차:7,10,8,9->(iTemp= 8)7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,10,9(교환 1 차)1 차:7,8,10,8,10,10,9->(iTemp= 9)7,8,9,9,10(교환 1 차)순환 횟수:6 차 아 쉬 움 교환 횟수:3 차 아 쉬 운 것 은 알고리즘 이 필요 한 순환 횟수:3 차 아 쉬 움 은 알고리즘 이 필요 한 순환 여전히 1/2*(n-1)*n.그래서 알고리즘 의 복잡 도 는 O(n*n)이다.우 리 는 그의 교환 을 보 러 왔 다.매번 외부 순환 이 한 번 만 교환 되 기 때문이다.그래서 f(n)<=n 그래서 우 리 는 f(n)=O(n)가 있다.따라서 데이터 가 어 지 러 울 때 일정한 교환 횟수 를 줄 일 수 있다.4.삽입 법:삽입 법 이 비교적 복잡 하 다.그의 기본 적 인 작업 원 리 는 카드 를 뽑 아서 앞의 카드 에서 해당 하 는 위 치 를 찾 아 삽입 한 다음 에 다음 장

#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
iTemp = pData;
iPos = i-1;
while((iPos>=0) && (iTemp<pData[iPos]))
{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data<<" ";
cout<<"
";
}

을 계속 하 는 것 이다.
역순(최 악의 경우)1 라운드:10,9,8,7->9,10,8,7(교환 1 회)(순환 1 회)2 라운드:9,10,8,7->8,9,10,7(교환 1 회)1 라운드:8,9,10,7->7,8,9,10(교환 1 회)순환 횟수:6 회 교환 횟수:3 회
기타:1 라운드:8,10,7,9->8,10,7,9(교환 0 회)(순환 1 회)2 라운드:8,10,7,9->7,8,10,9(교환 1 회)(순환 2 회)1 라운드:7,8,10,9->7,8,9,10(교환 1 회)순환 횟수:4 회 교환 횟수:2 회
위의 마지막 행위 분석 은 사실상 가상 을 초래 했다.우 리 는 이런 알고리즘 이 간단 한 알고리즘 중에서 가장 좋다 고 생각 하지만 사실은 그렇지 않다.순환 횟수 가 고정 되 지 않 지만 우 리 는 O 방법 을 사용 할 수 있 기 때문이다.위의 결 과 를 보면 순환 횟수 f(n)<=1/2*n*(n-1)<=1/2*n*n 을 알 수 있다.그래서 그 복잡 도 는 여전히 O(n*n)이다.현재 교환 을 보면 외관상 교환 횟수 는 O(n)(유도 유사 선택 법)이지 만 우 리 는 매번 내부 순환 과 같은 횟수 의'='작업 을 해 야 한다.정상 적 인 한 번 의 교환 에 우 리 는 세 번 의'='이 필요 한데 여기 가 분명히 좀 많아 서 우 리 는 시간 을 낭비 했다.마지막 으로 저 는 개인 적 으로 간단 한 정렬 알고리즘 중에서 선택 법 이 가장 좋다 고 생각 합 니 다.정렬 삽입

#include <iostream> 
using namespace std;
void coutstream(int a[],int n){
for(int i=0;i!=n;i++)
cout<<a<<" ";
}
void insertsort(int a[],int n){
int temp;
for(int i=1;i<n;i++)
{
int j=i;
temp=a; //  a        
while(j>0&&temp<a[j-1])
{
a[j]=a[j-1];
j--;
}
a[j]=temp;
}
}
int main()
{
int a[5]={1,6,4,8,4};
insertsort(a,5);//    
coutstream(a,5);//
return 0;
}

2.고급 정렬 알고리즘:고급 정렬 알고리즘 에서 우 리 는 이것 만 소개 할 것 이 고 현재 내 가 알 고 있 는(내 가 본 자료 중)가장 빠 른 것 이다.그것 의 일 은 여전히 이 진 트 리 처럼 보인다.우선 중간 값 middle 프로그램 에서 배열 의 중간 값 을 사용 한 다음 에 그것 보다 작은 것 을 왼쪽 에 놓 고 큰 것 을 오른쪽 에 놓 습 니 다(구체 적 인 실현 은 양쪽 에서 찾 아 한 쌍 을 찾 은 후에 교환 하 는 것 입 니 다).그리고 양쪽 에 이 과정 을 각각 사용한다.1.빠 른 정렬:

#include <iostream.h>
void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //    
do{
while((pData<middle) && (i<right))//          
i++; 
while((pData[j]>middle) && (j>left))//          
j--;
if(i<=j)//      
{
//  
iTemp = pData;
pData = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//           ，   （    ）
//       (left<j)，     
if(left<j)
run(pData,left,j);
//       (right>i)，     
if(right>i)
run(pData,i,right);
}
void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<<data<<" ";
cout<<"
";
}

여기 서 저 는 행위 에 대한 분석 을 하지 않 았 습 니 다.이것 은 매우 간단 하기 때문에 우 리 는 직접 알고리즘 을 분석 합 니 다.먼저 우 리 는 가장 이상 적 인 상황 을 고려 합 니 다.1.배열 의 크기 는 2 의 멱 입 니 다.이렇게 나 누 면 항상 2 로 나 눌 수 있 습 니 다.2 의 k 제곱,즉 k=log 2(n)로 가정 합 니 다.2.매번 우리 가 선택 한 값 이 중간 값 이 어야 배열 이 등분 할 수 있다.1 층 재 귀,n 차 순환,2 층 순환 2*(n/2).그러나 당신 은 이런 상황 이 발생 할 확률 이 얼마나 높다 고 생각 합 니까?허허,너 는 이 문 제 를 전혀 걱정 할 필요 가 없다.실천 은 대부분의 경우 빠 른 정렬 이 가장 좋다 는 것 을 증명 한다.이 문제 가 걱정 된다 면 더미 정렬 을 사용 할 수 있 습 니 다.이것 은 안정 적 인 O(log 2(n)*n)알고리즘 이지 만 보통 빠 른 정렬 보다 속도 가 느 립 니 다.
3.기타 정렬 1.양 방향 거품:일반적인 거품 은 단 방향 이 고 여 기 는 양 방향 이다.즉,역방향 작업 을 해 야 한 다 는 것 이다.코드 가 복잡 해 보 여서 자세히 정리 해 보면 알 수 있 듯 이 이리 저리 흔 들 리 는 방식 이다.이 코드 를 쓴 작 가 는 이렇게 하면 거품 이 일어 나 는 기초 위 에서 약간의 교환 을 줄 일 수 있다 고 생각한다.어쨌든 나 는 이것 이 재 미 있 는 코드 라 고 생각한다.볼 만하 다.

#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do
{
//     
for(int i=right;i>=left;i--)
{
if(pData<pData[i-1])
{
iTemp = pData;
pData = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//     
for(i=left;i<right+1;i++)
{
if(pData<pData[i-1])
{
iTemp = pData;
pData = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<<data<<" ";
cout<<"
";
}

빠 른 정렬

#include <iostream> 
using namespace std; 
class QuickSort 
{ 
public: 
void quick_sort(int* x,int low,int high) 
{ 
int pivotkey; 
if(low <high) 
{ 
pivotkey=partion(x,low,high); 
quick_sort(x,low,pivotkey-1); 
quick_sort(x,pivotkey+1,high); 
} 
} 
int partion(int* x,int low,int high) 
{ 
int pivotkey; 
pivotkey=x[low]; 
while(low <high) 
{ 
while (low <high&&x[high]>=pivotkey) 
--high; //  while        
x[low]=x[high]; 
while (low <high&&x[low] <=pivotkey) 
++low; //  while        
x[high]=x[low]; 
} 
x[low]=pivotkey; 
return low; 
} 
}; 
int main() 
{ 
int x[10]={52,49,80,36,14,58,61,97,23,65}; 
QuickSort qs; 
qs.quick_sort(x,0,9); 
cout <<"         ：" <<endl; 
for (int i=0;i <10;i++) 
{ 
printf("%d ",x); 
} 
return 0; 
}

2.SHELL 정렬
이 순 서 는 매우 복잡 해서 프로그램 을 보면 알 수 있다.우선 점차 줄 어드 는 보폭 이 필요 하 다.여기 서 우리 가 사용 하 는 것 은 9,5,3,1(마지막 보폭 은 반드시 1)이다.작업 원 리 는 먼저 9-1 개 요소 의 모든 내용 을 정렬 한 다음 에 같은 방법 으로 5-1 개 요소 의 정렬 을 다음 으로 유추 하 는 것 이다.

#include <iostream.h>
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int iTemp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step;
s = -k;
for(int j=k;j<Count;j++)
{
iTemp = pData[j];
w = j-k;//  step      
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp<pData[w]) && (w>=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<<data<<" ";
cout<<"
";
}

프로그램 이 좀 골 치 아파 보인다.하지만 어렵 지 않 습 니 다.s==0 의 블록 을 제거 하면 훨씬 쉬 워 집 니 다.여 기 는 0 걸음 길이 로 프로그램 이상 을 일 으 키 지 않도록 쓰 는 코드 입 니 다.이 코드 는 매우 볼 만하 다.이 알고리즘 의 이름 은 발명자 의 이름 D.L.SHELL 때문이다.참고 자료 에 따 르 면"복잡 한 수학 적 원인 으로 인해 2 의 멱 차 보폭 을 사용 하지 않 으 면 알고리즘 효율 을 낮 출 수 있다"고 말 했다.또한 알고리즘 의 복잡 도 는 n 의 1.2 차 멱 이다.마찬가지 로 매우 복잡 하고'이 책의 토론 범 위 를 넘 어 섰 다'는 이유 로(나 도 과정 을 모른다)우 리 는 결과 만 있 을 뿐이다.거품 정렬 성능 최적화 판\#include

using namespace std;
void maopao(int *list,int n) 
{ 
int i=n,j,temp; 
bool exchange;//        ，    
for(i=0;i<n;i++) 
{
exchange=false;
for (j=0;j<n-i-1;j++) 
{ 
if (list[j]>list[j+1]) 
{ 
temp=list[j]; 
list[j]=list[j+1]; 
list[j+1]=temp; 
exchange=true; 
}
} 
if (!exchange) 
{ 
return; 
} 
}
}
int main()
{
int a[7]={32,43,22,52,2,10,30};
maopao(a,7);
for(int i=0;i<7;i++)
cout<<a<<" ";
return 0;
}