冒泡排序:
时间复杂度:O(n*n) 空间复杂度:O(1) 稳定性:稳定
#include
#include
#include
#include
using namespace std;
void Bubble_sort(int a[], int n)
{for(int i = 0; i < n-1; ++i){for(int j = 0; j < n-i-1; ++j){if(a[j] > a[j+1])swap(a[j], a[j+1]);}}
}
int main(int argc, char const *argv[])
{int n;cin>>n;int a[n];memset(a, 0, sizeof(a));for(int i = 0; i < n; ++i)cin>>a[i];Bubble_sort(a,n);for(int i = 0; i < n; ++i)cout<
选择排序
时间复杂度:O(n*n) 空间复杂度:O(1) 稳定性:稳定
#include
#include
#include
#include
using namespace std;
void SimeSel_sort(int a[], int n)
{int min;for(int i = 0; i < n-1; ++i){min = i;for(int j = i+1; j <= n-1; ++j){if(a[j] < a[min])min = j;}swap(a[min],a[i]);}
}
int main(int argc, char const *argv[])
{int n;cin>>n;int a[n];memset(a, 0, sizeof(a));for(int i = 0; i < n; ++i)cin>>a[i];SimeSel_sort(a,n);for(int i = 0; i < n; ++i)cout<
插入排序
时间复杂度:O(n*n) 空间复杂度:O(1) 稳定性:稳定
#include
#include
#include
#include
using namespace std;
void insert_sort(int a[], int n)
{int i, j;for(int i = 0; i < n; ++i){if(a[i] < a[i-1]){int temp = a[i];j = i;while(j > 0 && a[j-1] > temp){a[j] = a[j-1];j--;}a[j] = temp;}}
}
int main(int argc, char const *argv[])
{int n;cin>>n;int a[n];memset(a, 0, sizeof(a));for(int i = 0; i < n; ++i)cin>>a[i];insert_sort(a,n);for(int i = 0; i < n; ++i)cout<
希尔排序
时间复杂度:O(n*logn)*(n*logn) 空间复杂度: O(1) 稳定性:不稳定
#include
#include
#include
#include
using namespace std;
void ShellSort(int a[], int n)
{int i,j;int up=n;do{up=up/3+1;for(i=up;i=0&&a[j]>temp;j-=up)a[j+up]=a[j];a[j+up]=temp;}}}while(up>1);
}
int main(int argc, char const *argv[])
{int n;cin>>n;int a[n];memset(a, 0, sizeof(a));for(int i = 0; i < n; ++i)cin>>a[i];ShellSort(a,n);for(int i = 0 ; i < n; ++i)cout<
快速排序
时间复杂度:O(n*logn) 空间复杂度:O(logn) 稳定性:不稳定
#include
#include
#include
#include
using namespace std;
void QuickSort(int a[],int l,int r)
{if(l=x)j--;if(i>n;for(int i=0;i>a[i];QuickSort(a,0,n-1);for(int i=0;i
堆排序
时间复杂度:O(n*logn) 空间复杂度:O(1) 稳定性:不稳定
#include
#include
#include
#include
using namespace std;
void MaxHeapFixDown(int a[],int i, int n)
{int j=2*i-1;int temp=a[i];while(ja[j])break;else{a[i]=a[j];i=j;j=2*i+1;}}a[i]=temp;
}
void HeapSort(int a[],int n)
{for(int i=n/2-1;i>=0;--i){MaxHeapFixDown(a,i,n);}for(int i=n-1;i>=1;--i){swap(a[i],a[0]);MaxHeapFixDown(a,0,i);}
}int main()
{int n;cin>>n;int a[100]={0};
for(int i=0;i>a[i];
HeapSort(a,n);
for(int i=0;i
归并排序
时间复杂度:O(n*logn) 空间复杂度:O(n) 稳定性:稳定
#include
#include
#include
#include
using namespace std;
void Merge(int a[],int p,int q,int r)
{int i,j,k,n1,n2;int *front,*back;n1=q-p+1;n2=r-q;front=(int *)malloc(n1*sizeof(int));back=(int *)malloc(n2*sizeof(int));for(int i=0;i>n;int a[100]={0};for(int i=0;i>a[i];MergeSort(a,0,n-1);for(int i=0;i