Java版选择排序和插入排序

排序算法不论在C语言Java,.net,php都很重要,冒泡排序、选择排序、插入排序是用的比较多的。个人觉得冒泡排序比较好理解,无非就是交换位置的过程,如下所示

public class BubbleSort{
    public static void main(String[] args){
        int score[] = {67, 69, 75, 87, 89, 90, 99, 100};
        for (int i = 0; i < score.length -1; i++){    //最多做n-1趟排序
            for(int j = 0 ;j < score.length - i - 1; j++){   
                if(score[j] < score[j + 1]){    //把小的值交换到后面
                    int temp = score[j];
                    score[j] = score[j + 1];
                    score[j + 1] = temp;
                }
            }           
            System.out.print("第" + (i + 1) + "次排序结果:");
            for(int a = 0; a < score.length; a++){
                System.out.print(score[a] + "\t");
            }
            System.out.println("");
        }
            System.out.print("最终排序结果:");
            for(int a = 0; a < score.length; a++){
                System.out.print(score[a] + "\t");
        }
    }
 }

但是像选择排序和插入排序理解起来会稍微困难一些,这2种排序和冒泡有很大的不同,先来看看插入排序

1.插入排序:

将n个元素的数列分为已有序和无序两个部分,如下所示:

{{a1},{a2,a3,a4,…,an}}
{{a1⑴,a2⑴},{a3⑴,a4⑴ …,an⑴}}

{{a1(n-1),a2(n-1) ,…},{an(n-1)}}

每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。

Java版选择排序和插入排序

这种方式的排序主要就是为待插入的数找合适位置,之后插入变为新数组,在重复同样的操作,下面是我写的一段java代码

package org.lxh;
public class InsertSort {
    /**
    *插入排序
    */
    public static void main(String[] args) {
        int arr[]={23,6,45,8,7,24,-2};
        for(int i=1;i<arr.length;i++){
            //insertVal是准备插入的数
            int insertVal=arr[i];
            int insertIndex=i-1;
            //如果待插入的数小于前一个数,则把较大的数移动到后面
            while(insertIndex>=0&&insertVal<arr[insertIndex]){
                arr[insertIndex+1]=arr[insertIndex];
                //考虑到类似-2这样的情况,还必须往前面找合适位置
                insertIndex--;
            }
            //到这里为止我们就为要插入的数据找到了位置
            arr[insertIndex+1]=insertVal;
                                                                                             
        }
        for(int k=0;k<arr.length;k++){
                System.out.println(arr[k]);
        }
    }
}

对于这段代码可能在 insertIndex-- 这个地方理解起来很困难,这里这样写是为了考虑类似-2的这种情况,不是交换一次就可以。

相关阅读:

JAVA 插入排序(直接插入)

排序算法(JAVA实现):冒泡排序法和插入排序法

Java实现直接插入排序

Java实现选择排序

排序算法(Java实现):选择排序法和快速排序法

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/763cb9a5cd0efcee3e6a519776f69a5e.html