基础排序之选择排序
Start
前言
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。《百度百科》
1. 选择排序
上面提到了选择排序是不稳定的排序方法，那冒泡排序是不是稳定的排序方法呢？稳定的意思指的是什么呢？
判断某排序算法是否稳定，我们可以简单理解成：排序前 2 个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。
如果相同，则是稳定的排序方法。
如果不相同，则是不稳定的排序方法。
如果排序前的数组是[3,3,1]，假定我们使用选择排序的话，那第一趟排序后结果就是[1,3,3]。这个数组有两个相同的值，它俩在 array[0]和 array[1]，结果经过排序，array[0] 的跑到了 array[2] 上了。
那么这就导致：2 个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序不相同，因此，我们就说它是不稳定的。
再回到上面的问题，上一篇说讲的冒泡排序是稳定的，主要原因是：俩俩比较的时候，没有对相等的数据进行交换(因为没必要)。因此它不存在 2 个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序不相同。
那么稳定排序的好处是什么？
- 参考知乎回答@独行侠的回答：
如果我们只对一串数字排序，那么稳定与否确实不重要，因为一串数字的属性是单一的，就是数字值的大小。但是排序的元素往往不只有一个属性，例如我们对一群人按年龄排序，但是人除了年龄属性还有身高体重属性，在年龄相同时如果不想破坏原先身高体重的次序，就必须用稳定排序算法。
很清晰的指出，只有当在“二次”排序时不想破坏原先次序，稳定性才有意义。
2. 第一趟排序
它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完。
首先，我们创建数组，找到它最大的值:
int[] arrays = {2, 3, 1, 4, 3, 5, 1, 6, 1, 2, 3, 7, 2, 3};
//假定max是最大的
int max = 0;
for (int i = 0; i < arrays.length; i++) {
if (arrays[i] > max) {
max = arrays[i];
}
}
随后这个最大的数和数组末尾的数进行交换：
//使用临时变量，让两个数互换
int temp;
temp = arrays[11];
arrays[11] = arrays[13];
arrays[13] = temp;
那么经过第一趟排序，我们的最大值已经到了数组的末尾了。
3. 第二趟排序
再次从数组获取最大的数(除了已经排好的那个）：
int max2 = 0;
for (int i = 0; i < (arrays.length - 1); i++) {
if (arrays[i] > max2) {
max2 = arrays[i];
}
}
System.out.println(max2);
再将获取到的最大值与数组倒数第二位交换：
temp = arrays[7];
arrays[7] = arrays[12];
arrays[12] = temp;
经过第二次排序，已经能够将数组最大两个数进行排序了
4. 代码简化
从前两趟排序其实我们就可以摸出规律了：
- 一个数组是需要 n-1 趟排序的(因为直到剩下一个元素时，才不需要找最大值)
- 每交换 1 次，再次找最大值时就将范围缩小1
- 查询当前趟数最大值实际上不用知道最大值是多少(上面我查出最大值，还要我手动数它的角标)，知道它的数组角标即可，交换也是根据角标来进行交换
第一趟：遍历数组14个数，获取最大值，将最大值放到数组的末尾[13]
第二趟：遍历数组13个数，获取最大值，将最大值放到数组倒数第二位[12]
….
数组有14个数，需要13趟排序。
//记录当前趟数的最大值的角标
int pos ;
//交换的变量
int temp;
//外层循环控制需要排序的趟数
for (int i = 0; i < arrays.length - 1; i++) {
//新的趟数、将角标重新赋值为0
pos = 0;
//内层循环控制遍历数组的个数并得到最大数的角标
for (int j = 0; j < arrays.length - i; j++) {
if (arrays[j] > arrays[pos]) {
pos = j;
}
}
//交换
temp = arrays[pos];
arrays[pos] = arrays[arrays.length - 1 - i];
arrays[arrays.length - 1 - i] = temp;
}
5. 选择排序优化
一般的选择排序每遍历一次数组，只找出最大或最小的那个值，那如果我们在一次遍历之后就把最大和最小值都找出来呢，时间在理论上会比原来少花一半左右。具体代码如下：
void SelectionSort_Optimization(int arr[], int size) {
int left=0, right=size-1; //left跟right用于循环上下界的左右逼近
while(left<right){
int temp;
int max=right, min=left;
for (int i = left;i <= right;i++) {
if (arr[i] > arr[max]) {
max = i;
}
if (arr[i] < arr[min]) {
min = i;
}
}
temp = arr[max]; //
arr[max] = arr[right]; // 这块代码将遍历后的最大值交换到右边
arr[right] = temp; //
if (min == right) { // 这段代码存在的意义在于可能存在min==right
min = max; // 的情况，在上面的arr[right]与arr[max]的
} // 值交换后，arr[left]就应该与arr[max]交换
temp = arr[min]; //
arr[min] = arr[left]; // 交换最小值到左边
arr[left] = temp; //
left++;
right--;
}
return;
}
申明：开始的图片来源网络，侵删
