排序算法 之 选择排序

        咳咳~选择排序,非常简单的算法…我自己经常用,因此写这段代码大约只要30秒…当初去参加CVTE面试,一面的最后是写一段代码,我原先的思路要用到二分查找思想,可惜写着写着就卡壳了…面试官提醒我时间不多了,于是我放弃了时间复杂度O(n*logn)的算法,在极短的时间内直接写了一个时间复杂度O(n^2)的类似选择排序的算法给他。虽然性能不高,但至少向他证明了我最最基本的代码能力。大概也正因为这段神速写完的代码,再加上面试官本身人很nice,我才顺利地通过了一面。

        好了,回忆完了,说正事儿~

        选择排序:最常见的排序算法之一,时间复杂度O(n^2),空间复杂度O(1),是不稳定的排序算法。代码实现:

void SelectSort(int x[], int n) //选择排序,升序
{
  int i, j, iMin, temp;
  for (i=0; i<n-1; i++)
  {
    iMin = i;
    for (j=i+1; j<n; j++)
      if (x[j] < x[iMin])
        iMin = j;
    temp = x[i];
    x[i] = x[iMin];
    x[iMin] = temp;
  }
}

        会不会觉得,用中间变量 temp 显得很老土呢?其实我也有点这么觉得= =||…So,我们改用异或计算交换数值吧!不仅节省了4个字节的内存,还能装装逼,真可谓一举两得!

void SelectSort(int x[], int n)
{
  int i, j, iMin;                 // 不再需要中间变量 temp
  for (i=0; i<n-1; i++)
  {
    iMin = i;
    for (j=i+1; j<n; j++)
      if (x[j] < x[iMin])
        iMin = j;
    if (i != iMin)                // 切记:异或交换两个数的值,一定不能用同一块内存异或它本身,否则结果恒为0
    {
      x[i] = x[i] ^ x[iMin];
      x[iMin] = x[i] ^ x[iMin];
      x[i] = x[i] ^ x[iMin];
    }
  }
}

    原文作者:Whitesoft
    原文地址: https://blog.csdn.net/Whitesoft/article/details/49492219
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞