데이터 구조 - 8 대 정렬 알고리즘 c 언어 구현
67343 단어 데이터 구조
삽입, 힐, 선택, 거품, 쌓 기, 빠 른 배열, 병합, 계수 c 언어 실현, 그리고 그 시간, 공간 복잡 도와 안정성 분석
#include
if(array[begin]>array[end])
return begin;
else
return end;
}
} else{
//begin>=mid
if(array[mid]>array[end])
return mid;
else{
//begin>=mid end>=mid
if(array[begin]<array[end] )
return begin;
else
return end;
}
}
}
int partion(int* array, int begin, int end){
//
int mid=getMid(array,begin,end);
Swap(array,mid,begin);// ，
int key=array[begin];
while(begin<end){
while(begin<end&&array[end]>=key)
end--;
array[begin]=array[end];
while(begin<end&&array[begin]<=key)
begin++;
array[end]=array[begin];
}
array[begin]=key;
return begin;
}
int partion2(int* array, int begin, int end){
//hora
int key=array[begin];
int start=begin;
while(begin<end){
while(begin<end&&array[end]>=key)
end--;
while(begin<end&&array[begin]<=key)
begin++;
Swap(array,begin,end);
}
Swap(array,begin,start);
return begin;
}
int partion3(int* array, int begin, int end){
//
int prev=begin;//
int cur=prev+1;//
int key=array[begin];
while(cur<=end){
if(array[cur]<key&&++prev!=cur)
Swap(array,cur,prev);
cur++;
}
Swap(array,begin,prev);
return prev;
}
void quickSort(int* array, int begin, int end){
if(begin>=end)
return;
int keyPos=partion(array,begin,end);
quickSort(array,begin,keyPos-1);
quickSort(array,keyPos+1,end);
}
//
void quickSortNoR(int* array,int n){
Stack st;
stackInit(&st,10);
if(n>1){
stackPush(&st,n-1);
stackPush(&st,0);
}
while(stackEmpty(&st)!=1){
int begin=stackTop(&st);
stackPop(&st);
int end=stackTop(&st);
stackPop(&st);
//
int keyPos=partion(array,begin,end);
// ：
// ：keyPos+1--end
if(keyPos+1<end){
stackPush(&st,end);
stackPush(&st,keyPos+1);
}
// ：begin--keyPos
if(begin<keyPos-1){
stackPush(&st,keyPos-1);
stackPush(&st,begin);
}
}
}
//
void quickSortNoR2(int* array,int n){
Queue q;
queueInit(&q);
if(n>1){
queuePush(&q,0);
queuePush(&q,n-1);
}
while(queueEmpty(&q)!=1){
int begin=queueFront(&q);
queuePop(&q);
int end=queueFront(&q);
queuePop(&q);
//
int keyPos=partion(array,begin,end);
// ，
// begin--keyPos-1
if(begin<keyPos-1){
queuePush(&q,begin);
queuePush(&q,keyPos-1);
}
// keyPos+1--end
if(keyPos+1<end){
queuePush(&q,keyPos+1);
queuePush(&q,end);
}
}
}
//
// ：O(nlgn)
// ：O(n)
// ：
// ：begin--mid mid+1--end
void merge(int*array,int* tmp,int begin,int mid,int end){
int idx=0,i;
int begin1=begin,end1=mid,begin2=mid+1,end2=end;
while(begin1<=end1&&begin2<=end2){
if(array[begin1]<array[begin2])
tmp[idx++]=array[begin1++];
else
tmp[idx++]=array[begin2++];
}
while(begin1<=end1)
tmp[idx++]=array[begin1++];
while(begin2<=end2)
tmp[idx++]=array[begin2++];
for(i=0;i<idx;i++){
//
array[i+begin]=tmp[i];
}
}
void mergeSortR(int* array,int* tmp,int begin,int end){
if(begin<end){
int mid=begin+(end-begin)/2;
//
mergeSortR(array,tmp,begin,mid);
mergeSortR(array,tmp,mid+1,end);
merge(array,tmp,begin,mid,end);
}
}
void mergeSort(int* array,int n){
if(n>1){
int* tmp=(int*)malloc(sizeof(int)*n);
mergeSortR(array,tmp,0,n-1);
free(tmp);
}
}
//
void mergeSortNoR(int* array,int n){
if(n<=1)
return;
int* tmp=(int*)malloc(sizeof(int)*n);
int k=1,i;
while(k<n){
//
for(i=0;i<n;i+=2*k){
int begin=i;
int mid=i+k-1;
if(mid>=n-1)
continue;
int end=i+2*k-1;
if(end>=n)
end=n-1;
merge(array,tmp,begin,mid,end);
}
k*=2;
}
}
//
// ：O(max(n,range))
// ：O(range)
// ：
void countSort(int* array,int n){
//
int i;
int min=array[0],max=array[0];
for(i=1;i<n;i++){
if(array[i]<min)
min=array[i];
if(array[i]>max)
max=array[i];
}
int range=max-min+1;
int* countArr=(int*)malloc(sizeof(int)*range);
memset(countArr,0,sizeof(int)*range);
for(i=0;i<n;i++){
countArr[array[i]-min]++;
}
int idx=0;
for(i=0;i<range;i++){
while(countArr[i]--){
array[idx++]=i+min;
}
}
free(countArr);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
