Java排序算法——选择排序（Selection sort）

传送门

• 冒泡排序
• 插入排序

---

简述

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

算法描述（设有n个元素）

1. 从第一个元素开始，比较所有未排序的元素，并标记最小（大）元素，将最小（大）元素与未排序的第一个元素进行交换。
2. 第一轮排序时，从第一个元素开始。比较第一个元素和第二个元素，将小（大）的元素的位置标记，并于之后的元素进行比较和标记，直到和最后一个元素比较结束，将标记的最小（大）的元素和第一个元素进行交换。一共进行n-1轮比较。
3. 第二轮排序时，同第一轮一样的过程，将未排序元素中最小（大）的元素送至第二位，一共进行了 n-2 次比较。
   …
4. 一共进行了n-1轮排序

图片来源于参考资料

Java代码

int[] arr={3,2,5,1,4};
for (int i=0;i<arr.length-1 ;i++ ){int min = i;for (int j=i+1;j<arr.length ;j++ ){if (arr[j]<arr[min]){min=j;}}if (min!=i){arr[i]=arr[i]^arr[min]; // ^ 异或符号，可以更快的进行两个数据之间的传递 arr[min]=arr[i]^arr[min];arr[i]=arr[i]^arr[min];}}System.out.println(Arrays.toString(arr));//使用java.util.Arrays包下的toString()方法可以快速遍历数组

复杂度

时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定