//插入类排序:直接插入排序,希尔排序,折半插入排序
//交换类排序:冒泡排序,快速排序
//归并类排序:归并排序,
//选择类排序:简单选择排序,堆排序
//直接插入排序 平均时间复杂度:O(n^2) 稳定
void insert(int a[],int n)
{
int t,i,j;
for(i=1;i<n;i++)
{
t=a[i];
for(j=i-1;a[j]>t && j>=0;j--)
{
a[j+1]=a[j];
}
a[j+1]=t;
}
}
//折半插入排序(直接插入排序优化) 二分思想 O(n^2) 稳定
void binaryinsert(int a[],int n)
{
int i,j,low,high,mid,t;
for(i=1;i<n;i++)
{
t=a[i];
low=0,high=i-1;
while(low<=high)
{
mid = (high + low) >> 1;
if(t<a[mid]) high=mid-1;
else low=mid+1;
}
for(j=i-1;j>high;j--) a[j+1]=a[j];
a[high+1]=t;
}
}
//希尔排序(带有步长的直接插入排序),
//当d=1时即为直接插入排序) O(n^1.3) 不稳定 仅顺序表
void shell(int a[],int n)
{
int d,i,j,t;
for(d=n/2;d>=1;d/=2)
{
for(i=d;i<n;i++)
{
if(a[i]<a[i-d])
{
t=a[i];
for(j=i-d;j>=0 && a[j]>t;j-=d) a[j+d]=a[j];
a[j+d]=t;
}
}
}
}
//冒泡排序 O(n^1.3) 稳定 顺序表,链表均可
void bubblesort(int a[],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
int t=a[j];a[j]=a[j+1];a[j+1]=t;
}
}
}
}
//快速排序 O(nlogn) 不稳定
void quicksort(int a[],int l,int r)
{
if(l>=r) return;
int i=l-1,j=r+1,x=a[(l+r)>>1];
while(i<j)
{
while(a[i]<x) i++;
while(a[j]>x) j--;
if(i<j) swap(a[i],a[j]);
}
quicksort(a,l,j);
quicksort(a,j+1,r);
}
//归并排序 稳定 O(nlogn)
void merge(int a[], int l, int r)
{
if(l>=r) return;
int mid= (l + r) >> 1;
merge(a,l,mid);
merge(a,mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid && j<=r)
{
if(a[i]<=a[j]) b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid) b[k++]=a[i++];
while(j<=r) b[k++]=a[j++];
for(i=l,j=0;i<=r;j++,i++) a[i]=b[j];
}
//简单选择排序 不稳定 O(n^2)
void select(int a[],int n)
{
for(int i=0;i<n;i++)
{
int idx=i;
for(int j=i;j<n;j++)
{
if(a[j]<a[idx]) idx=j;
}
if(idx!=i)
{
int t=a[i];a[i]=a[idx];a[idx]=t;
}
}
}
int main()
{
int a[9]={89,45,54,29,90,34,68,30,20};
int n=9;
select(a,n);
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}