冒泡排序 快速排序 直接插入排序 二分插入排序 希尔排序 选择排序 堆排序 归并排序
#include <iostream> #include<cstdlib> using namespace std; const int N=6; int n=5; int arr[N]={0,5,2,6,9,4}; void p(){ for(int i=1;i<=n;i++){ cout<<arr[i]<<" "; } cout<<endl; } void merge_sort(int l, int r){ int *t=(int *)malloc((r+1)*sizeof(int)); for(int i=l;i<=r;i++){ t[i]=arr[i]; } int m=(l+r)/2; int i=l,j=m+1,k=l; for(;i<=m && j<=r;k++){ if(t[i]<t[j]){ arr[k]=t[i++]; }else{ arr[k]=t[j++]; } } while(i<=m){ arr[k++]=t[i++]; } while(j<=r){ arr[k++]=t[j++]; } } void merge(int l, int r){ if(l<r){ int m=(l+r)/2; merge(l,m); merge(m+1,r); merge_sort(l,r); } } int pivot(int l, int r){ int p=l; arr[0]=arr[l]; while(l<r){ while(l<r && arr[r]>arr[0]){ r--; } arr[l]=arr[r]; while(l<r && arr[l]<arr[0]){ l++; } arr[r]=arr[l]; } arr[l]=arr[0]; return l; } void my_q_sort(int l, int r){ if(l<r){ int p=pivot(l,r); my_q_sort(l,p-1); my_q_sort(p+1,r); } } void my_adjust_heap(int index, int len){ int key=arr[index]; int k=index; int i=index*2; for(;i<=len;i*=2){ if(i+1<=len && arr[i]<arr[i+1]){ i++; } if(arr[k]>arr[i]){ break; }else{ arr[k]=arr[i]; k=i; } } arr[i/2]=key; } void build_heap(int len){ for(int i=len/2;i;i--){ my_adjust_heap(i,len); } } void my_heap_sort(int len){ build_heap(len); for(int i=len;i;i--){ cout<<arr[1]<<" "; swap(arr[1],arr[i]); my_adjust_heap(1,i-1); } } void b_sort(){ for(int i=1;i<n;i++){ for(int j=1;j<=n-i;j++){ if(arr[j]>arr[j+1]){ swap(arr[j],arr[j+1]); } } } } void select_sort(){ for(int i=1;i<n;i++){ int index=i; for(int j=i+1;j<=n;j++){ if(arr[j]<arr[index]){ index=j; } } swap(arr[i],arr[index]); } } void insert_sort(){ for(int i=2;i<=n;i++){ if(arr[i]<arr[i-1]){ arr[0]=arr[i]; int j=i-1; for( ;j && arr[0]<arr[j];j--){ arr[j+1]=arr[j]; } arr[j+1]=arr[0]; } } } void b_insert_sort(){ for(int i=2;i<=n;i++){ if(arr[i]<arr[i-1]){ arr[0]=arr[i]; int l=1,r=i-1; while(l<=r){ int m=(l+r)/2; if(arr[0]<=arr[m]){ r=m-1; }else{ l=m+1; } } for(int j=i;j>r+1;j--){ arr[j]=arr[j-1]; } arr[r+1]=arr[0]; } } } void shell_sort(int len){ for(int dk=len/2;dk;dk/=2){ for(int i=dk+1;i<=len;i++){ if(arr[i]<arr[i-dk]){ arr[0]=arr[i]; int j=i-dk; for( ;j && arr[0]<arr[j];j-=dk){ arr[j+dk]=arr[j]; } arr[j+dk]=arr[0]; } } } } int main(){ b_insert_sort(); p(); return 0; }