利用交换元素的位置进行排序的方法称作交换排序 冒泡排序： （1）思想（以升序为例）：
比较相邻的元素，如果第一个比第二个大，就交换它们，从开始的第一对到结尾最后一对作相同的工作，第一轮下来会将最大的数冒到最右边，然后区间右边减少一个，重复上述步骤，直到区间缩小为1。
（2）图解： 实现4趟冒泡排序就可将下列数组排为有序。 （3）优化思想：
设置标志位，用来判断该次排序有没有进行数据交换，如果没有进行数据交换，表示剩下的元素已经有序了。不需要再进行冒泡了。
（4）复杂度：
冒泡地一趟排序排n-1次，第二趟n-2，第三次n-3….所以最坏情况下（逆序），时间复杂度为O(n*n). 优化后，虽然一定程度减少了数据的比较次数，在最好情况下（有序），时间复杂度是O(n）。 空间复杂度O(1) 冒泡排序是一种稳定的排序算法
代码实现：
//普通版本 void BubbleSort(int* a,int len) { assert(a); assert(len>0); for(int i = 0;i < len;++i) { for(int j = 0;j < len-i-1;++j) { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); } } } }优化版本：
void BubbleSort(int* a,int len) { assert(a); assert(len>0); bool flag = true;//标志用于判断是否有序 for(int i = 0;i < len;++i)//外循环 { for(int j = 0;j < len-i-1;++j)//内循环，每次循环比较len-i-1次 { if(a[j]>a[j+1]) { swap(a[j],a[j+1]); flag = false; } } if(flag)//如果有序直接跳出 { break; } } } int main() { int arr[7] = {1,9,7,0,3,6,4}; BubbleSort(arr,7); Print(arr,7); }接下来了解一下分治思想： 分治与递归的关系： 很多用到分治方法的算法都用到了递归，但并不是用到了递归算法就是使用了分治算法，分治法也可以由迭代来实现，递归只是算法的实现手段。
快速排序： 复杂度：
最好情况，每次划分区间都将区间平分成两份，此时的时间复杂度为O(N*logN) 最坏情况，每次划分区间，都导致其中一个区间为空，此时的时间复杂度为O(N*N) 空间复杂度为O(logN)
（1）左右指针法：
//快排左右指针法 void Print(int *a,size_t n) { assert(a); for(size_t i = 0;i<n;i++) { cout<<a[i]<<" "; } cout<<endl; } int PartSort1(int *a,int left,int right) { int key = right; while(left<right) { while(left<right && a[left]<=a[key]) ++left; while(left<right && a[right]>=a[key]) --right; swap(a[left],a[right]); } swap(a[left],a[key]); return left; } void QuickSort(int* a,int left,int right)//分治法 子问题求解 { if(left>=right) return; int key = PartSort1(a,left,right); QuickSort(a,left,key-1); QuickSort(a,key+1,right); } int main() { int a[]={1,5,6,2,7,4}; QuickSort(a,0,sizeof(a)/sizeof(a[0])-1); Print(a,sizeof(a)/sizeof(a[0])); return 0; }（2）挖坑法
代码实现：
//快速排序挖坑法 int Sort2(int *a,int left,int right) { int key = a[right];//记录第一个保留的key值 while(left<right) { //左指针向右找比key大的值 while(left < right && a[left] <= key) left++; a[right]=a[left];//找到后将左指针指向的数填入坑 //右指针向左找比key小的值 while(left < right && a[right] >= key) right--; a[left]=a[right]; } a[left] = key;//将key值放入最后一个坑中 return left; } void QuickSort(int arr[],int l,int r) { if(l<r) { int key = Sort1(arr,left,right); QuickSort(arr,l,key-1); QuickSort(arr,key+1,r); } }（3）前后指针法
代码实现：
int PartSort3(int *a,int left,int right) { if(left>=right) return 0; int key = a[right]; int prev = left-1; int cur = left; while(cur<right) { //cur没有找到比key大的数就一直向前走 if(a[cur]<key && (++prev)!=cur) { swap(a[cur],a[prev]);//cur遇到比key小的值，让prev向前走一步并且和cur交换 } ++cur; } swap(a[++prev],a[right]); return prev; }优化： （1）区间元素少到一定个数，进行直接插入排序 快排采用了递归的算法，递归建立栈帧消耗十分大当对小区间进行排序时，反不如直接插入排序更为高效。 （2）三数取中法取得key值下标的位置 给定左右区间的值，计算出中间下标，返回这三个数中不大不小的那个,将该下标的值与最右侧的值进行交换即可。从而尽可能保证划分后的两个区间大小相差不会很大，从而提高了快排的效率。
int Getmid(int *a,int left,int right) { int mid = left+((right-left)>>1); if(a[left]<a[mid]) { if(a[right]<a[left]) return left; else if(a[right]>a[mid]) return mid; else return right; } else { if(a[right]<a[mid]) return mid; else if(a[left]<a[right]) return left; else return right; } } int PartSort1(int *a,int left,int right) { int key = right; swap(a[right],a[Getmid(a,left,right)]); while(left<right) { while(left<right && a[left]<=a[key]) ++left; while(left<right && a[right]>=a[key]) --right; swap(a[left],a[right]); } swap(a[left],a[key]); return left; }（3）非递归实现快速排序 快排的单趟排序都是运用了递归，当数量大的时候可能会遇到栈溢出问题， 递归本就是一种压栈的过程，因此我们可以用库中自带栈来实现非递归的快速排序，从而减少了递归导致的调用函数的开销。 非递归版本的实现：
void QuickSortR(int* a,size_t n) { assert(a); int left = 0; int right = n-1; stack<int> s; s.push(right); s.push(left); while(!s.empty()) { left = s.top(); s.pop(); right = s.top(); s.pop(); int mid = PartSort1(a,left,right); if(left < mid-1) { s.push(mid-1); s.push(left); } if(mid+1 < right) { s.push(right); s.push(mid+1); } } }