1，冒泡排序
（1）算法思想：从后往前（从前往后）两两比较相邻元素的值，若A[i-1]>A[i],则交换它们，直到序列比较完。完成一次比较后，会把最小值（最大值）交换到序列的第一个位置（最后一个位置）。然后循环进行刚才的操作，注意排序完的元素不在排序。
（2）冒泡排序代码如下：
1 Void BubbleSort(int A[],int A) 2 { 3 for(int i=0;i<n-1;i++) 4 { 5 bool flag=false; //表示本趟冒泡是否发生交换的标志 6 for(int j=n-1;j>i;j--) //一趟冒泡过程 7 { 8 if(A[j-1]>A[j]) //若为逆序 9 { 10 swap(A[j-1],A[j]); //交换 11 flag=true; 12 }
} 13 if(flag==false) //本趟遍历后没有发生交换，说明表已经有序 14 return ; 15 } 16 } 17 18 void swap(int &a,int &b) 19 { 20 int temp=a; 21 a=b; 22 b=temp; 23 }
（3）空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。
（4）时间效率：最好情况下：当初始序列有序时，时间复杂度为O(n)，
最坏情况：当初始序列为逆序时，需要进行n-1次排序，第i次排序需要进行n-i次关键字的比较，而每次比较后都必须移动元素3次来交换元素位置。
从而最坏情况下的时间复杂度为O(n2)，平均时间复杂度也为O(n2).
(5)稳定性：冒泡排序是一种稳定的排序算法。
2，快速排序
（1）算法思想：选取一个元素作为参考标准（一般以首元素为准），通过指针，low,high把小于参考元素的关键字排在左边，大于参考元素的关键字排在右边，第一次排序之后将左边一部分看成一部分，右边看成一部分，在用同样的方法，依次递归直到所有元素排序完成。
（2）代码如下：
1 int Partition(int A[],int low,int high) //一趟划分 2 { 3 int pivot=A[low]; //将第一个元素设为参考元素，对表进行划分 4 while(low<high) //循环跳出条件 5 { 6 while(low<high&&A[high]>=pivot) --high; 7 A[low]=A[high]; //将比参考元素小的元素移到左边 8 while(low<high&&A[low]<=pivot) ++low; 9 A[high]=A[low]; //将比参考元素大的元素移到右边 10 } 11 A[low]=pivot; //将参考元素放到最终位置 12 return low; //返回存放参看元素的最终位置 13 } 14 15 16 void QuickSort(int A[],int low,int high) 17 { 18 if(low<high) //递归条件 19 { 20 int pivotpos=Partition(A,low,high); //划分 21 QuickSort(A,low,pivotpos-1); //对左子表进行递归排序 22 QuickSort(A,pivotpos+1,high); //对右子表进行递归排序 23 } 24 }
（3）空间效率：最好情况O(log2n)，最坏情况，O(n)，平均情况，O(log2n).
（4）时间效率：若初始排序表基本有序或基本逆序时，就得到最坏情况下的时间复杂度为O(n2).
(5)稳定性：快速排序是一种不稳定的排序算法。
快速排序是所有内部排序算法中平均性能最优的排序算法。
原文：https://www.cnblogs.com/lcy-4/p/14905138.html