首页 > 代码库 > 算法——蛮力法之选择排序和冒泡排序c++实现

算法——蛮力法之选择排序和冒泡排序c++实现

  这次实现的是蛮力法中的两个例子,选择排序法和冒泡排序法,使用的编译环境是vs2013,下面对这两个算法做一个简单介绍,然后是两个算法的c++实现代码。

  选择排序法比较的范围是整个列表,每次扫描结束找出最小的一个元素一次放在前面的位置;而冒泡排序法每次是将相邻两个元素进行比较,将较大的元素放在后面,这样一次扫描结束后就将当前最大的那个元素放在了列表的后面。


 

  两个排序方法的算法如下:

选择排序法

  SelectionSort(A[0....n-1])

  //输入:一个可排序数组A[0....n-1],

  //输出:升序排序的数组A[0....n-1]

  for    i  <—0  to   n-2   do

    min  <—  i;

    for j <—  i+1  to  n-1    do

      if A[j]  <  A[min]     min  <—j;

        swap A[i] and A[min];

  


 

  该算法的输入规模就是元素的个数n,基本操作就是if语句中比较的步骤:A[j]  <  A[min],比较的执行次数为:(n-1)n/2,也就是Θ(n2)。


 

  冒泡排序算法:

  BubbleSort(A[0....n-1])

  //输入:一个可排序数组A[0....n-1]

  //输出:升序排序的数组A[0....n-1]

  for    i  <—0  to   n-2   do

    for j <—  0  to  n-2-i   do

      if A[j+1]<A[j]  

        swap A[j+1]andA[j]

该算法的时间复杂度和选择排序的时间复杂度一样都是Θ(n2)。


#include <iostream>
using namespace std;
void SelectionSort(int iSort[], int n);
void BubbleSort(int iSort[], int n);
void swap(int &a, int &b);
//-------------------主函数------------------- int main(){ int a[10]; for (int i = 0; i < 10; i++){ cin >> a[i]; } getchar(); //SelectionSort(a, 10); //这里传递的实参是数组名, //也就是将地址进行传递,这样被调用的函数就能够改变数组a的值。 BubbleSort(a, 10); for (int i = 0; i < 10; i++){ cout << " " << a[i]; } getchar(); return 1; } //-------------------选择排序法------------------- void SelectionSort(int iSort[],int n){ int i = 0, j = 0,min=0; for (i = 0; i < n - 1; i++){ min = i; for (j = i + 1; j < n ; j++){ if (iSort[j]<iSort[min]){ //如果要得到降序排列,只要将这里的判断条件改为if (iSort[j]>iSort[min])即可 min = j; } } swap(iSort[i], iSort[min]); } } //-------------------冒泡排序法------------------- void BubbleSort(int iSort[], int n){ int i = 0, j = 0; for (i = 0; i < n - 1; i++){ for (j = 0; j < n - 1 - i; j++){ if (iSort[j + 1] < iSort[j]){ swap(iSort[j + 1], iSort[j]); } } } } //-------------------交换元素------------------- void swap(int &a, int &b){ int temp; temp = a; a = b; b = temp; }

 

算法——蛮力法之选择排序和冒泡排序c++实现