选择排序算法

选择排序法 是对 定位比较交换法（也就是冒泡排序法） 的一种改进。选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中 选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有 简单选择排序、树型选择排序和 堆排序。 简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录， 将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。 简单选择排序算法： 假设我们要对上面的几个数字进行排序。 我们先找到里面最小的数字，就是1，所以我们把1排到第一位，然后1和8交换位置。 然后我们到后面的数组里面找相应最小的数字是2，再把2和6调换一下位置 以此类推最终只剩下最后一个元素，我们不用动它，或者让它自己跟自己交换位置就好了。 public class SelectSort { public static void main(String[] args) { int arr[]={8,6,2,3,1,5,7,4}; selectionSort(arr); for(int i:arr){ System.out.println(i); } } public static void selectionSort(int arr[]){ for(int i=0;i<arr.length;i++){ //遍历整个数组 int minIndex=i; //声明最小值坐标 for(int j=i+1;j<arr.length;j++){ //遍历为交换的数组 if(arr[minIndex]>arr[j]){ //拿当前最小值跟为交换的数组对比 minIndex=j; } } int conversion=arr[i]; //换位变量 arr[i]=arr[minIndex]; //交换位置 arr[minIndex]=conversion; } } } 算法思路：每次选择一个最小（大）的数，与有序序列后面的一个元素（第一个不有序的元素）做 交换 。  可以看出本算法：  1.简单排序算法是 不稳定 的。这个有点不好直接看出来，因为寻在最小值时是依次比较的，这个过程不会影响算法的稳定性，但是在交换时，由于交换位置的不确定性，会导致算法出现不稳定的情况：如{3*,3,1}–>{1,3,3*}。总之简单选择排序是不稳定的。最有一点，如果采用插入方式替换交换，那么这个算法就是稳定得了，可惜时间复杂度会上去。  2.时间复杂度，这个明显会一直是O(n^2)，两个循环会一直执行。  3.空间复杂度，O（1）保持最小或最大值.

选择排序–简单选择排序的改进（二元选择排序）

改进并没有降低时间复杂度和空间复杂度。但是却提供了一个很好的思路：类似与多线程解决问题的方法。在每次循环时找到一个最小值和最大值分别放到对应的位置有序位置上，两边同时排序。这样可以把最外层的循环由n降至n/2。 

这种方法在提高效率的同时，也带来了一些问题：就像多线程一下，如果同时访问一个位置数据可能就会出现问题

public class SelectSort { public static void main(String[] args) { int arr[] = { 8, 6, 2, 3, 1, 5, 7, 4 }; selectionSort(arr); for (int i : arr) { System.out.println(i); } } public static void selectionSort(int arr[]) { int length = arr.length; for (int i = 0; i < length / 2; i++) { // 遍历整个数组 int minIndex = i; // 声明最小值坐标 int maxIndex = i; // 声明最大值坐标 for (int j = i + 1; j < length; j++) { // 遍历为交换的数组 if (arr[minIndex] > arr[j]) { // 拿当前最小值跟为交换的数组对比 minIndex = j; } if (arr[maxIndex] < arr[length-j]) { // 拿当前最大值跟为交换的数组对比 因为最大的数字已经确定，所以这里只对比没有确定的值。 maxIndex = length-j; } } int tmp = arr[i]; // 理论上最多是有三个数字进行交换。所以多声明一个变量 if (tmp == arr[maxIndex]&&i<length/2-1) { // 当前值为最大值 应该是先交换最大值，再交互那最小值 int maxTmp = arr[length - i - 1]; arr[length - i - 1] = arr[maxIndex]; arr[i] = maxTmp; // 把最大值赋值给 当前坐标的值 int minTmp=arr[i]; arr[i] = arr[minIndex]; // 把最小值赋值给 当前坐标的值 arr[minIndex]=minTmp; }else{ int maxTmp = arr[length - i - 1]; int minTmp=arr[minIndex]; arr[length - i - 1] = arr[maxIndex]; arr[maxIndex] = maxTmp; // 把最大值赋值给 当前坐标的值 arr[minIndex]=tmp; arr[i]=minTmp; } } } }算法缺陷很明显：当排序的数组长度不是偶数的时候就会出现bug。所以这里改进一下，如果是奇数的话，外圈多循环一次就OK了。 public class SelectSort { public static void main(String[] args) { int arr[] = { 8, 6, 2, 3, 1, 5, 7, 4,9}; selectionSort(arr); for (int i : arr) { System.out.println(i); } } public static void selectionSort(int arr[]) { int length = arr.length; int forNum=(int) Math.ceil((double)arr.length/2); for (int i = 0; i < forNum; i++) { // 遍历整个数组 int minIndex = i; // 声明最小值坐标 int maxIndex = i; // 声明最大值坐标 for (int j = i + 1; j < length; j++) { // 遍历为交换的数组 if (arr[minIndex] > arr[j]) { // 拿当前最小值跟为交换的数组对比 minIndex = j; } if (arr[maxIndex] < arr[length-j]) { // 拿当前最大值跟为交换的数组对比 因为最大的数字已经确定，所以这里只对比没有确定的值。 maxIndex = length-j; } } int tmp = arr[i]; // 理论上最多是有三个数字进行交换。所以多声明一个变量 if (tmp == arr[maxIndex]&&i<forNum-1) { // 当前值为最大值 应该是先交换最大值，再交互那最小值 int maxTmp = arr[length - i - 1]; arr[length - i - 1] = arr[maxIndex]; arr[i] = maxTmp; // 把最大值赋值给 当前坐标的值 int minTmp=arr[i]; arr[i] = arr[minIndex]; // 把最小值赋值给 当前坐标的值 arr[minIndex]=minTmp; }else{ int maxTmp = arr[length - i - 1]; int minTmp=arr[minIndex]; arr[length - i - 1] = arr[maxIndex]; arr[maxIndex] = maxTmp; // 把最大值赋值给 当前坐标的值 arr[minIndex]=tmp; arr[i]=minTmp; } } } }