排序算法

数据结构与算法 / 算法
Word count: 6.7k   |   Reading time≈ 26 min

快速排序、归并排序，面试很重要，甚至要求现场写

其他多问思想、使用场景

排序经常放在面试的开头

排序算法概述

即使你只是使用标准库中的排序函数，学习排序算法仍然有三大实际意义：

  • IT从业人员必备技能，也是互联网公司面试的必考点；
  • 类似的技术也能有效解决其他类型的问题；
  • 排序算法常常是我们解决其他问题的第一步。

数据结构和算法中，关于排序有十大算法，包括冒泡排序，简单选择排序，简单插入排序，希尔排序、**归并排序，快速排序、堆排序，计数排序，桶排序、基数排序**。

1.冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为相关的元素会经由交换慢慢“浮”到数列的顶端。

基本思路：

1、比较相邻的元素。如果第一个比第二个大(小)，就交换它们两个；

2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大(小)的数；

3、针对所有的元素重复以上的步骤，除了最后一个；

重复步骤1~2，直到排序完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class BubbleSort{
    public static int[] sort(int[] array){
        if(array.length == 0){
            return array;
        }
        
        for(int i = 0; i < array.length; i++){
            for(int j = 0; j < array.length-1-i; j++){
                if(array[j+1] < array[j]){
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
    
    
    
    public static void main(String[] args){
        int[] src = {86,11,77,23,32,45,58,63,93,4,37,22};
        //打印原数组
        print(src);
        
        System.out.println("=====================");
        
        //打印排序后新数组
        int[] dest = BubbleSort.sort(src);
        print(dest);
        
    }
    
    public void print(int[] src){
        for(int i : src){
            System.out.print(i + " ");
        }
        System.out.println("");
    }
}

2.简单选择排序（整体选最值）

选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。
但是过程不同，
冒泡排序是通过相邻的比较和交换；
而选择排序是通过对整体的选择。

其实选择排序可以看成冒泡排序的优化，因为其目的相同，
只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。

具体步骤：

首先，找到数组中最大（小）的那个元素；

其次，将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换）；

再次，在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int[] sort(int[] array){
    if(array.length == 0) return array;
    
    for(int i = 0; i < array.length; i++){
        int minIndex = i; //存放最小数的下标
        for(int j = i; j < array.length; j++){
            //找到该轮最小数
            if(array[j] < array[minIndex]){
                minIndex = j;
            }
        }
        //交换
        int temp = array[minIndex];
        array[minIndex] = array[i];
        array[i] = temp;
    }
    
    return array;
}

3.简单插入排序

索引0位置默认是已排序数据的索引

待排序、已排序数据的索引

插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。

打扑克牌，在分牌时可能要整理自己的牌，牌多的时候怎么整理呢？就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。

举个例子，我们将要收到5,3,4,,8,6这几张牌，我们先收到5这张牌，毫无疑问，这张牌的位置是正确的，没必要整理。接着收到了牌3，然后3要插到5前面，把5后移一位，变成3,5。接着又收到了牌4，现在我们会怎么做？把4插入到5前面，把5后移一位。

具体步骤：

  • 对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

  • 为了给要插入的元素腾出空间，我们需要将插入位置之后的已排序元素在都向右移动一位。

插入排序所需的时间取决于输入中元素的初始顺序。
例如，对一个很大且其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

总的来说，插入排序对于部分有序的数组十分高效，也很适合小规模数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] sort(int[] array){
    if(array.length == 0) return array;
    
    int currentValue; // 记录当前待排序的数字是多少
    for(int i = 0; i < array.length - 1; i++){ //默认 索引0 位置的元素是有序的
        int preIndex = i;
        currentValue = array[preIndex+1];
        while(preIndex >= 0 && array[preIndex] > currentValue){
            //往后挪一个 并继续向前比较
            array[preIndex+1] = array[preIndex];
            preIndex--;
        }
        //找到当前一轮最后的位置
        array[preIndex + 1] = currentValue;//当前比较的数字不用挪了 直接放在其下一个位置即可
       
    }
    return array;
}

4.希尔排序（缩小增量）

数组的长度/2 来获得增量序列

一种基于插入排序的快速的排序算法

希尔排序为了加快速度简单地改进了插入排序，也称为缩小增量排序，同时该算法是冲破O(n^2）的第一批算法之一。

增量为3.png

希尔排序是把待排序数组按一定增量的分组，对每组使用直接插入排序算法排序；然后缩小增量继续分组排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减至 1 时，整个数组恰被分成一组，排序便完成了。这个不断缩小的增量，就构成了一个增量序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] sort2(int[] array){
        if (array.length == 0) return array;

        int gap = array.length/2; //增量

        int currentValue; //当前gap待排序数字
        while (gap > 0){
            //进行当前gap的简单插入排序算法
            for (int i = gap; i < array.length; i++){
                currentValue = array[i];
                int preIndex = i - gap;
                while(preIndex >= 0 && currentValue < array[preIndex]){
                    //往后挪
                    array[preIndex + gap] = array[preIndex];
                    preIndex = preIndex - gap;
                }
                array[preIndex + gap] = currentValue;
            }
            gap = gap/2; //增量每次变为原来的二分之一
        }

        return array;
    }

5.归并排序（合并有序子数组）

归并排序（Merge Sort） 是一种高效的、基于分治策略的排序算法。 它将一个大问题分解成小问题来解决，然后再将小问题的结果合并以得到最终的解决方案。 归并排序特别适合于对大数据集进行排序，并且是一种稳定的排序算法（即相等元素的相对位置在排序后不会改变）。

算法步骤：

  1. 分割（Divide）： 将待排序的数组递归地分割成更小的子数组，直到每个子数组只包含一个元素。 因为只有一个元素的数组自然是有序的。
  2. 合并（Conquer）： 将这些小的有序子数组两两合并，创建一个更大的有序数组。 这个过程重复进行，直到整个数组都被合并成一个有序数组。

核心思想：

  • 分治法（Divide and Conquer）： 将问题分解为更小的子问题，解决子问题，然后将子问题的解合并。
  • 递归（Recursion）： 递归地应用分割和合并步骤，直到问题足够小可以直接解决。

具体过程：

  1. 分割： 找到数组的中间位置，将数组分成两个子数组（左半部分和右半部分）。
  2. 递归排序： 递归地对左半部分和右半部分进行归并排序。
  3. 合并： 将两个已经排序的子数组合并成一个更大的有序数组。 这是归并排序的关键步骤。 合并过程通常需要创建一个临时数组，用于存放合并后的有序元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int[] sort3(int[] array) {
        if (array.length == 0) return array;

        //拆分
        int mid = array.length / 2;

        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);

        //合并两个有序数组
        return merge(sort3(left), sort3(right));
    }

    //合并两个有序数组并返回
    private int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];

        for (int index = 0, leftIndex = 0, rightIndex = 0; index < result.length; index++) {
            if (leftIndex >= left.length) { //left数组中的所有元素都已经被添加到result数组中
                result[index] = right[rightIndex++];
            } else if (rightIndex >= right.length) {
                result[index] = left[leftIndex++];
            } else if (left[leftIndex] < right[rightIndex]) {//还在比较范围之内的情况
                result[index] = left[leftIndex++];
            } else {
                result[index] = right[rightIndex++];
            }
        }

        return result;
    }

6.快速排序（基准数分区操作）

快速排序被誉为20 世纪科学和工程领域的十大算法之一。快速排序（Quicksort）是对冒泡排序的一种改进，也是采用分治法的一个典型的应用。

​ 首先任意选取一个数据（比如数组的第一个数）作为关键数据，我们称为基准数，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序，也称为分区（partition）操作。在实际实现时，一般会在原数组上直接操作。

​ 通过一趟快速排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

为了提升性能，有时我们在分割后独立的两部分的个数小于某个数（比如15）的情况下，会采用其他排序算法，比如插入排序。

  1. 当前元素 >= 基准数，我们不做任何变化。
  2. 当前元素 <= 基准数时，分割（分区）指示器右移一位，
    • 当前元素下标 <= 分割指示器下标，当前元素，保持不动
    • 当前元素下标 > 分割指示器下标，当前元素和分割指示器所指元素交换；

数比基准数大 不变
数比基准数小or相等 指示器右移
下标比指示器大 交换

比较和交换操作比较频繁，单独定义一个方法swap()用于交换数组中的两个元素

zoneIndex（ 完成了一次分区操作以后的返回值 一轮下来之后位置正确的数的返回值）分区指示器没有放在我们数组的最开始，分区指示器前面还有元素，应递归调用sort方法本身

分区操作partition()
首先要有基准数（基准数可以用随机数表示）
要有一个分区指示器zoneIndex作为结果返回出去
zoneIndex最开始是start-1

交换基准数和数组尾元素（将基准数放在最后）

交换完之后进行遍历

递归调用排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private int[] quickSort(int[] array, int start, int end) {
    if (array.length < 1 || start < 0 || end >= array.length || start > end) {
        return null;
    }

    //进行一轮之后获得的正确位置的数字的索引（快速排序）
    int zoneIndex = partition(array, start, end);

    //将剩下的区域继续进行快速排序
    if (zoneIndex > start) {
        quickSort(array, start, zoneIndex - 1);
    }
    if (zoneIndex < end) {
        quickSort(array, zoneIndex + 1, end);
    }
    return array;
}

private int partition(int[] array, int start, int end) {
    //基准数
    int pivotIndex = (int) (start + Math.random() * (end - start + 1));
    //分区指示器
    int zoneIndex = start - 1;
    //交换基准数所在位置 和 尾部元素的位置
    swap(array, pivotIndex, end);
    //遍历
    for (int i = start; i <= end; i++) {
        if (array[i] <= array[pivotIndex]){
            zoneIndex++;
            //当前索引比 pivotIndex 大时，就交换两种位置
            if (i > pivotIndex){
                swap(array,pivotIndex,i);
            }
        }
    }
    return zoneIndex;
}

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

7.堆排序（完全二叉树 二叉堆）

许多应用程序都需要处理有序的元素，但不一定要求他们全部有序，或者不一定要一次就将他们排序，很多时候，我们每次只需要操作数据中的最大元素（最小元素），那么有一种基于二叉堆的数据结构可以提供支持。

所谓二叉堆，是一个完全二叉树的结构，同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在一个二叉堆中，根节点总是最大（或者最小）节点。

完全二叉树：是由满二叉树而引出来的，如果我们将一棵满二叉树由上到下，由左至右，每个结点都用数字编号，另外一个二叉树也同样由上到下，由左至右，每个结点都用数字编号，二叉树中的每个结点都可以在满二叉树中一一对应，我们称这个二叉树为完全二叉树。所以一棵满二叉树一定是个完全二叉树，而完全二叉树不是满二叉树。

完全二叉树.png

推论1：对于位置为 K 的结点 左子结点 = 2 × k + 1 右子结点=2 × ( k + 1 )

推论2：最后一个非叶节点的位置为 ( N / 2 ) - 1，N 为数组长度。

按照数组下标构建一颗完全二叉树，后面调整为堆的定义

步骤：

  • 构建一个最大堆/最小堆（将二叉树调整为最大堆）从最后一个非叶结点(N/2)-1开始，从下到上、从右到左。（后面就是重新调整堆的操作）
  • 正式开始堆排序过程
    • 依次取堆顶元素
    • 将堆顶元素和尾元素进行交换
    • 将尾结点剥离
    • 重新调整堆 adjustHeap(array，i) 传入数组和当前要调整的树的根节点

不断将最大值放在堆尾，再从其他里面找最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//堆排序
int len;

public int[] heapSort(int[] array) {
    if (array.length < 1) return array;
    len = array.length;

    //构建一个最大堆
    buildMaxHeap(array);

    //不断取出堆顶元素
    while (len > 0) {
        //交换堆顶和堆位元素
        swap(array, 0, len - 1);
        //取出堆尾元素
        len--;
        //调整剩余元素为最大堆
        adjustMaxHeap(array, 0);
    }
    return array;
}

//构建最大堆---------------------------------------
private void buildMaxHeap(int[] array) {
    //从最后一个非叶节点开始，从下到上，从右到左
    for (int i = (len / 2) - 1; i >= 0; i--) {
        adjustMaxHeap(array, i);
    }
}

//调整为新的最大堆----------------------------------
private void adjustMaxHeap(int[] array, int i) {
    //i为需要调整的树的根节点
    int maxIndex = i; //保存最大数的索引
    int leftIndex = i * 2 + 1;
    int rightIndex = i * 2 + 2;
    if (leftIndex < len && array[leftIndex] > array[maxIndex]) {
        maxIndex = leftIndex;
    }
    if (rightIndex < len && array[rightIndex] > array[maxIndex]) {
        maxIndex = rightIndex;
    }
    if (maxIndex != i) {
        //交换位置
        swap(array, maxIndex, i);
        //调整可能不符合堆的节点
        adjustMaxHeap(array, maxIndex);

    }
}

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

8.计数排序

计数排序是一个排序时不比较元素大小的排序算法。

计数排序对一定范围内的整数排序时候的速度非常快，一般快于其他排序算法。但计数排序局限性比较大，只限于对整数进行排序，而且待排序元素值分布较连续、跨度小的情况。

如果一个数组里所有元素都是整数，而且都在0-K以内。那对于数组里每个元素来说，如果能知道数组里有多少项小于或等于该元素，就能准确地给出该元素在排序后的数组的位置。

计数排序.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public int[] counterSort(int[] array) {
    if (array.length == 0) return array;

    //计算最大值 最小值
    int min = array[0];
    int max = array[0];
    for (int i = 0; i < array.length; i++) {
        if (array[i] < min) {
            min = array[i];
        }
        if (array[i] > max) {
            max = array[i];
        }
    }
    //偏移量
    int bias = 0 - min;
    int[] counterArray = new int[max - min + 1];
    Arrays.fill(counterArray, 0);//填充0

    //统计计数
    for (int value : array) {
        counterArray[value + bias]++;
    }

    //排序--------
    int index = 0; //原始数组下标
    int i = 0; //计数器下标
    while (index < array.length) {
        if (counterArray[i] != 0) {
            array[index] = i - bias; //写回原始数组
            counterArray[i]--;
            index++;
        } else {
            i++;
        }
    }
    return array;
}



//-----------------------------排序另一个方式
    int index = 0;
    for (int i = 0; i < counterArray.length; i++) {
        while (counterArray[i] > 0) {
            array[index++] = counterArray[i] - bias;
            counterArray[i]--;
        }
    }

9.桶排序

每个桶中放置不同的数值

桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，利用某种函数的映射关系将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序）。

桶排序.png

基本步骤是：

  • 根据输入建立适当个数的桶，每个桶可以存放某个范围内的元素；
  • 将落在特定范围内的所有元素放入对应的桶中；
  • 对每个非空的桶中元素进行排序，可以选择通用的排序方法，比如插入、快排；
  • 按照划分的范围顺序，将桶中的元素依次取出。排序完成。

桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//桶排序
public static ArrayList<Integer> sort(ArrayList<Integer> array, int bucketSize) {
    if (array==null || array.size() <2){
        return array;
    }
    int max = array.get(0);
    int min = array.get(0);
    //找最大值 最小值
    for (int i = 0; i < array.size();i++){
        if (array.get(i)>max){
            max = array.get(i);
        }
        if (array.get(i) < min){
            min = array.get(i);
        }
    }

    //获得桶的数量
    int bucketCount = (max - min)/bucketSize+1;
    //构建桶
    ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
    ArrayList<Integer> resultArr = new ArrayList<>();
    for (int i = 0; i < bucketCount;i++){
        bucketArr.add(new ArrayList<Integer>());
    }
    //将原始数组中的数据分配到桶中
    for (int i =0; i < array.size();i++){
        bucketArr.get((array.get(i)-min)/bucketSize).add(array.get(i));
    }
    /**
     * 桶排序
     */
    for (int i = 0; i < bucketCount;i++){
        if (bucketSize == 1){
            for (int j = 0; j < bucketArr.get(i).size();j++){
                resultArr.add(bucketArr.get(i).get(j));
            }
        }else {
            if (bucketCount == 1){
                bucketSize--;                                        
            }
            //排序
            ArrayList<Integer> temp = sort(bucketArr.get(i),bucketSize);
            for (int j = 0; j < temp.size();j++){
                resultArr.add(temp.get(j));
            }
        }
    }
    return resultArr;
}

10.基数排序

常见的数据元素一般是由若干位组成的，比如字符串由若干字符组成，整数由若干位0~9数字组成。

基数排序按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，同时每一轮排序都基于上轮排序后的结果；当我们将所有的位排序后，整个数组就达到有序状态。

比如对于数字2985，从右往左就是先以个位为关键字进行排序，然后是十位、百位、千位，总共需要四轮。基数排序不是基于比较的算法。

基数是什么意思？对于十进制整数，每一位都只可能是0~9中的某一个，总共10种可能。那10就是它的基，同理二进制数字的基为2；对于字符串，如果它使用的是8位的扩展ASCII字符集，那么它的基就是256。

image.png 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//基数排序
public static int[] jishuSort(int[] array) {
    if (array == null || array.length < 2) {
        return array;
    }
    //找出最大数
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        max = Math.max(max, array[i]);
    }

    //先算出最大数的位数
    int maxDigit = 0;
    while (max != 0) {
        max /= 10;
        maxDigit++;
    }
    
    //构建桶
    ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
    for (int i = 0; i < 10; i++) {
        bucketList.add(new ArrayList<Integer>());
    }
    /**
     * 按照从右往左的顺序，依次将每一位都当做一次关键字，然后按照该关键字对数组排序，
     * 每一轮排序都基于上轮排序后的结果
     */
    int mod = 10, div = 1;
    for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {//共有maxDigit轮
        //遍历原始数组，投入桶中
        for (int j = 0; j < array.length; j++) {
            int num = (array[j] % mod) / div;//每次取最低位
            bucketList.get(num).add(array[j]);//放入对应数字的桶中
        }
        //桶中的数据写回原始数组，清除桶，准备下一轮排序
        int index = 0;
        for (int j = 0; j < bucketList.size(); j++) {
            for (int k = 0; k < bucketList.get(j).size(); k++) {
                array[index++] = bucketList.get(j).get(k);
            }
            //清空桶
            bucketList.get(j).clear();
        }
    }
    return array;
}

11.外部排序

排序算法总结

总结.png

名词解释

算法的稳定性

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，前一个键排序的结果可以为后一个键排序所用。

复杂度

所以好的算法应该具备时效高和存储低的特点。

「时效」是指时间效率，也就是算法的执行时间，对于同一个问题的多种不同解决算法，执行时间越短的算法效率越高，越长的效率越低；

「存储」是指算法在执行的时候需要的存储空间，主要是指算法程序运行的时候所占用的内存空间。

我们在讨论算法复杂度时，往往需要考虑这个待处理数据的大小，我们把待处理数据的大小称之为数据的规模大小。讨论一个算法的复杂度，往往也就是寻找程序的运行时间是如何随着问题规模的变化而变化。

而有的时候算法的运行时间还取决于数据本身分布性质而不仅仅是「问题的规模大小」。对于这样的算法，我们把它们的执行情况分为「最优情况」、「最坏情况」和「平均情况」来讨论。

某个特定的数据集能让算法的执行情况极好，这就是最「最好情况」，而另一个不同的数据会让算法的执行情况变得极差，这就是「最坏情况」。不过在大多数情况下，算法的执行情况都介于这两种极端情况之间，也就是「平均情况」。

对于「最优情况」，没有什么大的价值，因为它没有提供什么有用信息，反应的只是最乐观最理想的情况，没有参考价值。「平均情况」是对算法的一个全面评价，因为它完整全面的反映了这个算法的性质，但从另一方面来说，这种衡量并没有什么保证，并不是每个运算都能在这种情况内完成。而对于「最坏情况」，它提供了一种保证，这个保证运行时间将不会再坏了，所以一般我们所算的时间复杂度是最坏情况下的时间复杂度，这和我们平时做事要考虑到最坏的情况是一个道理。。

时间复杂度

一个算法执行所耗费的时间。

空间复杂度

对一个算法在运行过程中临时占用存储空间大小的量度。

常见复杂度

在各种不同算法中，若算法中语句执行次数(占用空间)为一个常数，则复杂度为O(1)；

当一个算法的复杂度与以2为底的n的对数成正比时，可表示为O(log n)；当一个算法的复杂度与n成线性比例关系时，可表示为O (n)，依次类推。

由小到大：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

排序算法时间复杂度助记

总结.png

冒泡、选择、插入排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(img)（外循环找元素O(n)，内循环找位置O(n)）

快速、归并、希尔、堆基于分治思想，log以2为底，平均时间复杂度往往和O(nlogn)（外循环找元素O(n)，内循环找位置O(logn)）相关

基数排序时间复杂度为O（N*M），其中N为数据个数，M为数据位数

快速排序的优势

从平均时间来看，快速排序是效率最高的：

快速排序中平均时间复杂度O(nlog n)，这个公式中隐含的常数因子很小，比归并排序的O(nlog n)中的要小很多，所以大多数情况下，快速排序总是优于合并排序的。

而堆排序的平均时间复杂度也是O(nlog n)，但是堆排序存在着重建堆的过程，它把根节点移除后，把最后的叶子结点拿上来，是为了重建堆，但是，拿上的值是要比它的两个叶子结点要差很多的，它要比较很多次，才能回到合适的位置。堆排序就会有很多的时间耗在堆调整上。

虽然快速排序的最坏情况为排序规模（n）的平方关系，但是这种最坏情况取决于每次选择的基准， 对于这种情况，已经提出了很多优化的方法，比如三取样划分和Dual-Pivot快排。

同时，当排序规模较小时，划分的平衡性容易被打破，而且频繁的方法调用超过了O(nlog n)为O(img)省出的时间，所以一般排序规模较小时，会改用插入排序或者其他排序算法。

Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2023-2025 Annie
  • Visitors: | Views:

嘿嘿 请我吃小蛋糕吧~

支付宝
微信