插入排序和冒泡排序

1、插入排序

• 流程如下：

1）从第一个元素开始遍历，该元素可以认为已经被排序，记录已排序序列的结尾元素为end = i
2）取下一个元素temp = arr[end + 1]，从已排序的元素序列从后往前遍历
3）如果遍历的元素arr[end]> temp，则将该元素移到下一位，即arr[end+1] = arr[end]，同时end–
4）如果遍历的元素arr[end]<= temp，则跳出循环
5）将temp插入到该元素的后面，即arr[end + 1] = temp

• C++代码为：

#include <vector>
using namespace std;void insert_sort(vector<int>& arr){int n = arr.size();for (int i = 1; i < n; i++){end = i - 1;temp = arr[i];while (end >= 0 && arr[end] > temp){arr[end] = arr[end + 1];end--;}arr[end + 1] = temp;}
}

• Python：

def insertion_sort(arr):for i in range(1, len(arr)):temp = arr[i]  # 当前待插入的元素end = i - 1  # 已排序部分的最后一个元素的索引位置while end >= 0 and arr[end] > temp:arr[end + 1] = arr[end]  # 把比当前元素大的元素往后移动end -= 1arr[end + 1] = temp  # 插入当前元素到正确的位置return arr

2、冒泡排序

• 流程如下：

1）从第一个元素开始，比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2）那么最后的元素应该会是最大的数。
3）持续每次对越来越少的元素重复上面的步骤，重复n = arr.size()次，直到没有任何一对数字需要比较。

• C++：

#include <vector>
using namespace std;void bubble_sort(vector<int>& arr){int n = arr.size();for (int i = 0; i < n; i++){for (int j = 0; j < n - i -1; j++){if (arr[j] > arr[j+1]){int temp = arr[j+1];arr[j+1] = arr[j];arr[j] = temp;}}}
}

• Python:

def bubble_sort(arr):n = len(arr)for i in range(n-1):for j in range(n-i-1):if arr[j] > arr[j+1]:temp = arr[j + 1]arr[j + 1] = arr[j]arr[j] = temp