1、排序算法概述
常用的内部排序方法有：交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、堆排序）、插入排序（直接插入排序、希尔排序）、归并排序、基数排序（一关键字、多关键字）。
- 所需辅助空间最多：归并排序
- 所需辅助空间最少：堆排序
- 平均速度最快：快速排序
- 不稳定：快速排序，希尔排序，堆排序。
选择排序算法的依据：任何排序算法在数据量小的时候基本体现不出来差距。选择依据有：
- 1.数据的规模 ：当数据规模较小时，选择直接插入排序或冒泡排序。
- 2.数据的类型 ：如全部是正整数，那么考虑使用桶排序为最优。
- 3.数据已有的顺序 ：快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。
数据量极小，而且已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。
2、简单选择排序时空复杂度
时间复杂度O()，空间复杂度O(1)，是一种不稳定的排序算法。
选择排序的时间复杂度： 简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数永远都是N (N - 1) / 2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0。当序列反序时，移动次数最多，为3N (N - 1) / 2。
简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n)。
3、简单选择排序原理
每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。也就是：每一趟在n-i+1(i=1，2，…n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。（这里只介绍常用的简单选择排序）
4、简单选择排序思路
给定数组：
int[] arr={里面n个数据}；第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arrr[1]交换；第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与r[2]交换；以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。
- 简单选择排序法就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换。如图所示：
5、简单选择排序举例说明
要排序数组：int[] arr={5,2,8,4,9,1};
第一趟排序： 原始数据：5 2 8 4 9 1
最小数据1，把1放在首位，也就是1和5互换位置，
排序结果：1 2 8 4 9 5
第二趟排序：
第1以外的数据{2 8 4 9 5}进行比较，2最小，
排序结果：1 2 8 4 9 5
第三趟排序：
除1、2以外的数据{8 4 9 5}进行比较，4最小，8和4交换
排序结果：1 2 4 8 9 5
第四趟排序：
除第1、2、4以外的其他数据{8 9 5}进行比较，5最小，8和5交换
排序结果：1 2 4 5 9 8
第五趟排序：
除第1、2、4、5以外的其他数据{9 8}进行比较，8最小，8和9交换
排序结果：1 2 4 5 8 9
注： 每一趟排序获得最小数的方法：for循环进行比较，定义一个第三个变量temp，首先前两个数比较，把较小的数放在temp中，然后用temp再去跟剩下的数据比较，如果出现比temp小的数据，就用它代替temp中原有的数据。具体参照后面的代码示例，相信你在学排序之前已经学过for循环语句了，这样的话，这里理解起来就特别容易了。
6、简单选择排序代码
public class SelectionSort {
public static void main(String[] args) {
int[] arr = { 6, 3, 8, 2, 9, 1 };
System.out.println("排序前数组为："+Arrays.toString(arr));
sort(arr);
System.out.println("排序后的数组为："+Arrays.toString(arr));
}
public static void sort(int[] arr) {
int loopTimes = 0;
for(int i = 0; i < arr.length - 1; i++){// 做第i趟排序
System.out.println();
System.out.println("i="+i);
int k = i;
for(int j = k + 1; j < arr.length; j++){// 选最小的记录
System.out.print(" j="+j);
if(arr[j] < arr[k]){
k = j; //记下目前找到的最小值所在的位置
}
loopTimes++;
}
//在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
if(i != k){ //交换a[i]和a[k]
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
System.out.println();
System.out.println("循环次数为："+loopTimes);
}
}
// 排序前数组为：[6, 3, 8, 2, 9, 1]
// i=0
// j=1 j=2 j=3 j=4 j=5
// i=1
// j=2 j=3 j=4 j=5
// i=2
// j=3 j=4 j=5
// i=3
// j=4 j=5
// i=4
// j=5
// 循环次数为：15
// 排序后的数组为：[1, 2, 3, 6, 8, 9]
评论区