算法学习笔记–冒泡排序&选择排序

常见的排序算法复杂度如下表所示。冒泡排序和选择排序是排序算法中比较简单易懂的两种，原理不再赘述，本文使用python&c++实现一下这两种算法。

冒泡排序

冒泡排序顾名思义，就是通过类似冒泡操作的一次次的相邻位置替换，一次找到一个数字的正确位置（这里是最大值，第二大值……），如下图所示，话不多说上代码。

python版本：

import numpy as np def bubbleSort(arr): for i in range(len(arr)): for j in range(len(arr)-i-1): if arr[j+1] < arr[j]: tmp = arr[j] arr[j] = arr[j+1] arr[j+1] = tmp return arr if __name__ == "__main__": arr1 = np.array([5,4,3,2,1]) print bubbleSort(arr1)

c++版本：

#include<iostream> void bubbleSort(int *arr,int length){ for (int i = 0; i < length; i++){ for (int j = 0; j < length-i-1; j++){ if (arr[j+1]<arr[j]){ int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } } int main(){ int array[] = {6,5,4,3,2,1}; int length = sizeof(array)/sizeof(array[0]); bubbleSort(array, length); for (int i=0; i < sizeof(array)/sizeof(array[0]); i++){ std::cout<<array[i]<<std::endl; } return 0; }

选择排序

所谓选择排序，就是每一轮循环将待排序部分最小的值移动到最左边，如下图所示

代码如下： python版本：

import numpy as np def selectiveSort(arr): for i in range(len(arr)): minIndex = i for j in range(i+1,len(arr)): if arr[j]<arr[minIndex]: tmp = arr[j] arr[j] = arr[minIndex] arr[minIndex] = tmp return arr if __name__ == "__main__": arr = np.array([5,4,3,2,1]) print selectiveSort(arr)

c++版本：

#include <iostream> void selectiveSort(int *arr,int length){ for (int i=0; i<length; i++){ int minIndex = i; for (int j=i+1; j<length; j++){ if(arr[j]<arr[minIndex]){ int tmp = arr[j]; arr[j] = arr[minIndex]; arr[minIndex] = tmp; } } } } int main() { int arr[] = {5,4,3,2,1}; int length = sizeof(arr)/sizeof(arr[0]); selectiveSort(arr,length); for (int i=0; i<length; i++){ std::cout<<arr[i]<<std::endl; } return 0; }