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

Java实现简单排序——冒泡、选择、插入、奇偶排序1)冒泡排序(从小到大排序):位置处于相互临近的两个数组元素互相比较,如果大小不满足条件就交换,否则继续比较后面的相邻选择直至这趟循环结束。例子:521432)选择排序3)插入排序4)奇偶排序

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]+" ");
        }
    }

测试结果依旧如上。

/

这里写图片描述

最后有个概念我们可能会用到,稳定性:是指具有相同值的数据项,经过排序后相互位置没有改变,比如6(我们称为6.1)排序之前在6(6.2)的前面,排序之后还是(即6.1还是在6.2的前面)。

今天的文章Java实现简单排序——冒泡、选择、插入、奇偶排序分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/28728.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注