经典冒泡排序（C++/Java/python实现与刷题）
好看的都关注了我们
冒泡排序是一种稳定的排序算法，时间复杂度为O(n^2)，空间复杂度为O(1)
所谓稳定性，其实就是说，当你原来待排的元素中间有相同的元素，在没有排序之前它们之间有先后顺序，在排完后它们之间的先后顺序不变，我们就称这个算法是稳定的
常用的时间复杂度所耗费的时间从小到依次是 O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
冒泡排序是最为出名的排序算法之一，从序列的一端开始往另一端冒泡（你可以从左往右冒泡，也可以从右往左冒泡），依次比较相邻的两个数的大小（可以是比大也可以是比小）。
冒泡排序思路：
1、 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3、 针对所有的元素重复以上的步骤，除了最后一个。
4、 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
C++版冒泡排序
void BubbleSort(vector<int>& v) {
int len = v.size();
for (int i = 0; i < len - 1; ++i)
for (int j = 0; j < len - 1 - i; ++j)
if (v[j] > v[j + 1])
swap(v[j], v[j + 1]);
}
冒泡排序改进版
冒泡有一个最大的问题就是这种算法不管不管你有序还是没序，闭着眼睛把你循环比较了再说。
比如我举个数组例子：[ 5，6，7，8，9 ]，一个有序的数组，根本不需要排序，它仍然是双层循环一个不少的把数据遍历干净，这其实就是做了没必要做的事情，属于浪费资源。
针对这个问题，我们可以设定一个临时遍历来标记该数组是否已经有序，如果有序了就不用遍历了。
void BubbleSort_orderly(vector<int>& v) {
int len = v.size();
bool orderly = false;
for (int i = 0; i < len - 1 && !orderly; ++i) {
orderly = true;
for (int j = 0; j < len - 1 - i; ++j) {
if (v[j] > v[j + 1]) { // 从小到大
orderly = false; // 发生交换则仍非有序
swap(v[j], v[j + 1]);
}
}
}
}
Java实现冒泡排序
public class bubble_Sort {
public static void sort(int arr[]){
for( int i = 0 ; i < arr.length - 1 ; i++ ){
for(int j = 0;j < arr.length - 1 - i ; j++){
int temp = 0;
if(arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
冒泡排序改进版
public class Bubble_Sort_optimization {
public static void sort(int arr[]){
for( int i = 0;i < arr.length - 1 ; i++ ){
boolean isSort = true;
for( int j = 0;j < arr.length - 1 - i ; j++ ){
int temp = 0;
if(arr[j] > arr[j + 1]){
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSort = false;
}
}
if(isSort){
break;
}
}
}
}
java实现一个工整的冒泡排序
public class Bubble_Sort {
public static void main(String[] args) {
int[] arr = new int[]{24, 69, 80, 57, 13};
bubbleSort(arr);
printArray(arr);
}
public static void printArray(int[] arr) {
System.out.print("[");
for(int x = 0; x < arr.length; ++x) {
if (x == arr.length - 1) {
System.out.print(arr[x]);
} else {
System.out.print(arr[x] + ", ");
}
}
System.out.println("]");
}
public static void bubbleSort(int[] arr) {
for(int x = 0; x < arr.length - 1; ++x) {
for(int y = 0; y < arr.length - 1 - x; ++y) {
if (arr[y] > arr[y + 1]) {
int temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
}
}
python实现冒泡排序
def bubble_sort(arr):
"""冒泡排序"""
# 第一层for表示循环的遍数
for i in range(len(arr) - 1):
# 第二层for表示具体比较哪两个元素
for j in range(len(arr) - 1 - i):
if arr[j] > arr[j + 1]:
# 如果前面的大于后面的，则交换这两个元素的位置
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
排序算法刷题
合并排序数组
给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
解法：以下解法使用从后往前并且使用原来存在的数组A，从后往前极大地减小了时间复杂度，不需要遍历，而任使用A数组极大地降低了空间复杂度
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int k=m+n-1,i=m-1,j=n-1;
while(i>=0&&j>=0){
if(A[i]<B[j]){
A[k--]=B[j--];
}else{
A[k--]=A[i--];
}
}
while(j>=0){
A[k--]=B[j--];
}
}
}