数据结构之排序算法

Ghero 2020-05-03

数据结构之排序算法

一、前言

排序算法的评价指标:

  1. 算法执行效率
  • 最好、最坏以及平均时间复杂度。注意:原始数据有序度的不同,对排序的执行时间有很大的影响
  • 时间复杂度的系数、常数、低阶。注意:实际开发中,数据规模可能很小,因此需要考虑这几个方面
  • 比较次数和交换次数。注意:基于比较的排序算法会涉两个基本的操作,即元素比较大小和元素交换或者移动

2.算法的内存消耗

  • 引入原地排序(Sorted in place),即原地排序算法,特指空间复杂度为O(1)

3.算法的稳定性

  • 稳定性指原始原始数据集中存在两个相等的元素,在排序过后,两个元素的前后相对顺序不发生改变。不改变为稳定的排序,否则为不稳定的排序。

二、时间复杂度为O(n2)的排序算法

  • 冒泡排序(Bubble Sort)
  1. 核心思想:对相邻的两个元素进行比较,看是否满足大小关系要求。
  2. 核心代码:
//排序方法
    public static void bubbleSort(int[] arr){
        //首先判断数组的大小
        if (arr.length <= 1){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {//冒泡的趟数for (int j = 0; j < arr.length - 1 - i; j++) {//交换次数
                if (arr[j] > arr[j + 1]){
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }重点:冒泡的次数i为:数组的长度n - 1;每次冒泡的比较次数j = n - i - 1代码优化:
//优化的排序方法
    public static void bubbleSort(int[] arr){
        //首先判断数组的大小
        if (arr.length <= 1){
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {//冒泡的趟数
            boolean flag = false;//添加标志位,用于判断是否发生数据交换;若某一趟没有发生交换,说明后续数组已经有序,可以不用进行比较
            for (int j = 0; j < arr.length - 1 - i; j++) {//交换次数
                if (arr[j] > arr[j + 1]){
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;                   flag = true;
                }
            }            if(!flag){                break;            }
        }
    }

  3.算法指标

  • 最好时间复杂度O(n),即原始数组为有序的;最坏时间复杂度O(n2),即原始数组为逆序的;
  • 平均时间复杂度:因原始数组的有序性不同,分析比较复杂。引入“有序度”和“无序度”的概念。
  • 有序度指的是具有有序关系的元素对的个数
  • 完全无序的数组有序度为0;完全有序的数组有序度为n*(n-1)/2,即满有序度
  • 逆序度与有序度相反。逆序度 = 满有序度 - 有序度
  • 排序的过程相当于增加有序度,减少无序度
  • 平均时间复杂度取中间值。n*(n-1)/4,O(n2)
  • 是原地排序算法
  • 是稳定排序算法
  • 插入排序(Insertion Sort)
  • 核心思想:将未排序数组分为已排序区间和未排序区间。将未排序区间的元素与已排序区间的元素依次进行比较,进行插入
  • 核心代码:
public static void insertionSort(int[] arr){//默认从小到大,尾部比较法
        for (int i = 1; i < arr.length; i++) {//此时i代表的是未排序区间中要参与插入的元素以及其位置
            int value = arr[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {//从尾部开始比较,j代表已排序区间的元素个数
                if (arr[j] > value){
                    arr[j + 1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j + 1] = value;
        }
    }
//默认从大到小,头部插入法for (int i = 1; i < arr.length; i++) {    for (int j = 0; j < i ; j++) {        if (arr[j] < arr[i]){            int temp = arr[i];            arr[i] = arr[j];            arr[j] = temp;        }    }}注意:若从小到大排序,则选择尾部插入法;从大到小排序,则选择头部插入法
  • 算法指标
  • 是稳定排序算法
  • 是原地排序算法
  • 最好:O(n);最坏:O(n2);平均时间复杂度:O(n2)
  • 选择排序(Selection Sort)
  • 核心思想:将数组分为待排序区间和已排序区间。从未排序区间中选择元素最小的元素,放到已排序区间的末尾
  • 核心代码:
public static void sectionSort(int[] arr){默认从小到大
        for (int i = 0; i < arr.length - 1; i++) {//比较后元素要插入的位置
            int min = arr[i];
            int minIndex = i;//用于存放最小值的坐标
            for (int j = i + 1; j < arr.length; j++) {//比较区间中最小的元素
                if (min > arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            if (minIndex != i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
    }
  • 算法指标:
  • 原地排序算法、非稳定算法
  • 最好、最坏以及平均时间复杂度都为O(n2)
  • 小结
  1. 算法性能:插入排序 > 选择排序 > 冒泡排序
  2. 三种算法都可以看作将排序区间分为待排序区间和已排序区间
  3. 使用场景:小规模数据排序

相关推荐