【21天算法学习】直接选择排序

作者简介：

🍀姓姜，字君竹。

🍁浅薄观点：科以载文，文以载道

🌱软件技术升计科，计划考研

🌾要有最朴素的生活和最遥远的梦想，即使明日，天寒地冻，路遥马亡

1.概念及介绍

 直接选择排序也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R[1]~R[n-1]中选取最小值，与R[1]交换，…，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

2.时间空间复杂度

 在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行n - i次比较 (1 <= i <= n-1)，而每次交换最多需要3次移动，因此，总的比较次数C = (n*n - n)/2；

 总的移动次数3(n-1)，由此可知，直接选择排序的时间复杂度为 O(n2) ，所以当记录占用字节数较多时，通常比直接插入排序的执行速度快些；

 对于空间复杂度来说，简单选择排序仅需一个存储空间用于记录交换的暂存单元，即空间复杂度为 O(1)；

 由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。

3.图解

1. 代码实现
   

int main() {
  int a[] = { 22,45,21,23,54,76,8,67,67 };
  int sz = sizeof(a) / sizeof(a[0]);
  int i = 0;
  for(i = 0; i < sz - 1; i++){
    int k = i;
    int j = 0;
    for (j = i + 1; j < sz; j++) {
      if (a[j] < a[k]) {
        k = j;
      }
    }
    if (k != i) {
      int tmp = a[i];
      a[i] = a[k];
      a[k] = tmp;
    }
  }
  for (i = 0; i < sz; i++) {
    printf("%d ", a[i]);
  }
  return 0;
}

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。