（一）冒泡排序（稳定） 1.基本思想：每一趟从数组的头部开始，两两做比较，根据大小进行位置的交换，直到最后一个数到达末尾，即该数为此趟的最大值，在循环中继续重复此操作，最终得到排序好的序列 2.时间复杂度： 最优的情况也就是开始就已经排序好序了，那么就可以不用交换元素了，则时间花销为：[ n(n-1) ] / 2；所以最优的情况时间复杂度为：O( n^2 )；
最差的情况也就是开始的时候元素就是逆序的，那么每一次排序都需要交换元素，则时间花销为：[3n(n-1) ] / 2；所以最差的情况时间复杂度为：O( n^2 )； 综上所述： 最优时间复杂度：O(n^2); 最差时间复杂度：O(n^2); 平均时间复杂度：O(n^2);
3.空间复杂度（空间复杂度就是在交换元素时那个临时变量所占的内存空间）： 最优的空间复杂度就是开始元素顺序已经排好了，则空间复杂度为：0； 最差的空间复杂度就是开始元素逆序排序了，则空间复杂度为：O(n)； 平均的空间复杂度为：O(1)；
4.代码实现：
void bubble_sort(int a[], int n) { int t; for(int i=0;i<n-1;i++) for (int j = 0; j < n-1-i; j++) if (a[j] > a[j + 1]) { t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } }（二）选择排序（不稳定） 1.基本思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。 2.时间复杂度： 比较时间：T=(n-1)+(n-2)+…+1=n(n-1)/2 交换时间：全部有序，则交换次数为0；全部逆序，则交换次数为n-1 综上所述： 最优时间复杂度：O(n^2); 最差时间复杂度：O(n^2); 平均时间复杂度：O(n^2); 3.空间复杂度：同冒泡排序 4.代码实现：
void select_sort(int a[], int n) { int i,j,min; for (i = 0; i < n - 1; i++) { min = i; for (j = i + 1; j < n; j++) { if (a[j] < a[min]) min = j; } int t; t = a[i]; a[i] = a[min]; a[min] = t; } }（三）插入排序（稳定） 1.基本思想：将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。） 2.时间复杂度：O(n^2); 3.空间复杂度:O(1); 4.代码实现：
void insert_sort(int a[], int n) { int i,j,key; for (i = 1; i < n; i++) { key = a[i]; j = i - 1; while (j >= 0 && key < a[j]) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } }（四）快速排序（不稳定） 1.基本思想：在数组中选一个基准数（通常为数组第一个）； 将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边； 对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序 2.时间复杂度：O(nlogn); 3.空间复杂度:O(nlogn); 4.代码实现：
void quick_sort(int a[], int begin, int end) { if (begin < end) { int i = begin, j = end,temp=a[begin]; while (i < j) { while (i<j&&a[j]>temp) j--; a[i] = a[j]; while (i < j&&a[i]<=temp) i++; a[j] = a[i]; } a[i] = temp; quick_sort(a, begin, i - 1); quick_sort(a, i + 1, end); } }（五）堆排序（不稳定） 1.基本思想： 堆的定义如下：n个元素的序列{k1,k2，···，kn}当且满足以下关系时，称之为堆 对于一个小顶堆，若在输出堆顶的最小值之后， 使剩余n-1个元素的序列再次筛选形成一个堆，再输出次小值，由此反复进行，便能得到一个有序的序列，这个过程就称之为堆排序。 2.时间复杂度：O(nlogn); 3.空间复杂度:O(1); 4.代码实现：
#include <iostream> const int N =10; using namespace std; void HeapAdjust(int a[],int s,int m)//一次筛选的过程 { int rc,j; rc=a[s]; for(j=2*s;j<=m;j=j*2)//通过循环沿较大的孩子结点向下筛选 { if(j<m&&a[j]<a[j+1]) j++;//j为较大的记录的下标 if(rc>a[j]) break; a[s]=a[j];s=j; } a[s]=rc;//插入 } void HeapSort(int a[],int n) { int temp,i,j; for(i=n/2;i>0;i--)//通过循环初始化顶堆 { HeapAdjust(a,i,n); } for(i=n;i>0;i--) { temp=a[1]; a[1]=a[i]; a[i]=temp;//将堆顶记录与未排序的最后一个记录交换 HeapAdjust(a,1,i-1);//重新调整为顶堆 } } void print(int a[],int n) { for(int i=1;i<=n;i++) cout<<a[i]<<" "; } int main() { int n,i; cin>>n; int a[N]; for(i=1;i<=n;i++) { cin>>a[i]; } HeapSort(a,n); print(a,n); return 0; }（六）归并排序（稳定） 1.基本思想：分而治之 2.时间复杂度：O(nlogn); 3.空间复杂度:O(n); 4.代码实现：
#include<iostream> using namespace std; template<typename T> void merge(T a[], int first, int mid, int last, T temp[]) { int i = first,j=mid+1; int m = mid,n=last,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<=n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[i+first] = temp[i]; } template<typename T> void mergesort(T a[], int first, int last, T temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); mergesort(a, mid + 1, last, temp); merge(a, first, mid, last, temp); } } void main() { int a[8] = { 8,3,2,6,7,1,5,4 }, temp[8] = { 0 }; mergesort(a, 0, 7, temp); for (int i = 0; i < 8; i++) cout << a[i] << " "; cout << endl; system("pause"); }