排序算法（一）：冒泡排序和选择排序

1.冒泡排序

冒泡排序，顾名思义，数值大的数据像从前向后冒（顺序排列）。每次比较相邻的两个元素，如果后者比前者数值更小则交换二者的顺序，依次遍历整个数组，完成排序。

冒泡排序.gif

python实现：

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

c++实现：

void bubble_sort(int arr[], int len){
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            if (arr[j]>arr[j+1])
                std::swap(arr[j], arr[j+1]);
        }
    }
}

一个小坑
在编写c++代码时开始只想给bubble_sort()函数传入一个参数：数组arr[]，arr的长度len试图在函数中通过 sizeof(arr) / sizeof(arr[0]) 获得，但是测试时始终无法正确得到数组arr的长度。获得数组长度的正确方法：

#include<iostream>
using namespace std;
template<class T>
int length(T& arr)
{
    //cout << sizeof(arr[0]) << endl;
    //cout << sizeof(arr) << endl;
    return sizeof(arr) / sizeof(arr[0]);
}
int main()
{
    int arr[] = { 1,5,9,10,9,2 };
    // 方法一
    cout << "数组的长度为：" << length(arr) << endl;  // 输出结果：数组的长度为：6
    // 方法二
    //cout << end(arr) << endl;
    //cout << begin(arr) << endl;
    cout << "数组的长度为：" << end(arr)-begin(arr) << endl;  // 输出结果：数组的长度为：6
    system("pause");
    return 0;
}

2.选择排序

选择排序，首先在数组全体元素中找到最小的元素，记录其索引，将该元素与未排序部分的首元素交换位置。剩余元素中重复该操作，即可完成排序。

选择排序.gif

python实现：

def selection_sort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

c++实现

void selection_sort(int arr[], int len){
    for(int i=0;i<len-1;i++){
        int minindex=i;
        for(int j=i+1;j<len;j++){
            if (arr[minindex] > arr[j]){
                minindex = j;
            }
        }
        std::swap(arr[i], arr[minindex]);
    }
}