首页 > 编程语言 > 详细

冒泡排序和直接插入排序和选择排序

时间:2018-02-14 22:52:41      阅读:32      评论:0      收藏:0      [点我收藏+]

标签:bsp   直接插入排序   如果   ()   得到   监视   思想   思考   sys   

简单排序(学完了要及时复习,不然像没学一样,而且

以后要花更多的时间)

冒泡排序:小的数往上冒

冒泡排序(BubbleSort)是重复地走访要排序的数列,

一次比较两个元素,如果他们的顺序错误,就把他们就

把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

 

原理:

1.比较相邻的元素。如果第二个比第一个大,就交换他们两个。(小的在前)

2.对每一对相邻元素作同样的工作,从第一对到结尾的

最后一对。在这一点,最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤,出最后一个。

4.持续每次对越来越少的元素重复上面的步骤,直到

没有任何一对数字需要比较。

 

时间复杂度:

若文件的初始状态是正序的,一趟扫描即可完成排序。

所需要的关键字比较次数C和记录和记录移动次数M

均达到最小值:Cmin=n-1;

Mmin=0;

所以冒泡排序最好的时间复杂度为O(n)。

public class BubbleSort{
    public static void sort(long[] arr){
        long tmp=0;
        for (int i=0;i<arr.length-1;i++) {
            //趟数,并让最小的于前
        for (int j=arr.length-1;j>i;j--) {
                if (arr[j]<arr[j-1]) {
                    //进行交换
                    tmp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=tmp;
                }
            }    
        }
    }
}

public class TestSort1{
    public static void main(String[] args) {
        long[] arr=new long[5];
        arr[0]=34;
        arr[1]=23;
        arr[2]=2;
        arr[4]=1;
        arr[3]=-4;
        //如果没有赋值完的话,后面的直接补0
        System.out.print("[");
        for (long num:arr){
            //用法??
            System.out.print(num+" ");

        }
        System.out.print("]");
        System.out.println();

        BubbleSort.sort(arr);
        //排序后再打印 

        System.out.print("[");
        for(long num:arr){
            System.out.print(num+" ");
        }
        System.out.print("]");
        System.out.println();

    }
}
/*
运行结果:
  i         j
[34 23 2 -4 1 ]
[-4 1 2 23 34 ]
*/

//自己再去默写一次

 

选择排序:

选择最小的于前并交换位置,其余不变

public class SelectionSort1{
    public static void sort(long[] arr){
        int k=0;
        long tmp=0;
        for (int i=0;i<arr.length-1;i++) {
            //趟数小于length-1,因为最后一个不用排序,就是最大的
            k=i;
            //最小的指向数,k去指向
            for (int j=i;j<arr.length;j++) {
                //为什么是arr.length而不是length-1?length-1只能到length-1
              //边界位置还是要思考思考!!最后再测试测试
                if(arr[j]<arr[k]) {
                    k=j;
                }
            }
            tmp=arr[i];
            arr[i]=arr[k];
            arr[k]=tmp;
        }
    }
}

public class TestSort2{
    public static void main(String[] args) {
        long[] arr=new long[5];
        arr[0]=34;
        arr[1]=23;
        arr[2]=2;
        arr[4]=1;
        arr[3]=-4;
        //如果没有赋值完的话,后面的直接补0
        System.out.print("[");
        for (long num:arr){
            //用法??
            System.out.print(num+" ");

        }
        System.out.print("]");
        System.out.println();

        SelectionSort1.sort(arr);
        //排序后再打印

        System.out.print("[");
        for(long num:arr){
            System.out.print(num+" ");
        }
        System.out.print("]");
        System.out.println();

    }
}
/*
arr.length-1的循环结果
[34 23 2 -4 1 ]
[-4 2 23 34 1 ]
arr.length的循环结果
[34 23 2 -4 1 ]
[-4 1 2 23 34 ]
*/

直接插入排序:

直接插入排序是一种简单的插入排序法,其基本思想是

把待排序的记录按其关键码值的大小逐个插入到一个已经

排好序的有序序列中,直到所有的记录插入完为止,得到

一个新序列。

例如,已知待排序的一组记录是

60,71,49,11,24,3,66

假设在排序过程中,前三个记录已经按关键码值递增

的次序重新排序,构成一个有序序列:

49,60,71

将待排序记录中的第四个记录11插入尚需序列总,得到

一个新的含4个记录的有序序列。

1.设置监视r0,将待插入记录的值赋给r0;

2.设置开始查找的位置j;

3.在数组中进行搜索,搜索中将第j个记录后移,直到

r0.key>=[j].key为止;

4.将r0插入r[j+1]的位置上

冒泡排序和直接插入排序和选择排序

标签:bsp   直接插入排序   如果   ()   得到   监视   思想   思考   sys   

原文:https://www.cnblogs.com/shijinglu2018/p/8449023.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号