排序算法第一讲 --- 冒泡排序(Python、C++、C)

排序算法系列目录

  排序算法第一讲 — 冒泡排序(Python、C++、C)   排序算法第二讲 — 选择排序(Python、C++、C)   排序算法第三讲 — 插入排序(Python、C++、C)   排序算法第四讲 — 快速排序(Python、C++、C)   排序算法第五讲 — 希尔排序(Python、C++、C)   排序算法第六讲 — 归并排序(Python、C++、C)

---

题目描述：

给你一个整数数组 nums，请你将该数组采用冒泡方式进行升序排列。

---

解题思路:

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

---

代码：

Python写法：

class Solution(object): def solution(self, nums): n = len(nums) for i in range(n-1): for j in range(i+1, n): if nums[i] > nums[j]: temp = nums[i] nums[i] = nums[j] nums[j] = temp return nums

C++写法：

#include<iostream> using namespace std; int main() { int a[10] = {1, 2, 4, 5, 6, 10, 4, 2, 8, 6}; for(int i = 0; i < 10; i++) for(int j = i+1;j < 10; j++) if(a[i] > a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; } for(i = 0; i < 10; i++) cout<< a[i] <<" "; cout << "\n"; return 0; }

C语言：

#include <stdio.h> int main(){ int nums[] = {4, 9, 5, 6, 8, 3, 2, 7, 10, 1}; int temp; for(int i = 0; i < 10; i++){ for(int j = i+1; j < 10; j++){ if (nums[i] > nums[j]){ temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } } for(i = 0; i < 10; i++) printf("%d ", nums[i]); printf("\n"); return 0; }

看完以上的实现思路后，发现并不是按照冒泡写的，故推出以下版本：

import random def bubble_sort(nums): for i in range(len(nums)): for j in range(len(nums)-i-1): if nums[j] > nums[j+1]: temp = nums[j] nums[j] = nums[j+1] nums[j+1] = temp return nums nums = [random.randint(0, 10) for i in range(10)] print("排序前", nums) print("排序后", bubble_sort(nums))

---

题目来源：

http://lab.csdn.net/#/question/38?tagId=16