【C/C++】算法入门：排序/算法笔记

（设排序从小到大）

冒泡排序

这个大家都会，从第一个开始往后俩俩交换，然后第二个，最后到最后一个，复杂度n^2
选择排序

思路和冒泡差不多，比如要得到从小到大的排序，就是从第一个开始，i取1~n，每次取[i,n]中的最小值，将最小值和a[i]交换。

我写的垃圾代码，中间还写错了改了半天：

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 0x3F3F3F3F;

void show_ans(int a[], int n)

{

   for (int i = 0; i < n; i++)

   {

      printf("%d ", a[i]);

   }

   printf("\n");

}

//这个函数有问题：

int find_min(int a[], int begin, int n, int& loc)

{

   int min = maxn;

   for (int i = begin; i < n; i++)

   {

      if (a[i] < min)

      {

         min = a[i];

         loc = i;

         //printf("%d\n",min);

         //break; 这里不能写break，不然就找不到最小值啦，寻找全局性最小一定要全跑完

      }

   }

   return min;

}

//选择排序 从[i,n]中选择最小元素与a[i]交换

void selectSort(int a[], int n) //n是数组长度，因为数组传参的时候只传首地址，不能计算数组长度

{

   for (int i = 0; i < n; i++)

   {

      int loc = 0;

      int min = find_min(a, i, n, loc);

      printf("%d min %d\n", i, min); //

      swap(a[i], a[loc]);

      show_ans(a, n);

      printf("\n");

   }

}

int main()

{

   int a[] = {4,3,2,1};

   int n = sizeof(a)/sizeof(a[0]);

   printf("%d\n", n);

   selectSort(a, n);

   for (int i = 0; i < n; i++)

   {

      printf("%d ", a[i]);

   }

   system("pause");

}

晴神的书上例程：

void selectSort(int a[], int n) //n是数组长度，因为数组传参的时候只传首地址，不能计算数组长度

{

   for (int i = 0; i < n; i++)

   {

      int k = i;

      for (int j = i; j < n; j++)

      {

          if (a[j] < a[k])

          {

              k = j;

          }

      }

      int temp = a[i];

      a[i] = a[k];

      a[k] = temp;

   }

}

非常简洁。

插入排序

to be continued...

巴特西

【C/C++】算法入门：排序/算法笔记

最新文章

热门文章