排序算法-选择排序

算法简介

选择排序就是找到数组中最小元素将其和数组第一个元素交换位置，然后在剩下的元素中找到最小元素并将其与数组第二个元素进行交换，以此类推，直至整个数组排序结束。

算法描述

• 找到数组中最小元素并将其和数组第一个元素交换位置
• 在剩下的元素中找到最小元素并将其与数组第二个元素交换，直至整个数组排序

代码实现

 /** * 选择 * * @param array */ private static void selectionSort(int[] array) { if (array == null || array.length == 0 || array.length == 1) return; int min; for (int i = 0; i < array.length - 1; i++) { min = i; for (int j = array.length - 1; j > i; j--) { if (array[j] < array[min]) min = j;//将最小数的索引保存 } //最小元素与第i位置元素互换 if (array[i] > array[min]) { int temp = array[i]; array[i] = array[min]; array[min] = temp; } } }

性能分析

最好情况：交换 0 次，但是每次都要找到最小的元素，因此时间复杂度为$ O(n^2) $。

最坏情况：交换 \(n-1\)次，但是每次都要找到最小的元素，因此时间复杂度为$ O(n^2) $。

平均情况下时间复杂度为$ O(n^2) $。

因为需要一个临时变量来交换元素位置和一个变量记录最小位置，(另外遍历序列时自然少不了用一个变量来做索引)，所以其空间复杂度为\(O(1)\)。

由于每次都是选取未排序序列R中的最小元素 a 与 R 中的第一个元素交换，很可能破坏了元素间的相对位置，因此选择排序是不稳定的。

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
选择排序	\(O(n^2)\)	\(O(n^2)\)	\(O(n^2)\)	\(O(1)\)	不稳定