O(n²)的 n² 怎么读啊？n的2次方吗？

选择排序（Selection sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度，所以用到它的时候，数据规模越小越好。
O(n²)的 n² 怎么读啊？n的2次方吗？

欧的恩平方

对的，也可以读作"n平方"

应该是吧，我觉得似乎没问题

• 这篇博客: 冒泡、插入和选择排序------时间复杂度为O(n²)的排序算法中的 选择排序（Selection Sort） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• public int[] selectionSort(int[] a, int n) {
          for (int i = 0; i < a.length - 1; i++) {
              int min = i;
              for (int j = i + 1; j < a.length; j++) {
                  if (a[j] < a[min]) {//找出未排序部分的最小值的坐标
                      min = j;
                  }
              }
              if (min != i) {
                  //交换
                  int temp = a[i];
                  a[i] = a[min];
                  a[min] = temp;
              }
          }
          return a;
      }

  选择排序的时间复杂度如何？

  最好、最坏和平均情况：选择排序无论何种情况每个大循环内都需要比较未排序部分找出最小元素的坐标，所以时间复杂度都为O(n²)。

  是否是原地排序算法​​​​​​​？

  因为选择排序也是在自身数组上进行排序，无需申请额外的内存空间，所以空间复杂度为O(1)，是原地排序算法。

  是否是稳定的排序算法？

  我们可以举个例子，一个数组：3,4,3,2,1。当找到1的时候，需要与第一个3交换，此时两个3的前后顺序翻转，所以选择排序不是稳定的排序算法。

  ---

  	原地排序？	稳定排序？	最好   最坏  平均
  冒泡排序	√	√	O(n)  O(n²)   O(n²)
  插入排序	√	√	O(n)  O(n²)   O(n²)
  选择排序	√	×	O(n²)  O(n²)   O(n²)

  总结这三种排序，你会发现，冒泡排序和插入排序稳定性和时间复杂度要优于选择排序，那么应该选择冒泡排序还是插入排序呢？

  实际上，插入排序要优于冒泡排序，可以比较两者数据交换和数据移动的部分：

      //冒泡排序
      if(a[j] > a[j+1]){//数据交换
          int temp = a[j];
          a[j] = a[j + 1];
          a[j + 1] = temp;
          flag = true;
      }
  
      //插入排序
      if (a[j] > value) {
          a[j + 1] = a[j];//数据移动
      }

  从上面这两部分的代码我们可以发现，冒泡排序的数据交换部分需要三次交换操作，而插入排序需要的移动次数只需一次。

  经实验也证明，在大的数据量下的排序操作时，插入排序要明显优于冒泡排序，这也是插入排序在这三种排序算法中应用最广的原因。

  ---

  本博客是博主在学习王争老师的《数据结构与算法之美》时做的学习笔记，如有纰漏请在评论区指出，我们共同学习算法之美。