冒泡排序&插入排序&选择排序

  • 2019-12-11
  • 80
  • 0

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一 个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。 我用一个例子,带你看下冒泡排序的整个过程。我们要对一组数据 4 , 5 , 6 , 3 , 2 , 1 ,从小到到大进行排序。

package com.husaky.algorithm;

public class Bubble {
    public static void main(String[] args) {
        int arr[] = {4, 3, 6, 5, 2, 1};
        int result[];
        result = bubbleSort(arr);
        for (int i = 0; i < result.length; ++i) {
            System.out.println(result[i]);
        }

    }

    /**
     * 冒泡排序算法
     * @param arr 要排序的数组
     * @return arr
     */
    public static int[] bubbleSort(int[] arr) {
        int length = arr.length; if (length <= 1) return arr;
        for (int i = 0; i < length; ++i) {
            // 提前推出冒泡排序的标志
            boolean exit = false;
            for (int j = 0; j < length - i -1; ++j) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    exit = true;   // 有数据交换
                }
            }
            if (!exit) break;
        }
        return arr;
    }
}

插入排序

一个有序的数组,我们往里面添加一个新的数据后,如何继续保持数据有序呢?很简单,我们只要遍历数组,找到数据应该插入的位置将 其插入即可。这是一个动态排序的过程,即动态地往有序集合中添加数据,我们可以通过这种方法保持集合中的数据一直有序。而对于一组静态数据,我们也可以借鉴上面讲 的插入方法,来进行排序,于是就有了插入排序算法。 那插入排序具体是如何借助上面的思想来实现排序的呢? 首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

插入排序也包含两种操作,一种是元素的比较,一种是元素的移动。当我们需要将一个数据a插入到已排序区间时,需要拿a与已排序区间的元素依次比较大小, a找到合适的插入位置。找到插入点之后,我们还需要将插入点之后的元素顺序往后移动一位,这样才能腾出位置给元素 插入。 对于不同的查找插入点方法(从头到尾、从尾到头),元素的比较次数是有区别的。但对于一个给定的初始序列,移动操作的次数总是固定的,就等于逆序度。

    /**
     * 插入排序算法
     * @param arr
     * @return
     */
    public static int[] insertionSort(int[] arr) {
        int length = arr.length;
        if (length <= 1) return arr;
        for (int i = 0; i < length; ++i) {
            // 相当于从未排数组种拿一个元素,和已排数组的元素比较,第一次已排数组的第一个元素就是已排数组的第一个元素
            int value = arr[i];
            int j = i - 1;
            // 第一次i=0; j=0 已排插入第一个元素,第二次i=1;j=0 开始比较
            // 第三次i=2;j=1; 下面要走两次循环,分别和已排数组的两个元素比较
            for (; j >= 0; --i) {
                if (arr[j] > value) {
                    // 移动位置插入新元素
                    arr[j + 1] = arr[j];
                }else {
                    break;
                }
            }
            // 第一次,已排数组为空,放入未排数组的第一个元素进去
            arr[j + 1] = value;
        }
        return arr;
    }


选择排序

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末 尾。

  /**
     * 选择排序
     * @param arr
     * @return
     */ public static int[] selectionSort(int[] arr)
    {
        int length = arr.length;
        if (length <= 1) return arr;
        for(int i = 0; i < length - 1; i++)
        {
            // 做第i趟排序
            int k = i;
            for(int j = k + 1; j < length; j++)
            {
                // 选最小的记录
                if(arr[j] < arr[k]){
                    k = j; //记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束,也就是找到本轮循环的最小的数以后,再进行交换
            if(i != k)
            {
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }
        return arr;
    }

评论

还没有任何评论,你来说两句吧

粤ICP备17155863号

- 友情链接 - Theme by Qzhai