:-: 14.3 选择排序 * * * * * **基本概念：** 它是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 它的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。 **算法的运作：** 1、首先在未排序序列中找到最小（大）元素，若最后所得最小（大）值的位置和当前对比的元素位置不同，就交换存放到排序序列的当前对比的元素位置，若相同直接跳过从下一个开始。 2、再从剩余未排序元素中继续寻找最小（大）元素的位置。 3、以此类推，重复以上步骤，直到所有元素均排序完毕。 **图片示例：** :-:  **代码实现：** 第一种方式： ~~~ public void selectionSort(int nums[]) { int min = 0, sign = 0; for (int i = 0; i < nums.length - 1; i++) { min = i; for (int j = min + 1; j < nums.length; j++) { if (nums[min] > nums[j]) { min = j; } } if (min != i) { sign = nums[min]; nums[min] = nums[i]; nums[i] = sign; } } } ~~~ 第二种方式：我称为鸡尾酒选择排序，一轮选两个，就是从两边向中间，逐步有序，左边是选择出的最小值，右边是选择出的最大值，直到左右交合。 **图片示例：** :-:  ~~~ public void selectionSort(int nums[]) { int left = 0, right = nums.length - 1, j, min, max, temp = 0; while (left < right) { min = left; for (j = left + 1; j <= right; j++) { if (nums[min] > nums[j]) { min = j; } } if (min != left) { temp = nums[min]; nums[min] = nums[left]; nums[left] = temp; } left++; max = right; for (j = right - 1; j >= left; j--) { if (nums[max] < nums[j]) { max = j; } } if (max != right) { temp = nums[max]; nums[max] = nums[right]; nums[right] = temp; } right--; } } ~~~ **复杂度分析：** 时间复杂度：平均：O(n^2)、最坏：O(n^2)、最优：O(n^2)。 空间复杂度：最坏：O(n), 最优：O(1)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。** **本文主要参考以下文章：** [维基百科——选择排序](https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F) [JS中常见排序算法（示例图片来源）](https://github.com/Sir814/Sort/blob/master/02.%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F.gif)