选择排序与冒泡排序

选择排序与冒泡排序的使用很少，但依旧经典。

1.选择排序(慢,不稳定)

//选择排序(时间复杂度为N**2,空间为1,不稳定)
//每次找到最小的放在最前面,每次循环比较n次,换一次
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }

//选择排序的优化
//每次循环找到一个最大的和最小的
//将最大的放在数组最后面,最小的放在前面;
//*************************
//交换的时候需要注意:1.先交换最小值,
//                2.若max存的值为数组最前面,则跟交换后的min互换
//即:若max=j;swap(a,max,min) 因为min与j已经互换位置了,需要重定向
for(int j=0;j<a.length;j++){
    int max = a.length-j-1;
    int min = j;
    for (int i = j; i < a.length-j; i++) {
        if (a[min] > a[i]) min = i;
        if (a[max] < a[i]) max = i;
    }
    //两组数的交换
    swap(a,min,j);
    if(max!=j){  //否则正常交换
        swap(a,max,a.length-j-1);
    //如果max==j,先将min和j交换后,max需与min交换
    }else{swap(a,min,a.length-j-1);}

}

2.冒泡排序(慢,稳定)

//冒泡排序(时间复杂度为N**2,空间为1,稳定)[最好情况能达到n]
//每次找到最大的放在最后面,每次循环比较n次,换k次
    //循环次数,排从尾到第二个的数   n
        for (int j=a.length-1;j>0;j--) {
            //一次循环     n
            for (int i=0;i<a.length-1;i++) {
                if (a[i] > a[i+1]) swap(a,i,i+1);
            }
        }

//改进版冒泡,最快达到n,已排好情况下,发现一次没换直接返回
        int k=0;
        for(int j=a.length;j>0;j--)
        {
            for (int i = 0; i < j - 1; i++) {
                if (a[i] > a[i + 1]) {
                    swap(a, i, i + 1);
                     k++;
                }
            }
            if (k==0) break;
        }