정렬 알고리즘 - 정렬 알고리즘 집합
7013 단어 정렬 알고리즘
다음은 구체 적 인 실현 이다.
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 1000000
int Array[N];
int Temp[N];
//1、
void BubbleSort(int a[],int n){
int i,j;
int temp;
int tag;
for(i=n-1;i>0;i--){
tag = 0;
for(j=0;j<i;j++)
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
tag=1;
}
if(tag==0) break;
}
}
//2、
void SimpleInsertSort(int a[],int n){
int i,j,k;
int temp;
for(i=1;i<n;i++){
for(j=0;j<i;j++)
if(a[j]>a[i]){
k=j;
break;
}
if(j==i) continue;
temp=a[i];
for(j=i;j>k;j--)
a[j]=a[j-1];
a[k]=temp;
}
}
//3、
void ShellSort(int a[],int n,int d){
int h,i,j,k;
int temp;
do{
d=d/3+1;
for(h=0;h<d;h++)
for(i=h+d;i<n;i+=d){
for(j=h;j<i;j+=d)
if(a[j]>a[i]){
k=j;
break;
}
if(j==i) continue;
temp=a[i];
for(j=i;j>k;j-=d)
a[j]=a[j-d];
a[k]=temp;
}
}while(d>1);
}
//4、
void SimpleSelectSort(int a[],int n){
int i,j,k;
int temp;
for(i=0;i<n;i++){
temp=a[i];
k=i;
for(j=i+1;j<n;j++)
if(a[j]<temp){
temp=a[j];
k=j;
}
if(k!=i){
temp=a[i];
a[i]=a[k];
a[k]=temp;
}
}
}
//5、
void CreateHeap(int a[],int n){
int i,j;
int temp;
for(i=(n-2)/2;i>=0;i--){
j=2*i+1;
while(j<n){
if(j+1<n&&a[j+1]>a[j])
j++;
if(a[(j-1)/2]<a[j]){
temp=a[(j-1)/2];
a[(j-1)/2]=a[j];
a[j]=temp;
}
else break;
j=2*j+1;
}
}
}
void HeapAdjust(int a[],int n){
int i=0;
int j;
int temp;
while(i<n&&2*i+1<n){
j=2*i+1;
if(j+1<n&&a[j+1]>a[j])
j++;
if(a[i]<a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else break;
i=j;
}
}
void HeapSort(int a[],int n){
int i;
int temp;
CreateHeap(a,n);
for(i=n-1;i>0;i--){
temp=a[i];
a[i]=a[0];
a[0]=temp;
HeapAdjust(a,i);
}
}
//6、
int partition(int a[],int low,int high){
int pivotKey=a[low];
while(low<high){
while(low<high&&pivotKey<=a[high])
high--;
a[low]=a[high];
while(low<high&&a[low]<=pivotKey)
low++;
a[high]=a[low];
}
a[low]=pivotKey;
return low;
}
void QuickSort(int a[],int low,int high){
int pivotTag;
if(low<high){
pivotTag=partition(a,low,high);
QuickSort(a,low,pivotTag-1);
QuickSort(a,pivotTag+1,high);
}
}
//7、
void Merge(int a[],int p,int q,int r){
int i,j;
int *ptr=(int*)malloc((r-p+1)*sizeof(int));
int begin_1,end_1,begin_2,end_2;
begin_1=p;
end_1=q;
begin_2=q+1;
end_2=r;
j=0;
while(begin_1<=end_1&&begin_2<=end_2){
if(a[begin_1]<=a[begin_2]){
ptr[j]=a[begin_1];
begin_1++;
}
else{
ptr[j]=a[begin_2];
begin_2++;
}
j++;
}
while(begin_1<=end_1)
ptr[j++]=a[begin_1++];
while(begin_2<=end_2)
ptr[j++]=a[begin_2++];
for(i=0;i<r-p+1;i++)
a[p+i]=ptr[i];
free(ptr);
}
void MergeSort(int a[],int first,int last){
int mid;
if(first<last){
mid=(first+last)/2;
MergeSort(a,first,mid);
MergeSort(a,mid+1,last);
Merge(a,first,mid,last);
}
}
//8、 (LSD)
int MaxBit(int a[],int n){
int i;
int d=1;
int p=10;
for(i=0;i<n;i++)
while(a[i]>=p){
p*=10;
++d;
}
return d;
}
void RadixSort(int a[],int n){
int i,j,k;
int radix=1;
int d=MaxBit(a,n);
int *ptr=(int*)malloc(n*sizeof(int));
int *count=(int*)malloc(10*sizeof(int));
for(i=1;i<=d;i++){
for(j=0;j<10;j++)
count[j]=0;
for(j=0;j<n;j++){
k=(a[j]/radix)%10;
count[k]++;
}
for(j=1;j<10;j++)
count[j]=count[j-1]+count[j];
for(j=n-1;j>=0;j--){
k=(a[j]/radix)%10;
count[k]--;
ptr[count[k]]=a[j];
}
for(j=0;j<n;j++)
a[j]=ptr[j];
radix*=10;
}
free(ptr);
free(count);
}
int main(void){
int i;
int index;
clock_t first,second;
for(i=0;i<N;i++)
Array[i]=rand()%N;
/*printf(" :
");
for(i=0;i<N;i++)
printf("%d\t",Array[i]);
printf("
");*/
while(1){
for(i=0;i<N;i++)
Temp[i]=Array[i];
printf(" :
");
printf("1---
");
printf("2---
");
printf("3---
");
printf("4---
");
printf("5---
");
printf("6---
");
printf("7---
");
printf("8---
");
scanf("%d",&index);
if(index<1||index>8) break;
first=clock();
switch(index){
case 1: BubbleSort(Temp,N);
break;
case 2: SimpleInsertSort(Temp,N);
break;
case 3: ShellSort(Temp,N,10);
break;
case 4: SimpleSelectSort(Temp,N);
break;
case 5: HeapSort(Temp,N);
break;
case 6: QuickSort(Temp,0,N-1);
break;
case 7: MergeSort(Temp,0,N-1);
break;
default: RadixSort(Temp,N);
}
second=clock();
/*printf(" :
");
for(i=0;i<N;i++)
printf("%d\t",Temp[i]);*/
printf(" :%f
",(double)(second-first)/CLOCKS_PER_SEC);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
WEEK. 01 2022.04.03 TIL정렬(sorting)이란 이름, 학번, 학점 등의 키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 의미함. 정렬 알고리즘은 안정적인 알고리즘과 그렇지 않은 알고리즘으로 나...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.