算法学习笔记(python&c++实现)--冒泡排序&选择排序

xiaoxiao2021-03-01  12

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

常见的排序算法复杂度如下表所示。冒泡排序和选择排序是排序算法中比较简单易懂的两种,原理不再赘述,本文使用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; }
转载请注明原文地址: https://www.6miu.com/read-4049989.html

最新回复(0)