1592391606(1).jpg
public static void selectSort(int[] arr){
if(arr.length==0)
return;
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]){
//1.易错点
minIndex=j;
}
}
swap(arr,minIndex,i);
}
}
//固定代码
public static void swap(int[] arr,int i,int j){
//1. 取出arr[i]的值
int temp=arr[i];
//2. j位置的值覆盖到i位置,此时i位置的值已经不存在了
//所以我们要在步骤1 将i对应的值保存起来
arr[i]=arr[j];
//3. j位置赋值temp temp其实保存的是i原来位置的值
//完成交换
arr[j]=temp;
}
不能直接找到一个比minIndex小的就swap,因为交换后比较的就是minIndex和后一个元素2个元素的比较 而不是minIndex和后面所有元素比较
首先有2层循环: 第一层,从0-length依次选取待排序的元素 第二次,将待排序的元素与后面的所有元素比较,选择后面所有元素中最小的元素,然后交换
所以时间复杂度为 O(n^2) 没有开辟新的空间,所以空间复杂度为O(1)
插入排序.png
public static void insertSort(int[] arr){
//1. i=1
for(int i=1;i<arr.length;i++){
//2. j>0
for(int j=i;j>0;j--){
//3. arr[j]<arr[j-1]
if(arr[j]<arr[j-1]){
swap(arr,j,j-1);
}
}
}
}
//swap 代码同上 下面全部省略 默认arr是合法的
易错点3,不容易理解,要记住。
优化一:
public static void insertSort(int[] arr){
for(int i=0;i<arr.length;i++){
for(int j=i;j>0;j--){
if(arr[j]<arr[j-1]){
swap(arr,j,j-1);
}else{
break;
}
}
}
}
从代码中我们看出,当i找到合适的位置后,我们没有退出循环,但是从图片上,此时已经是有序的了。所以用break直接跳出循坏。
优化二:
减少重复赋值
View绘制6步分析-1.png
思想时不变的,只不过将swap()换成单次赋值,这样减少一次赋值
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
//1.
int temp = arr[i];
int j;
for (j = i; j > 0; j--) {
if (temp < arr[j - 1]) {
//2.
arr[j] = arr[j - 1];
} else {
break;
}
}
//3.
arr[j] = temp;
}
}
==易错点==
根据上图覆盖的思想,很容易写出下面的代码:
public static void insertSort5(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int minIndex = i;
for (int j = i; j > 0 ; j--) {
if (temp < arr[j - 1]) {
arr[j] = arr[j - 1];
} else {
//TODO 错误 当i=1时 执行一次没有走到这个语句 变成了{8, 8, 2, 3, 1, 5, 7, 4}
minIndex = j;
break;
}
}
arr[minIndex] = temp;
}
}
这个是不对的,不能保存临死的j,因为当i=1时 执行一次没有走到这个语句,那么后面的排序就全错了
优化三:
优化判断,其实也并非多大优化,就是更加整洁
public static void insertSort(int[] arr){
for(int i=0;i<arr.length;i++){
int temp=arr[i];
int j;
for(j=i;j>0&&temp < arr[j - 1];j--){
arr[j] = arr[j - 1];
}
arr[j]=temp;
}
}
可以看到一个简单插入排序就可以有这么多的优化。
==选择排序与插入排序的比较==
选择排序从从头(i=0)开始向后遍历,每次找到length-i后面元素中的所有元素中的最小值。然后记录最小值的位置,当从i遍历到length结束后,交换minIndex和i的位置,此时i前面(包括i位置)的所有元素就都是有序的了 插入排序,正好与选择排序相反,思想有点像我们生活中的扑克牌,当你抓1张的时候,没有别的牌和他比较,那么他就是有序的,再来一张,比第一张牌小,那么它俩交换。第二章插入到i=0的位置。再抓第三张牌(i=2)后,先和第二张(i=1)比较,小于,交换,在和i=0比较,小于再交换,此时第三张牌之前的元素都是有序的。 所以选择排序是向后寻找,插入是向前寻找 选择排序是不稳定排序,插入排序是稳定排序
选择排序核心代码:
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[min] < arr[j]) {
min = j;
}
}
swap(arr,min,i);
}
如果我有一段数组: 5 6 8 5 2 7
当i=0时 认为5是最小的 ,所以i=0与i=3比较 不满足arr[min] < arr[j] 当i=4时满足
那么i=0和i=4交换,所以 最后变成2 6 8 5 '5' 7
看出选择是不稳定的。
插入排序
View绘制6步分析.png
当红色4之前的元素都排好序,此时带插入的元素为蓝色4,判断 arr[j] < arr[j - 1];不成立,位置不变。比较下一个元素5.所以插入是稳定
冒泡排序,应该是大家接触的最早的排序算法之一了。
原始数据
1.png
第一轮循环
2.png
完成第一轮排序
3.png
第二轮循环
4.png
完成第二轮排序
5.png
思想:
每次从启示位置(i=0)开始,相邻的两个元素,两两比较,当右侧位置的值大于左侧位置的值,交换位置,否则位置不变,继续下次循环。
6.png
编码前的分析
代码实现
public static void bubbleSort(int[] arr){
for(int i=0;i<arr.length-1;i++){
//1.
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
}
==易错点==
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
//1.
for (int j = 1; j < arr.length - i - 1; j++) {
if (arr[j - 1] > arr[j]) {
swap(arr, j, j - 1);
}
}
}
}
这个咋一看好像是正确的,但是实际少排序一次,当i=0 那么arr.length - i - 1 = 7,那么最后一个元素是没有比较的,输出的结果为:
1 2 3 4 5 6 8 9 7
上面的代码是向前比较,而冒泡排序之所以叫冒泡排序,就是要排序的值,向后比较,向后移动。感觉是在冒出来
优化一
7.png
可以看到,当前面的元素已经是有序的了,但是我们还是会走完流程。我们可以记录最后交换位置时j的位置
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean isSroted=true;
for (int j = 1; j < arr.length - i - 1; j++) {
if (arr[j - 1] > arr[j]) {
swap(arr, j, j - 1);
isSroted=false;
}
}
if(isSorted){
break;
}
}
}