性质

稳定性

稳定性指相等的元素经过排序之后相对顺序是否发生了改变。

时间复杂度

对于基于比较的排序算法的时间复杂度,较好的性能是$O(nlogn)$,坏的性能是$O(n^2)$。一个排序算法的理想性能是$O(n)$,但是平均而言不可能达到。

选择排序

Selection sort是较为简单的一种排序算法,每次找到第$i$小的元素,然后将这个元素与数组的第$i$个位置上的元素交换。换句话说:每次找到未完成排序的数组中最小的值,然后将其与边界(已排序和未排序元素的边界)进行交换。

  • 由于swap操作的存在,因此该算法是一种不稳定的排序算法
  • 选择排序的最优、平均、最坏时间复杂度都是$O(n^2)$。两层for

Java:

public static void selection(int[] arr){
	    int n = arr.length;
        for (int i = 1; i < n; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            swap(arr, i, minIndex);
        }
    }

冒泡排序

Bubble Sort由于在算法的执行过程中,较小的元素像气泡一样慢慢浮到数组的顶端,故称为冒泡排序。

工作原理:每次检查相邻的两个元素,如果满足排序条件,则交换。经过$i$次扫描,数组末尾的$i$项必然是第$i$大的元素,因此冒泡排序最多需要扫描$n - 1$遍数组就能完成排序。

  • 稳定的排序算法
  • 序列完全有序时,冒泡排序只需遍历一次数组,不用执行任何交换操作,时间复杂度位$O (n) $
  • 最坏情况下,需要进行$\frac{(n - 1)n}{2} $次交换操作。
  • 平均时间复杂度为$O(n)$
public static void bubbleSort(int[] arr) {
        boolean flag = true;
        while (flag) {
            flag = false;
            for (int i = 1; i < arr.length -1; i++) {
                if (arr[i] > arr[i + 1]) {
                    flag = true;
                    swap(arr, i, i + 1);
                }
            }
        }
    }

插入排序

Insertion Sort:将待排序元素划分为已排序和未排序两部分,每次从未排序元素中选择一个插入到已排序的的元素中的正确位置。

案例:打扑克牌时,从桌上抓一张牌,按牌的大小插入正确的位置。

  • 稳定的排序算法
  • 最优的时间复杂度是$O(n)$
  • 插入排序的最坏、平均时间复杂度为$O(n^2)$
public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

计数排序

Counting Sort:是一种线性时间的排序算法。

工作原理:使用一个额外的数组$C$,其中第$i$个元素是待排序数组$A$中值等于$i$的元素的个数,然后通过数组$C$来将$A$中的元素排到正确的位置。

分为三个步骤:

  1. 计算每个数出现的次数
  2. 求除每个数出现次数的前缀和
  3. 利用出现次数的前缀和,从右至左计算每个数的排名
  • 稳定的排序算法
  • 时间复杂度为$O(n + w)$,其中$w$代表待排序数据的值域大小。
public static int[] countingSort(int[] A){
    //k是元素大小的上界
    int k = 100;
    int[] C = new int[k];
    int[] B = new int[A.length];
    for (int i = 0; i < A.length; i++) {
        C[A[i]]++;
    }
    //求前缀和
    for (int i = 1; i < k; i++) {
        C[i] = C[i] + C[i -1];
    }
    for (int j = A.length -1; j >= 0; j--) {
        int a = A[j];
        B[C[a] - 1] = a;
        C[a]--;
    }
    return B;
}

归并排序

merge sort:是一种采用了分治思想的排序算法。

主要分为三个步骤:

  • 将数组划分为两部分
  • 递归地对两个子序列进行归并排序
  • 合并两个子序列

性质:

  • 是一种稳定的排序算法
  • 最优、最坏、平均时间复杂度均为$O(nlogn)$
  • 归并排序的空间复杂度为$O(n)$
public static void mergeSort(int[] arr, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
        //递归地对左右两边进行排序
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        //合并
        merge(arr, low, mid, high);
    }
}

//merge实际上是将两个有序数组合并成一个有序数组
private static void merge(int[] arr, int low, int mid, int high) {
    //temp数组用于暂存合并的结果
    int[] temp = new int[high - low + 1];
    //左半边的指针
    int i = low;
    //右半边的指针
    int j = mid + 1;
    //合并后数组的指针
    int k = 0;

    //将记录由小到大地放进temp数组
    for (; i <= mid && j <= high; k++) {
        if (arr[i] < arr[j])
            temp[k] = arr[i++];
        else
            temp[k] = arr[j++];
    }
    //接下来两个while循环是为了将剩余的(比另一边多出来的个数)放到temp数组中
    while (i <= mid)
        temp[k++] = arr[i++];

    while (j <= high)
        temp[k++] = arr[j++];

    //将temp数组中的元素写入到待排数组中
    for (int l = 0; l < temp.length; l++)
        arr[low + l] = temp[l];
}

堆排序

Heap Sort:利用数据结构中的堆设计的一种排序算法。

工作原理:对所有待排序元素建堆, 利用最大堆(最小堆)的特性,依次取出堆顶元素,就可以得到排好序的数组。

当前节点的下为$i$时,它的父结点、左子节点、右子节点的获取方式如下:

//向下舍入
parent = floor((i -  1) /2);
leftChild = 2* i + 1;
rightChild = 2 * i + 2;
  • 不稳定的排序算法
  • 最优、平均、最坏时间复杂度均为$O(nlogn)$。
public static void heapSort(int[] arr) {
        //生成大根堆
        int len = arr.length;
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(arr, i, len);
        }
        for (int j = arr.length -1; j > 0; j--) {
            swap(arr, 0, j);
            heapify(arr, 0, j);
        }
    }

    private static void heapify(int[] arr, int i, int length) {
        int temp = arr[i];
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //如果左子节点小于右子节点,k指向右子节点
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            if (arr[k] > temp){
                //如果子节点大于父结点,将子节点值赋值给父结点
                arr[i] = arr[k];
                i = k;
            }else {
                break;
            }
        }
        arr[i] = temp;
    }

快速排序

Quick Sort:简称为快排,也成为分区交换排序。是一种广泛运用的排序算法。

基本原理:通过分治思想实现排序。

  1. 选取基准值,以基准值为界,将比它大的和比它小的分别放在两边。
  2. 对子序列进行递归快排,直至序列为空或者只有一个元素。
public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivotIndex = partition(arr, start, end);
        quickSort(arr, start, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, end);
    }

    /**
     * 分治
     *
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private static int partition(int[] arr, int start, int end) {
        //将第一个元素作为基准元素
        int pivot = arr[start];
        int left = start;
        int right = end;
        while (left != right) {
            //控制right并左移
            while (left < right && arr[right] > pivot) {
                right--;
            }
            //控制left并右移
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            if (left < right) {
                swap(arr, left, right);
            }
        }
        //pivot和指针重合点交换
        arr[start] = arr[left];
        arr[left] = pivot;
        return left;
    }

希尔排序

Shell Sort:最小增量排序,是插入排序的一种改进版本。

工作原理:对不相邻的记录进行比较和移动。

  1. 将待排序数组分成若干个子序列(每个子序列的元素在原始数组中间距相同)
  2. 对这些子序列进行插入排序
  3. 减少每个子序列中元素之间的间距,重复上述过程直至间距减少为1。
  • 不稳定的排序算法
  • 最优时间复杂度为$O(n)$。
  • 平均时间复杂度和最坏时间复杂度与间距序列的选取有关,已知最好的最坏时间复杂度为$O(nlog^2n)$。
  • 空间复杂度为$O(n)$。
public static void shellSort(int[] arr, int length) {
        int h = 1;
        while (h < length / 3) {
            h = 3 * h + 1;
        }
        while (h >= 1) {
            for (int i = h; i < length; i++) {
                for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                    swap(arr, j, j - h);
                }
            }
            h = h / 3;
        }
}

基数排序

Radix Sort:是一种非比较型整数排序算法。

工作原理:将待排序的元素拆分为$k$个关键字,然后先对第$k$个关键字进行稳定排序,再对第$k - 1$个关键字进行稳定排序,……最后对第一个关键字进行稳定排序。

大白话:先根据个位排序,再根据十位排序,再按照百位排序……

基数排序中需要借助一种稳定算法完成内层对关键字的排序。

基数排序根据两种不同的排序顺序,可以分为:

  • LSD(Least significant digital):从低位开始
  • MSD(Most significant digital):从高位开始

性质:

  • 基数排序是一种稳定的排序算法。
  • 如果每个关键字的值域不大,可以使用计数排序作为内层排序,此时复杂度为$O(kn + \sum\limits_{i=1}^{k}w_i)$,其中$w_i$为第$i$个关键字值域的大小,如果关键字值域很大,就可以使用基于比较的$O(nklogn)$的排序。
  • 空间复杂度$O(k + n)$

桶排序

Bucket Sort:是排序算法的一种,适用于待排序数据值域较大但分布较为均匀的情况。

步骤:

  1. 设置一个定量的数组当作空桶
  2. 遍历序列,将元素一个个的放入对应的桶中
  3. 对每个不是空的桶中元素取出来,按序放入序列。

性质:

  • 如果使用稳定的内层排序,并且将元素插入桶中时不改变元素的相对顺序,那么桶排序是一种稳定的排序算法。
  • 桶排序的平均时间复杂度为$O(n + n^2/k + k)$,(将值域平均分成n块 + 排序 + 重新合并元素),当$k \approx n $时为$O(n)$。
  • 最坏时间复杂度为$O(n^2)$。
private static int indexFor(int a, int min, int step) {
        return (a - min) / step;
    }

    public static void bucketSort(int[] arr) {

        int max = arr[0], min = arr[0];
        for (int a : arr) {
            if (max < a)
                max = a;
            if (min > a)
                min = a;
        }
        int bucketNum = max / 10 - min / 10 + 1;
        List buckList = new ArrayList<List<Integer>>();
        // create bucket
        for (int i = 1; i <= bucketNum; i++) {
            buckList.add(new ArrayList<Integer>());
        }
        // push into the bucket
        for (int i = 0; i < arr.length; i++) {
            int index = indexFor(arr[i], min, 10);
            ((ArrayList<Integer>) buckList.get(index)).add(arr[i]);
        }
        ArrayList<Integer> bucket = null;
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            bucket = (ArrayList<Integer>) buckList.get(i);
            insertSort(bucket);
            for (int k : bucket) {
                arr[index++] = k;
            }
        }

    }

    private static void insertSort(List<Integer> bucket) {
        for (int i = 1; i < bucket.size(); i++) {
            int temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j) > temp; j--) {
                bucket.set(j + 1, bucket.get(j));
            }
            bucket.set(j + 1, temp);
        }
    }

参考

OI WIKI

Wikipedia


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!

JVM之Java内存结构(一) 上一篇
2019和2020 下一篇