정렬 알고리즘 총결산(1)

삽입 정렬:
안정시키다
최적 시간 복잡도: O (n) 이 때 수열 순서 배열
최악의 시간 복잡도: O (n^2) 이 때 수열 역순 배열
정렬 사상: 하나의 원소 a를 고정시키고 각각 a 이전의 원소를 비교한다. 만약에 a 이전의 원소가 a보다 크면 원소가 뒤로 이동하고 a를 a보다 작은 원소 뒤에 삽입한다.
삽입 순서를 이해하려면 실제 귀속과 불귀속의 사상은 상반된 과정이고 귀속의 마지막 층은 비귀속 순환의 1층에 해당한다
반복 버전의 삽입 정렬:

#include<stdio.h>
#include<stdlib.h>

void Insert(int *a,int p,int q)
{
    int	key;
	key=a[q+1];
	int j;
	j=q;
	while(j>=0 &&a[j]>key)
	{
		a[j+1]=a[j];
		j--;
	}
	a[j+1]=key;
}

void Recursive_InsertSort(int *a,int p,int q)
{
	if(p<q)
	{
		Recursive_InsertSort(a,p,q-1);
		Insert(a,p,q-1);
	}
}




int main()
{
	int a[10]={1,5,7,9,8,2,6,4,0,3};
	int b[10];
	int i,j,tem;
	Recursive_InsertSort(a,0,10);

	for(i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
	system("pause");
}

반복되지 않은 삽입 정렬

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int a[10]={1,5,7,9,8,2,6,4,0,3};
	int b[10];
	int i,j,tem;
	for(i=1;i<10;i++)
	{
		tem=a[i];
		j=i-1;
		printf("ai1=%d
",a[i]);
			printf("tem1=%d
",tem);
		while(a[j]>tem&&j>=0)   // tem a[i]
		{
			printf("ai=%d
",a[i]);
			printf("tem=%d
",tem);
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=tem;
	}
	for(i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
	system("pause");
}

거품 정렬:
안정시키다
최적 시간 복잡도: O (n^2)
최악의 시간 복잡도: O (n ^2)
거품 정렬 알고리즘의 사상은 매번 순환할 때마다 각각 i...n의 최소값은 교환을 통해 i점에 도달합니다.
반복 버전 거품 정렬 알고리즘:

#include<stdio.h>
#include<stdlib.h>

void Insert(int *a,int p,int q)
{
	int i,j,tem;
	for(i=p;i<q;i++)
	{
		if(a[i-1]>a[i])
		{
			tem=a[i-1];
			a[i-1]=a[i];
			a[i]=tem;
		}
	}

}

void Recursive_BubbleSort(int *a,int p,int q)
{
	if(p<q)
	{
		Insert(a,p,q);
		Recursive_BubbleSort(a,p,q-1);
	}	
}

int main()
{
	int a[10]={5,1,7,9,8,2,6,4,0,3};
	int b[10];
	int i,j,tem;
	Recursive_BubbleSort(a,1,10);
	for(i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
	system("pause");
}

거품 정렬 알고리즘:

#include<stdio.h>
#include<stdlib.h>


void BubbleSort(int *a,int n)
{
	int tem,i,j;
	for(i=0;i<n;i++)
	{
		for(j=n-1;j>i;j--)
		{
			if(a[j]<a[j-1])
			{
				tem=a[j];
				a[j]=a[j-1];
				a[j-1]=tem;
			}
		
		}
	}
}

int main()
{
	int a[10]={1,5,7,9,8,2,6,4,0,3};
	int b[10];
	int i,j,tem;
	BubbleSort(a,10);

	for(i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
	system("pause");
}

정렬 선택:
불안정하다
최적 시간 복잡도: O (n^2)
최악의 시간 복잡도: O (n ^2)
정렬 알고리즘을 선택하는 사상은 매번 순환할 때마다 각각 i...n의 최소값은 교환을 통해 i점에 도달하는데 거품 알고리즘과 달리 거품 알고리즘은 인접 원소와 교환한다.

#include<stdio.h>
#include<stdlib.h>

void SelectSort(int *a,int m,int n)
{
	int i,j,min,tem;
	for(i=m;i<n;i++)
	{
		min=i;
		for(j=i+1;j<n;j++)
		{
			if(a[min]>a[j])
			{
				min=j;
			}
		}
		tem=a[min];
		a[min]=a[i];
		a[i]=tem;
	}
}

int main()
{
	int a[10]={5,1,7,9,8,2,6,4,0,3};
	int b[10];
	int i,j,tem;
	SelectSort(a,0,10);
	for(i=0;i<10;i++)
	{
		printf("%d ",a[i]);
	}
	system("pause");
}