一、简单选择排序
-
描述：给定待排序序列A[ 0......n ] ，选择出第i小元素，并和A[i]交换，这就是一趟简单选择排序。
示例：给定数组A[0 ...... 5]={3, 5, 8, 9, 1, 2}，分析A数组进行选择排序的过程：
第二趟：i=2，index=6， a[2] 和 a[6] 进行交换。得到序列：{ 1,2,8,9,3,5 }
第三趟：i=3，index=5， a[3] 和 a[5] 进行交换。得到序列：{ 1,2,3,9,8,5 }
第四趟：i=4，index=6， a[3] 和 a[5] 进行交换。得到序列：{ 1,2,3,5,8,9 }
第五趟：i=5，index=5， 不用交换。得到序列：{ 1,2,3,5,8,9 }
6-1）趟选择结束，得到有序序列：{ 1,2,3,5,8,9 }
public class SimpleSelectionSort1 { void simpleSelectionSort(int[] arr) { int length = arr.length; int i, j, index; //1. 进行length-1趟选择，每次选择出最小值 for (i = 0; i < length; i++) { index = i; //2. 选择第i小记录为arr[index] for (j = i+1; j < length; j ++) { if (arr[j] < arr[index]) { index = j; } } if (index != i) { arr[i] = arr[i] + arr[index]; arr[index] = arr[i] - arr[index]; arr[i] = arr[i] - arr[index]; } } printArray(arr); } void printArray(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } } public static void main(String[] args) { int[] arr = {9, 6, 12, 1, 15, 10, 17, 2, 11, 1, 4, 8, 19, 14}; SimpleSelectionSort1 selectionSort = new SimpleSelectionSort1(); selectionSort.simpleSelectionSort(arr); }} import java.util.ArrayList;import java.util.Arrays;import java.util.Iterator;import java.util.List;public class SimpleSelectionSort2 { public List list = new ArrayList (); /** * 递归函数进行简单选择排序--采用list存储新排序的array，不太好 * @param arr 待排序的数组 */ void simpleSelectionSort(int[] arr) { int length = arr.length; int i, index; if (length == 1) { list.add(arr[0]); printArray(list); return; } //选择序列中最小元素，下标为index for (i = index = 0; i < length; i++) { if (arr[i] < arr[index]) { index = i; } } //将最小元素与序列中首元素交换 if (index != 0) { arr[0] = arr[0] + arr[index]; arr[index] = arr[0] - arr[index]; arr[0] = arr[0] - arr[index]; } list.add(arr[0]); //去除序列中的最小首元素，进行递归调用 arr = Arrays.copyOfRange(arr, 1, arr.length); simpleSelectionSort(arr); } /** * 递归函数进行简单选择排序 * @param array 待排序的数组 * @param startIndex 从startIndex数组下标开始往后排序，忽略startIndex之前的元素 */ public void simpleSelectionSortRecursion(int[] array, int startIndex){ //递归结束条件 if(startIndex == array.length - 1){ printArray(array); return; } //假设start元素为最小值 int minIndex = startIndex; for(int i = startIndex; i < array.length; i++){ if(array[i] < array[minIndex]){ minIndex = i; } } //如果start元素就是最小值，则不再交换 if (minIndex != startIndex) { array[startIndex] = array[startIndex] + array[minIndex]; array[minIndex] = array[startIndex] - array[minIndex]; array[startIndex] = array[startIndex] - array[minIndex]; } //递归：前面一位已经排序成功，排序startIndex元素往后移一位 simpleSelectionSortRecursion(array, startIndex + 1); } void printArray(List array) { Iterator iterator = array.iterator(); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); } } void printArray(int[] array) { for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } } public static void main(String[] args) { int[] arr = {9, 6, 12, 1, 15, 10, 17, 2, 11, 1, 4, 8, 19, 14}; SimpleSelectionSort2 selectionSort2 = new SimpleSelectionSort2(); selectionSort2.simpleSelectionSort(arr); System.out.println("\n------------分割线--------------"); selectionSort2.simpleSelectionSortRecursion(arr, 0); }} 性能分析
容易看出，简单选择排序所需进行记录移动的操作次数较少，这一点上优于冒泡排序，最佳情况下（待排序序列有序）记录移动次数为0，最坏情况下（待排序序列逆序）记录移动次数n-1。
外层循环进行了n-1趟选择，第i趟选择要进行n-i次比较。每一趟的时间：n-i次的比较时间+移动记录的时间（为一常数0或1，可以忽略）。总共进行了n-1趟。忽略移动记录的时间，所以总时间为(n-1)*(n-i)=n^2-(i+1)*n+i。时间复杂度为O（n^2）。不管是最坏还是最佳情况下，比较次数都是一样的，所以简单选择排序平均时间、最坏情况、最佳情况 时间复杂度都为O（n^2）。同时简单选择排序是一种稳定的原地排序算法。当然稳定性还是要看具体的代码，在此就不做深究。