排序算法 - 选择排序

深碍√TFBOYSˉ_ 2023-08-17 16:43 275阅读 0赞

基本思路

先默认未排序区首个元素为最小，然后从后面的元素中挑出最小的元素，与这个元素交换，直至循环完成。

1475571-20190815213627230-1753040981.png

算法代码

  1. 1 //简单的选择排序
  2.  2 void SelectSort(int *arr, int n)
  3.  3 {
  4.  4     int i, j;
  5.  5     int temp;
  6.  6     int minIndex;
  7.  7     for (i = 0; i < n - 1; i++) //做第i趟排序,共n-1趟，因为第n趟只剩一个一定是最大的
  8.  8     {
  9.  9         minIndex = i;
  10. 10         for (j = i + 1; j < n; j++)
  11. 11         {
  12. 12             if (arr[j] < arr[minIndex])
  13. 13                 minIndex = j;
  14. 14         }
  15. 15         if (minIndex != i) //后面有更小的元素
  16. 16         {
  17. 17             temp = arr[i];
  18. 18             arr[i] = arr[minIndex];
  19. 19             arr[minIndex] = temp;
  20. 20         }
  21. 21     }
  22. 22 }

算法分析

从i个记录中挑选最小记录需要比较i-1次。

第i（i=0～n-2）趟从n-i记录中挑选最小记录需要比较n-i-1。

对 n 个记录进行简单选择排序，所需进行的关键字的比较次数 总计为：

1475571-20190815213748126-1269609219.png

移动记录的次数，正序为最小值 0，反序为最大值3(n-1) 。

简单选择排序的最好、最坏和平均时间复杂度为O(n2)。

转载于:https://www.cnblogs.com/WindSun/p/11360751.html

发表评论

表情：
评论列表 （有 0 条评论，275人围观）

还没有评论，来说两句吧...

相关阅读

    相关 排序算法——选择排序

    一、算法思想 给定一个无序数列，用第一个位置与后面的元素比较，只要遇到更小的，就将其调换。 第一遍：用 idx 0 位置上的数与后面的数依次比较，更小则调换，否则不动

    小灰灰小灰灰/ 0 赞/ 375 阅读

    相关 排序算法-选择排序

    选择排序 是这样的原理 第一次排序将 最小的值 放在第一位 第二次排序将 第二小的放在第二位 之后 依次把第i小的 放在 i 位置上 我觉得最重要的一点是 如何拿

    短命女短命女/ 0 赞/ 381 阅读

    相关 排序算法--选择排序

    1.基本思想：假设\[1...n\]为待排序数据的下标，R(i)表示第i个数据，将数据按从小到大（从大到小）的顺序排序。第一趟排序假设第一个数据（即R(1)）为最小（最大）的

    港控/mmm°港控/mmm°/ 0 赞/ 444 阅读

    相关 排序算法---选择排序

    基本思路： 选择排序 就是第一次遍历，把最大（最小）放到最前面。 第二次遍历，把第二大的放到第二个位置，即将第一次遍后除去最大的那个，再找剩下数中最大的。 第三次遍历，除

    古城微笑少年丶古城微笑少年丶/ 0 赞/ 411 阅读