Java实现简单排序——冒泡、选择、插入、奇偶排序

1)冒泡排序（从小到大排序）：位置处于相互临近的两个数组元素互相比较，如果大小不满足条件就交换，否则继续比较后面的相邻选择直至这趟循环结束。

例子：52143
第一趟:a[0]与a[1]比较，a[0]>a[1]，交换两个元素，然后a[1]与a[2]比较… 结果为21435,第一趟比较后最大的元素一定在数组元素的末尾

第二趟:a[0]与a[1]比较…,第二趟比较后倒数第二大的元素一定在a[a.length-2]位置

第n-1趟…….这趟结束之后数组一定全都有序了

思考为什么比较n-1次就行了？

原因在于n-1趟后，排序完之后，剩下一个元素也一定是有序的（还需自己思考）

第一次趟需要进行9次比较，第二趟需要8次……

以下图片来自《Java数据结构和算法》:

代码如下：

public static void bubbleSort(int[] a){
        int temp;
        for(int i=0;i<a.length-1;i++){  //只需要N-1趟就足够了
            for(int j=0;j<a.length-i-1;j++){
             /*因为每一趟循环下来，总有一个前面的最大的元素移动到了后面，所以后面的元素就不用比较了*/
                if(a[j]>a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }

测试数据如下：

public static void main(String[] args) {
        int[] a=new int[]{
  
  120,34,2,67,11,6,100,58,6,45};
        bubbleSort(a);//冒泡排序
    }

数据结果为：

2 6 6 11 34 45 58 67 100 120

还有一个关于冒泡排序算法的有趣改版，大概是这个意思，利用两个游标，一个在数组的最左边，另一个在数组的最右边，同时向中间移动，这是外循环，里面还有两个孽循环，一个是从利用冒泡排序将大的元素向后移动，而另外一个是利用冒泡排序将小的元素向前移动，代码如下:

/* * 利用左右两个外标，逐渐向里面推进，当两个外标相等时推出 * 在这两个外标里面有两个循环，前面的一个循环从左外标利用冒泡算法推进到右外标-把大的数向右边移动 * 第二个循环从右外标向左边移动，把小的数向左边移动 */
    public static void bubleSort2(int[] a){
        int leftout=0,rightout=a.length-1;
        //leftout和rightout是数组双向的外标
        int temp;
        for(;rightout>leftout;rightout--,leftout++){
            for(int in=leftout;in<rightout;in++){   
                if(a[in]>a[in+1]){                    
                    temp=a[in];
                    a[in]=a[in+1];
                    a[in+1]=temp;
                }
            }
            for(int in=rightout-1;in>leftout;in--){
                if(a[in-1]>a[in]){
                    temp=a[in];
                    a[in]=a[in-1];
                    a[in-1]=temp;
                }
            }
        }
        System.out.println();
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }

    }

经过测试后发现结果一样，大家理解即可。

2）选择排序：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；
然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。一共N-1趟。
例子：53214
第一趟，先假设a[0]就是最下的数，用一个变量i记录下标，i=0,后面四个数依次与a[0]即5比较，如果有比a[i]还小的数，就将i的值改为此时的下标….直到与最后一个元素比较后,结束这一趟的程序.（i显然等于3）
第一趟结束后，判断i与0是否相等，不相等就交换两个下标的元素，
那么结果就是13254

第一趟，还是先假设第一个元素为最小，用i记录下标即i=1,依次与右面的元素比较……i=2，
第二趟结束后，判断i与1是否相等，不相等就交换两个下标的元素，
那么结果就是12354
…….
第N-1趟，判断最后两个元素是否排序了…..至此算法就结束了。

代码如下:

public static void selectionSort(int[] a){
        int k,temp;
        for(int i=0;i<a.length-1;i++){
            k=i;
            for(int j=i+1;j<a.length;j++){
                if(a[j]<a[k]){
                    k=j;
                }
            }
            if(k!=i){
                temp=a[k];
                a[k]=a[i];
                a[i]=temp;
            }
        }
        System.out.println();
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }

结果依旧如上.

3)插入排序：从第二个元素开始(第一个元素只有一个数，显然“排好序了”),将它的值存入一个临时变量temp中，然后依次与前面的数——[0]比较。如果比他小，就再与前面的元素比较，因为a[0]已经是再前面的元素了，所以就结束了比较循环，就将比a[1]大的数向后移动一个位置（因为a[1]的值已经存入了临时变量中，所以不怕被覆盖），然后将a[1]的值存入之前a[0]的位置。

然后再从第三个元素开始…..

例子：
326541
从a[1]开始，将a[1]存入temp中，依次比较直至不满足条件，将比temp大的元素全都后移一步，填入a[1]的值…….结果为236541
从a[2]…..结果为236541
a[3]…..结果为235641
……
最后一步，234561—>123456

public static void insertSort(int[] a){
        int in,temp;
        for(int i=1;i<a.length;i++){
            temp=a[i];
            in=i;
            while(in>0 &&a[in-1]>temp ){
                a[in]=a[in-1];
                in--;
            }
        }
        System.out.println();
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }

测试结果依旧如上。

4）奇偶排序:它的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对，a[j]和 a[j+1],j是奇数(j=1,3……),对应数组中实际是从a[0]与a[1]如果它们的关键字的值次序颠倒,就交换它们。
第二趟扫描对所有的偶数数据项进行同样的操作(j=2,4……),对应数组中实际是从a[1]与a[2],重复进行这样两趟的排序直到数组全部有序….
可能有同学还不是很清楚，没关系接着看就行了。
例子：52136
首先是奇数，a[0]与a[1]比较，a[2]与a[3]
偶数就是a[1]与a[2]比较，a[3]与a[4]

代码如下：

public static void oddEvenSort(int[] a){
        int j;
        for(int i=0;i<a.length;i+=2){
            j=0;
            scan(a,j);
            j=1;
            scan(a,j);
        }
        //这个while循环是上面的循环的优化
        boolean flag=true;
        int temp;
        System.out.println();
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
    private static void scan(int[] a,int j){
        int temp;
        while(j<a.length-1){
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
            j+=2;
        }
    }

测试结果依旧如上，这时候我相信大家已经理解了奇偶排序的含义，其实上面的代码可以优化，代码如下：

public static void oddEvenSort(int[] a){
        //这个while循环是上面的循环的优化
        boolean flag=true;
        int temp;
        while(flag){
            flag=false;
            for(int j=0;j<a.length-1;j+=2){
                if(a[j]>a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                    flag=true;
                }
            }
            for(int j=1;j<a.length-1;j+=2){
                if(a[j]>a[j+1]){
                    temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                    flag=true;
                }
            }
        }
        System.out.println();
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }