一、排序算法的分类
1. 比较排序 VS 非比较排序
是否需要比较两个元素的大小才能进行排序
2. 交换排序 VS 插入排序 VS 选择排序
交换：每次只调换两个元素之间的位置
插入：遍历到的元素放入之前维护的已完成排序的序列中
选择：选择剩余元素中最大或最小的元素
3. 排序算法的稳定度
如果排序算法并不改变两个相同值的元素的相对位置，则此算法的稳定度高
二、冒泡排序
1.算法
每次遍历，从头至尾依次比较两两相邻元素是否满足排序条件，不满足则交换两者位置
当一次遍历中没有发生交换操作后，结束遍历
2.代码
C++：
1 void bubble(vector<int> &array) { 2 if (array.size() == 0) { 3 return; 4 } 5 bool flag = false; 6 while (!flag) { 7 flag = true; 8 for (int i = 0; i < array.size() - 1; i++) { 9 if (array[i] > array[i + 1]) { 10 int temp = array[i]; 11 array[i] = array[i + 1]; 12 array[i + 1] = temp; 13 flag = false; 14 } 15 } 16 } 17 }
JAVA：
1 void bubble(int[] array) { 2 if (array.length == 0) { 3 return; 4 } 5 boolean flag = false; 6 while (!flag) { 7 flag = true; 8 for (int i = 0; i < array.length - 1; i++) { 9 if (array[i] > array[i + 1]) { 10 int temp = array[i]; 11 array[i] = array[i + 1]; 12 array[i + 1] = temp; 13 flag = false; 14 } 15 } 16 } 17 }
Python：
1 def bubble(array): 2 if not array: 3 return 4 flag = False 5 while not flag: 6 flag = True 7 for i in range(0, len(array)-1): 8 if array[i] > array[i+1]: 9 array[i], array[i+1] = array[i+1], array[i] 10 flag = False
3.优化
每次遍历后，最后一次交换操作之后的所有元素均已完成排序，下一次遍历的终点可以前提至最后交换操作元素的索引位置
4.评估
时间复杂度：O(n2)
空间复杂度：O(1)
稳定性：稳定
原文：https://www.cnblogs.com/xmalll/p/11629902.html