Fork me on GitHub

排序算法归纳总结

排序算法一直以来是我学的比较乱的一个部分,分不太清很多常用算法的特点。这次趁着写博客,我仔细捋一捋我听说过的算法。wiki百科上给出了很全的算法目录,我点了点,有一半的算法连名字都没听过,尤其是不实用算法的那五个,就不多做阐述了。

本篇博客排序的适用规模从小到大。

在讲解算法之前,要先考虑清楚,一个算法孰优孰劣,应该有怎样的评判标准。我觉得wiki百科上给出的几点很明确了,我就在这里直接引用了。

评判标准:

  • 计算的时间复杂度:(最差、最优及平均),依据列表的大小(n)。一般而言,好的性能是O($nlogn$),坏的性能是O($n^2$)。
  • 内存使用量:以及其他电脑资源的使用
  • 稳定性:稳定排序算法会让原本有相同键值的记录维持相对次序。比如说5,2,5,6,排完序后第一个5依然在第二个5之前,称稳定。但很多情况下,排列的元素并不会只是一个数字,多数为有很多属性的元素,所以稳定性就显得格外重要。

冒泡排序

工作原理:重复走访过要排序的数列,一次比较两个元素,如果顺序错误就把他们交换过来,重复至到没有再需要交换,则排序完成。

算法描述:
1、比较相邻元素。如果第一个比第二个大(或小),则交换。
2、对当前范围每一对相邻元素做比较。结束时,最后的元素是最大值(或最开始的元素是最小值)。
3、缩小比较范围。
4、重复操作2、3,直至范围变为1,即不再需要比较。

计算的时间复杂度

  • 最坏:O($n^2$)
  • 最优:O(n)
  • 平均:O($n^2$)

内存使用量

  • 空间复杂度:需要辅助空间O(1)

稳定性稳定

特点:简单,稳定,但效率低下。

Java代码:

public static void bubbleSort(int arr[]){
        int len=arr.length;
        for(int i=0;i<len-1;i++){
            for(int j=0;j<len-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }

示意图

鸡尾酒排序

鸡尾酒排序属于冒泡排序的一种变形,不同的是冒泡每次循环是单向,但鸡尾酒是双向。

大部分特点与冒泡排序一样。若排序是大部分已经排序过的话,会接近O(n)。

示意图

选择排序

工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

算法描述:
1、将未排序序列的第一个元素标记为最小值
2、遍历当前未排序序列,找出最小值并标记
3、将最小值放至已排序序列末尾
4、重复1、2、3,直至未排序序列为空

计算的时间复杂度

  • 最优、最差及平均:O($n^2$)

内存使用量

  • 空间复杂度:需要辅助空间O(1)

稳定性不稳定

特点:数据量较小时,选择排序比冒泡排序要快。原地操作几乎是选择排序的唯一优点,空间复杂度要求较高时,可选择此排序;然而实际应用比较罕见。

Java代码:

public static void selectionSort(int[] arr) {
        int i, j, min, temp, len = arr.length;
        for (i = 0; i < len - 1; i++) {
            min = i;//未排序序列中最小数据数组下标
            for (j = i + 1; j < len; j++)//在未排序元素中继续寻找最小元素,并保存其下标
                if (arr[min] > arr[j]){
                    min = j;}
            temp = arr[min]; //将最小元素放到已排序序列的末尾
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }

示意图

插入排序

工作原理:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。其实插入排序的过程与玩手牌一样,从后往前查看比较,找到相应的位置插入即可。

算法描述:
1、从第一个元素开始,可以认为它已被排序
2、取出下一个元素,在已排序序列中从后往前扫描
3、若某元素大于新元素,将该元素移至下一位置,如此重复,直至找到小于新元素的位置,将新元素插入该位置后
4、重复操作3

计算的时间复杂度

  • 最坏:O($n^2$)
  • 最优:O(n)
  • 平均:O($n^2$)

内存使用量

  • 空间复杂度:需要辅助空间O(1)

稳定性稳定

特点:不适合数据量比较大的排序应用。如果数据量小于千,或输入元素大致上按顺序排列,那么插入排序是一个不错的选择。

Java代码:

public static void insertionSort( int[] arr ){
        for( int i=0; i<arr.length-1; i++ ) {
            for( int j=i+1; j>0; j-- ) {
                if( arr[j-1] <= arr[j] )
                    break;
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }

示意图

希尔排序

也称递减增量排序算法,是插入排序的一种更高效的改进版本。

工作原理:将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素一次性地朝最终位置前进一大步,然后算法再取越来越小的步长进行排序,到最后一步,即变成了普通的插入排序。不过在最后,所有数据基本已经排序好了。

算法描述:
例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

然后再以3为步长进行划分:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序后:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后再以1为步长进行排序,此时就是简单的插入排序了

重点:步长的选择是希尔排序的重要部分

Donald Shell(设计者)最初建议选择步长为n/2

已知的最好步长序列是(1,5,19,41,109,……)(详情见希尔排序

计算的时间复杂度

  • 最优:O(n)
  • 最差:O($(nlogn)^2$)
  • 平均:O($(nlogn)^2$)

内存使用量

  • 空间复杂度:需要辅助空间O(1)

稳定性不稳定

特点:在使用最优步长序列时,比插入排序快。在较小数组中,比快速排序和堆排序还要快。但若涉及大量数据,速度依旧不及快速排序。

Java代码:

public static void shellSort(int[] arr) {
    int gap = 1, i, j, len = arr.length;
    int temp;
    while (gap < len / 3)
        gap = gap * 3 + 1; 
    for (; gap > 0; gap /= 3)
        for (i = gap; i < len; i++) {
            temp = arr[i];
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                arr[j + gap] = arr[j];
            arr[j + gap] = temp;
        }
}

这里的代码中的步长取n/3

示意图

归并排序

工作原理:归并排序是采用分治法的一个非常典型的应用。归并排序的思想是先递归分解数组,再合并数组。

算法描述(迭代法):
1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2、设定两个指针,最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4、重复步骤3直到某一指针到达序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾

合并:基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

分解:基本思路是将数组分解成left和right,如果这两个数组内部数据是有序的,那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的?可以再二分,直至分解出的小组只含有一个元素时为止,此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

计算的时间复杂度

  • 最优、最差及平均:O($nlogn$)

内存使用量

  • 空间复杂度:所需辅助空间O(n)

稳定性稳定

Java代码(迭代版):

public static void mergeSort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    int block, start;

    // 原版代码的迭代次数少了一次,没有考虑到奇数列数组的情况
    for(block = 1; block < len; block *= 2) {
        for(start = 0; start <len; start += 2 * block) {
            int low = start;
            int mid = (start + block) < len ? (start + block) : len;
            int high = (start + 2 * block) < len ? (start + 2 * block) : len;
            //两个块的起始下标及结束下标
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            //开始对两个block进行归并排序
            while (start1 < end1 && start2 < end2) {
            result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            }
            while(start1 < end1) {
            result[low++] = arr[start1++];
            }
            while(start2 < end2) {
            result[low++] = arr[start2++];
            }
        }
    int[] temp = arr;
    arr = result;
    result = temp;
    }
    result = arr;       
}

示意图

快速排序

工作原理:快速排序主要采取分治法,将大问题逐步划分为小问题,逐个解决。

算法描述:
1、从数列中挑出一个元素,称为“基准”。
2、分区:所有比基准值小的元素摆在基准前面,所有比基准值大的元素摆在基准后面。分区结束时,基准应位于数列中间。
3、对左右区间递归执行操作2,直至各区间只有一个数。

计算的时间复杂度

  • 最坏:O($n^2$)
  • 最优:O($nlogn$)
  • 平均:O($nlogn$)

内存使用量

  • 空间复杂度:需要辅助空间O($logn$)

稳定性不稳定

特点:通常情况下,快速排序比其他O($nlogn$)算法更快。

Java代码:

public static void quickSort(int arr[],int head,int tail){
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        int i = head, j = tail, pivot = arr[(head + tail) / 2];
        while (i <= j) {
            while (arr[i] < pivot) {
                ++i;
            }
            while (arr[j] > pivot) {
                --j;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;
            } else if (i == j) {
                ++i;
            }
        }
        quickSort(arr, head, j);
        quickSort(arr, i, tail);
    }

示意图

堆排序

顾名思义,堆排序是利用堆这种数据结构所设计的一种排序算法,采用的是二叉堆

二叉堆性质
1、父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2、每个节点的左右子树都是一个二叉堆(都是最大堆或最小堆)。

算法描述:
1、构造最大堆(Build_Max_Heap):若数组下标范围为0~n,考虑到单独一个元素是大根堆,则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始,向前依次构造大根堆,这样就能保证,构造到某个节点时,它的左右子树都已经是大根堆。

2、堆排序(HeapSort):由于堆是用数组模拟的。得到一个大根堆后,数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点,并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换,再对heap[0…n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换,再对heap[0…n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间,故操作完后整个数组就是有序的了。

3、最大堆调整(Max_Heapify):该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整,使得子节点永远小于父节点 。

上面这个是从大佬的博客拷来的步骤,说实话,太官方太仔细了些,我看不太懂。不过我看了几遍大佬博客下面的示意图后,明白了大概步骤,下面就整理一下。

步骤:
1、将数组构造为最大堆,在构造的过程中每一步都要检测当前堆是否为最大堆,如果不是,则进行调整
2、将第一个根节点与末节点互换后,移除末节点。移除出的末节点,就是堆中的最大数。
3、重新构建最大堆
4、重复步骤2、3,直至堆只有一个节点后再移除,则得到排列好的序列

计算的时间复杂度

  • 最优、最差及平均:O($nlogn$)

内存使用量

  • 空间复杂度:所需辅助空间O(n)

稳定性不稳定

Java代码:

public class HeapSort {

    private int[] arr;

    public HeapSort(int[] arr){
        this.arr = arr;
    }

    /**
     * 堆排序的主要入口方法,共两步。
     */
    public void sort(){
        /*
         *  第一步:将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点,根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1; 
        for(int i = beginIndex; i >= 0; i--){
            maxHeapify(i, len);
        }

        /*
         * 第二步:对堆化数据排序
         * 每次都是移出最顶层的根节点A[0],与最尾部节点位置调换,同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素,使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }

    private void swap(int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 调整索引为 index 处的数据,使其符合堆的特性。
     * 
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆(数组)的长度
     */
    private void maxHeapify(int index,int len){
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引,默认左子节点。

        if(li > len) return;       // 左子节点索引超出计算范围,直接返回。
        if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点,哪个较大。
            cMax = ri;
        if(arr[cMax] > arr[index]){
            swap(cMax, index);      // 如果父节点被子节点调换,
            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }

    /**
     * 测试用例
     * 
     * 输出:
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};        
        new HeapSort(arr).sort();        
        System.out.println(Arrays.toString(arr));
    }

}

示意图

总结

PS:

  • Timsort是结合了合并排序与插入排序的算法,效率很好Java SE7、Android与python均采用Timsort算法对数组排列。(后续会更新此算法介绍)

参考资料:

-------------本文结束感谢您的阅读-------------