交换排序
(1)冒泡排序
#include<stdio.h> #include<iostream> using namespace std; void P(int a[],int n) { for(int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; } void bubblesort(int a[],int len) { int flag=true; for(int i=0; i<len&&flag; i++) { flag=false; for(int j=i+1; j<len; j++) { if(a[i]>a[j]) { int tmp=a[i]; a[i]=a[j]; a[j]=tmp; flag=true; } } } } int main() { int a[]= {8,5,0,3,7,1,2}; P(a,7); bubblesort(a,7); P(a,7); return 0; }时间复杂度:O（n2）(2)快速排序
#include<stdio.h> #include<iostream> using namespace std; void P(int a[],int n) { for(int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; } void quick_sort(int s[],int l,int r) { if(l<r) { int i=l,j=r,x=s[l]; while(i<j) { while(i<j&&s[j]>x) j--; if(i<j) s[i++]=s[j]; while(i<j&&s[i]<x) i++; if(i<j) s[j--]=s[i]; } s[i]=x; quick_sort(s,l,i-1); quick_sort(s,i+1,r); } } int main() { int a[]= {10,9,8,7,6,5,4,3,2,1}; P(a,10); quick_sort(a,0,9); P(a,10); return 0; }时间复杂度：O(nlog2(n))
选择排序
(1)简单选择排序
#include<stdio.h> #include<iostream> using namespace std; void P(int a[],int n) { for(int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; } void selectsort(int a[],int len) { for(int i=0; i<len-1; i++) { int min=i; for(int j=i+1; j<len; j++) { if(a[j]>a[min]) { min=j; } } if(min!=i) swap(a[i],a[min]); } } int main() { int a[]= {8,5,0,3,7,1,2}; P(a,7); selectsort(a,7); P(a,7); return 0; }时间复杂度:O(n2)(2)堆排序
①建大堆（降序）
#include<iostream> using namespace std; void P(int a[],int n) { for(int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; } void AdjustDown(int arr[],int i,int n) { int j=i*2+1; while(j<n) { if(j+1<n&&arr[j]>arr[j+1]) j++; if(arr[i]<arr[j]) break; swap(arr[i],arr[j]); } } void MakeHeap(int arr[],int n) { int i=0; for(int i=n/2-1; i>=0; i--) { AdjustDown(arr,i,n); } } void HeapSort(int arr[],int len) { int i=0; MakeHeap(arr,len); for(int i=len-1; i>=0; i--) { swap(arr[i],arr[0]); AdjustDown(arr,0,i); } } int main() { int a[]= {8,5,0,3,7,1,2}; P(a,7); HeapSort(a,7); P(a,7); return 0; }时间复杂度：O(nlog2n)
②建小堆（升序）
#include<iostream> using namespace std; void P(int a[],int n) { for(int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; } void AdjustDown(int arr[],int i,int n) { int j=i*2+1; while(j<n) { if(j+1<n&&arr[j]<arr[j+1]) j++; if(arr[i]>arr[j]) break; swap(arr[i],arr[j]); } } void MakeHeap(int arr[],int n) { int i=0; for(int i=n/2-1; i>=0; i--) { AdjustDown(arr,i,n); } } void HeapSort(int arr[],int len) { int i=0; MakeHeap(arr,len); for(int i=len-1; i>=0; i--) { swap(arr[i],arr[0]); AdjustDown(arr,0,i); } } int main() { int a[]= {8,5,0,3,7,1,2}; P(a,7); HeapSort(a,7); P(a,7); return 0; }插入排序
(1)直接插入排序
#include<stdio.h> #include<iostream> using namespace std; void P(int a[],int n) { for(int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; } void insertsort(int a[],int len) { for(int i=1; i<len; i++) { int tmp=a[i]; int j=i-1; while(a[j]<tmp&&j>=0) { a[j+1]=a[j]; j--; } a[j+1]=tmp; } } int main() { int a[]= {8,5,0,3,7,1,2}; P(a,7); insertsort(a,7); P(a,7); return 0; }时间复杂度：O(n2/4) 最好：O(n)(2)折半插入排序
#include<stdio.h> #include<iostream> using namespace std; void P(int a[],int n) { for(int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; } void insertsort(int a[],int len) { for(int i=1; i<len; i++) { int tmp=a[i]; int start=0,end=i-1; while(start<=end) { int mid=(start+end)/2; if(a[mid]<tmp) { end=mid-1; } else { start=mid+1; } } for(int j=i-1; j>=end; j--) a[j+1]=a[j]; a[end+1]=tmp; } } int main() { int a[]= {8,5,0,3,7,1,2}; P(a,7); insertsort(a,7); P(a,7); return 0; }时间复杂度：O(n)(3)希尔排序
#include<stdio.h> #include<iostream> using namespace std; void P(int a[],int n) { for(int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; } void shellsort(int arr[],int len) { int i,j; int increment=len; int key; while(increment>1) { increment=increment/3+1; for(int i=increment; i<len; i++) { key=arr[i]; j=i-increment; while(j>=0) { if(key>arr[j]) { int tmp=arr[j]; arr[j]=key; arr[j+increment]=tmp; } j=j-increment; } } } } int main() { int a[]= {8,5,0,3,7,1,2}; P(a,7); shellsort(a,7); P(a,7); return 0; }归并排序
#include<stdio.h> #include<iostream> using namespace std; void P(int a[],int n) { for(int i=0; i<n; i++) cout<<a[i]<<" "; cout<<endl; } void mergearray(int a[],int first,int mid,int last,int temp[]) { int i=first,j=mid+1; int m=mid,n=last; int k=0; while(i<=m&&j<=n) { if(a[i]<=a[j]) temp[k++]=a[i++]; else temp[k++]=a[j++]; } while(i<=m) { temp[k++]=a[i++]; } while(j<=m) { temp[k++]=a[j++]; } for(int i=0; i<k; i++) { a[first+i]=temp[i]; } } void mergesort(int a[],int first,int last,int temp[]) { if(first<last) { int mid=(first+last)/2; mergesort(a,first,mid,temp); mergesort(a,mid+1,last,temp); mergearray(a,first,mid,last,temp); } } int main() { int a[]= {8,5,0,3,7,1,2}; P(a,7); int temp[10]; mergesort(a,0,6,temp); P(a,7); return 0; }时间复杂度:O（nlog2(n)）
