冒泡排序

基本介绍

冒泡排序的英文Bubble Sort,是一种最基础的交换排序。之所以叫做冒泡排序,是因为这种排序算法的每一个元素都可以像气泡一样,根据自身大小,一点一点向着数组的一侧移动。
冒泡排序的基本思想是:通过对排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素从前移向后部。
原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素,轮转的次数和元素数量相当,所以时间复杂度是O(N^2)。

冒泡排序

冒泡排序规则

  • 一共进行数组的大小-1次大的循环
  • 每一躺排序的次数在逐渐减少
  • 如果我们发现在某趟排序中没有发生一次交换,可以提前结束冒泡排序。

冒泡排序的代码实现

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = new int[] { 7, -1, 6, 18, 22, 5, 4 };
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int tmp; // 用于数据交换
        boolean flag = false; // 用于标记是否进行过交换
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j+1]){
                    flag = true;
                    tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
            if(!flag){  //说明没有进行过交换,排序已经结束。此时退出循环,不再进行排序
                break;
            }
        }
    }
}

选择排序

基本介绍

选择式排序也属于内部排序法,是从欲排序的数据中,按指定的规则选出某一元素,再依规定交换位置后达到排序的目的。
选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。

算法演示

选择排序的基本思想

  • 第一次从 arr[0]~arr[n-1]中选取最小值, 与 arr[0]交换
  • 第二次从 arr[1]~arr[n-1]中选取最小值,与 arr[1]交换
  • 第三次从 arr[2]~arr[n-1]中选取最小值,与 arr[2] 交换,
  • …,
  • 第 i 次从 arr[i-1]~arr[n-1]中选取最小值,与 arr[i-1]交换,
  • …,
  • 第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值, 与 arr[n-2]交换,
  • 总共通过 n-1 次,得到一个按排序码从小到大排列的有序序列。

选择排序注意点

1.选择排序一共有【数组大小-1】轮排序
2.每一轮排序,又是一个循环,循环的规则

  • 先假定当前这个数是最小的数,
  • 然后和后面的每个数进行比较,如果发现有比当前数更小的数,就重新确定最小数,并得到下标
  • 当遍历到数组的最后时,就得到本轮最小数和下标
  • 交换

选择排序的代码实现

import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = new int[] { 10, -3, 7, 20, 87, 4, 1 };
        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
        selectSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
    }

    public static void selectSort(int[] arr) {
        int minIndex = 0;
        int min = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    minIndex = j;
                    min = arr[j];
                }
            } // 此时完成第一轮

            // 然后将两个值进行交换
            arr[minIndex] = arr[i];
            arr[i] = min;
            // 第一遍循环完成

        }
    }
}

Last modification:December 18th, 2020 at 12:52 am
如果觉得我的文章对你有用,请随意赞赏