标签：
冒泡排序
冒泡排序的优化
【冒泡排序】 冒泡排序的思想是：（以从小到大排序为例）从左到右两两比较，第一个数和第二个数比较，如果不符合顺序（第一个数大于第二个数），就交换这两个数的位置，接着第二个数和第三个数比较，如果不符合顺序（第二个数大于第三个数），就交换这两个数的位置...... 一趟处理完之后（从最左侧的两个数开始处理，处理到最右侧两个数）最大的那个数就放到了正确的位置（即最右侧的位置）。接下来，第二趟重复以上步骤，还是从左到右依次两两比较（只不过不用处理最后一个数，因为它已经放到了正确的位置上了）。接着第三趟、第四趟......直到所有的数都放到正确的位置排序结束。由于每一趟的处理，都会把待排序中最大的那个数通过一步步位置交换，最终在一堆数中脱颖而出，排到右侧正确的位置，就像一个气泡从水中一步步往上冒最终浮出水面一样，冒泡排序由此得名。
以排序[1, 9, 7, 4, 5, 2, 3]举例说明：
第一个数和第二个数比较（即1和9比较），因为1小于9，已经符合左小右大的顺序，所以不做处理：
第二个数和第三个数比较（即9和7比较），因为9大于7，所以需要交换9和7的位置：
第三个数和第四个数比较（即9和4比较），因为9大于4，所以需要交换9和4的位置：
第四个数和第五个数比较（即9和5比较），因为9大于5，所以需要交换9和5的位置：
第五个数和第六个数比较（即9和2比较），因为9大于2，所以需要交换9和2的位置：
第六个数和第七个数比较（即9和3比较），因为9大于3，所以需要交换9和3的位置：
至此，第一趟比较完，数字“9”就像一个气泡一样一步步浮出了水面，从一堆数中脱颖而出，它是最大的数，已经放到了最右侧的位置，它已经放到了正确的位置，下边就不需要再处理它了。
第二趟需要把第二大的数放到右数第二个位置上，后面每一趟需要把剩余数中最大的数排到剩余位置的最右侧...... 第一趟的完整图解：
第二趟完整图解：
第三趟完整图解：
第四趟完整图解：
第五趟完整图解：
第六趟完整图解：
剩下最后一个数，就不需要处理了，它自然就排到了正确的位置。 完整 Python 代码：
# 冒泡排序
def bubble_sort(nums):
for steps in range(len(nums)-1, 0, -1): # 总共需要的趟数
for i in range(steps): # 从左到右，从第一个数开始两两比较
if nums[i] > nums[i+1]: # 如果左边值大于右边值
nums[i], nums[i+1] = nums[i+1], nums[i] # 交换两个数的位置完整 C++ 代码：
// 冒泡排序
void bubble_sort(std::vector<int> &nums)
{
for (int i = nums.size() - 1; i > 0; i--) // 总共需要的趟数
{
for (int j = 0; j < i; j++) // 从左到右，从第一个数开始两两比较
{
if (nums[i] > nums[i+1]) // 如果左边值大于右边值
{
std::swap(nums[j], nums[j+1]) // 交换两个数的位置
}
}
}
}完整 C 代码：
// 冒泡排序
void bubble_sort(int arr[], int num)
{
for (int i = num-1; i > 0; i--) // 总共需要的趟数
{
for (int j = 0; j < i; j++) // 从左到右，从第一个数开始两两比较
{
if (nums[i] > nums[i+1]) // 如果左边值大于右边值
{
// 交换两个数的位置
int tmp = nums[j];
nums[j] = nums[j+1]
nums[j+1] = tmp;
}
}
}
}【冒泡排序的优化】 你可能已经发现，其实到第四趟结束时所有数全已排好，第五躺、第六躺就是在浪费时间，我们有没有办法在发现所有数都排好时提前结束排序呢？答案是可以的，只需要设置一个标志，判断某一趟是否有数据交换，如果一趟下来没有任何数据交换就说明所有数已排好，就可以结束排序。 完整 Python 代码：
# 优化的冒泡排序
def bubble_sort_better(nums):
for steps in range(len(nums)-1, 0, -1): # 总共需要的趟数
swap = False # 设置标志
for i in range(steps): # 从左到右，从第一个数开始两两比较
if nums[i] > nums[i+1]: # 如果左边值大于右边值
nums[i], nums[i+1] = nums[i+1], nums[i] # 交换两个数的位置
swap = True # 有数据交换
if not swap: # 如果一趟下来没有发生数据交换
return # 提前结束排序