#include <stdio.h>
#include <stdlib.h>
void swap(int* p1,int* p2){
int tmp=*p1;
*p1=*p2;
*p2=tmp;
}
void printArray(const int* array,int size){
for(int i=0;i<size;i++)
printf("%d ",array[i]);
printf("\n");
}
void selectionSort(int* array,int size){
int minv,min;
for(int i=0;i<size-1;i++){
minv=array[i];
min=i;
for(int j=i+1;j<size;j++){
if (array[j]<minv)
{
minv=array[j];
min=j;
}
}
if(min-i) swap(&array[i],&array[min]);
printf("%d: ",i);
printArray(array,6);
}
}
void insertionSort(int* array,int size){
int x;
for(int i=1,j;i<size;i++){
x=array[i];
for(j=i;j>0 && array[j-1]>x;j--){
array[j]=array[j-1];
}
array[j]=x;
printf("%d: ",i);
printArray(array,size);
}
}
void merge(int* array,int* tmp,int left,int mid,int right){
int leftend,ti,t;
leftend=mid-1;
t=ti=left;
while(left<=leftend && mid<=right){
if(array[left]<=array[mid]) tmp[ti++]=array[left++]; // 稳定排序
else tmp[ti++]=array[mid++];
}
while(left<=leftend) tmp[ti++]=array[left++];
while(mid<=right) tmp[ti++]=array[mid++];
for(int i=t;i<=right;i++)
array[i]=tmp[i];
}
void msort(int* array,int* tmp,int left,int right){
if(left>=right) return;
int mid=(left+right)/2;
msort(array,tmp,left,mid);
msort(array,tmp,mid+1,right);
merge(array,tmp,left,mid+1,right); // merge two parts
}
void mergeSort(int* array,int size){
int* tmp;
tmp=(int*)malloc(sizeof(int)*size);
if(!tmp) return;
msort(array,tmp,0,size-1);
free(tmp);
}
int main(){
int array[]={5,4,3,2,999,1,0,-100};
// printArray(array,6);
// printf("\n------selectionSort------\n");
// selectionSort(array,6);
// printf("\n------insertionSort------\n");
// insertionSort(array,6);
printf("%d\n",sizeof(array)/sizeof(int));
mergeSort(array,sizeof(array)/sizeof(int));
printArray(array,sizeof(array)/sizeof(int));
return 0;
}
