简单算法——直接插入、冒泡、直接选择

95 阅读 0 评论 63 点赞

我是靠谱客的博主缓慢铃铛，最近开发中收集的这篇文章主要介绍简单算法——直接插入、冒泡、直接选择，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

排序的算法有很多
这里写图片描述
其中直接插入排序、直接选择排序、冒泡排序属于简单排序，它们对空间的要求不高，但是时间效率却不稳定；
本文将介绍三种简单排序，下一篇会介绍三种简单排序对应的高级排序快速排序、希尔排序、堆排序
首先做一个公用的元素交换实现函数，下面的swap调用都是这个

 /**
     * 交换数组元素
     * 交换思想很简单 数字x y  =>  x=x+y;y=x-y;x=x-y;
     * 这种方法不使用临时变量，能有效降低算法空间复杂度，但也有缺点，比如可能存在越界风险
     * @param arr
     * @param a
     * @param b
     */
    public void swap(int []arr,int a,int b){
        arr[a] = arr[a]+arr[b];
        arr[b] = arr[a]-arr[b];
        arr[a] = arr[a]-arr[b];
    }

冒泡排序

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”。
基本操作：
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一轮，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
如：
原始数组： 5 3 6 4
第一步：3 5 4 6
第二步：3 4 5 6 （实际到这里排序已经结束，但是原始的冒泡排序会走完所有的循环）
第三步：3 4 5 6
第四步：3 4 5 6

程序实现

    int arr[] = {5,3,6,4};
    public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //每次将最大的数字移到最后，下次循环长度-1，再将剩余数组中最大的数字移到剩余数组长度的后面
            for (int j = 0; j < arr.length - i -1; j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr, j, j+1);
                }
            }
        }
       // printArr(arr);
    }

也可以优化一下，如果排序已经完成，就停止循环：

    public void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = true;//设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已然完成。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

直接插入排序

基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。如：

原始数组： 5 3 6 4
第一步：5 - - - 3 6 4
第二步：3 5 - - - 6 4 （3和5比较一次）
第三步：3 5 6 - - - 4（6和5比较一次）
第四步： 3 4 5 6 （4和3 5 6 各比较一次）

程序实现

    int arr[] = {5,3,6,4};
    /**
     * 采用直接插入排序 将数组按升序排列
     * @param arr
     */
    private void directInsert(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]){//两层意思：1、如果是第一个元素就放着 不比较也不交换 2、如果后面一个数字小于前面那个 就进行交换
                swap(arr, j, j-1);
                j--;
            }
        }
    }

也可以这样实现：

    int arr[] = {5,3,6,4};
    public void insertSort(int[] arr) {
        int j;
        for (int i = 0; i < arr.length; i++) {
            int tem = arr[i];
            for (j = i; j > 0 && tem < arr[j - 1]; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = tem;
        }
        //printArr(arr);
    }

直接选择排序

基本思想是：第一轮遍历中从R[0]~R[n-1]的数组中选取最小值，与R[0]交换；第二轮从数组R[1]~R[n-1]中遍历选取最小值，与R[1]交换，…..，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到升序序列。如：
原始数组： 5 3 6 4
第一轮：[ 3 ] 5 6 4 （选出最小值3 和第一个数字5交换）
第二轮：[ 3 4 ] 6 5 （选出最小值4 和第二个数字5交换）
第三轮：[ 3 4 5 ] 6 （选出最小值5 和第三个数字6交换）
第四轮：[ 3 4 5 6 ]

程序实现

    public void straightSelection(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int tem = i;//存放较小元素下标
            for (int j = i + 1; j < arr.length; j++){
                if (arr[j] < arr[tem]) {
                    tem = j;
                }
            }
            if (tem != i) {
                swap(arr, i, tem);
            }
        }
        printArr(arr);
    }