数据结构和常用排序算法复杂度

1.顺序表

• 插入操作时间复杂度
  最好O(1)，最坏O(n)，平均O(n)
  移动结点的平均次数n/2

• 删除操作时间复杂度
  最好O(1)，最坏O(n)，平均O(n)
  移动结点的平均次数(n-1)/2

• 按值查找时间复杂度
  最好O(1)，最坏O(n)，平均O(n)
  移动结点的平均次数(n+1)/2

2.单链表

• 头插法O(n)
• 尾插法O(n)
• 按序查找O(n)
• 按值查找O(n)
• 插入 删除
  其中插入和删除操作，指定结点O(1),需要从头查找则花费主要用于查找O(n)

3.二叉树

• 二叉树的遍历
  时间复杂度O(n)，空间复杂度O(n)

• 二叉排序树
  插入/删除O(n)

4.图

• 邻接矩阵存储空间
  O(n^2)

• 邻接表存储空间
  无向图O(|V|+2|E|)，有向图O(|V|+|E|)

• 十字链表和邻接多重表存储空间
  O(|V|+|E|)

• 广度优先搜索
  时间复杂度：邻接表O(|V|+|E|)，邻接矩阵O(|V|^2)
  空间复杂度：O(n)

• 深度优先搜索
  时间复杂度：邻接表O(|V|+|E|)，邻接矩阵O(|V|^2)
  空间复杂度：O(n)

• 求最小生成树时间复杂度
  Prim算法：O(|V|^2)
  Kruskal算法：O(|E|log|E|)

• 求最短路径时间复杂度
  Dijkstra算法：O(|V|^2)
  Floyd算法：O(|V|^3)

• 拓扑排序时间复杂度
  O(|V|+|E|)

5. 排序

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

• 内排序：所有排序操作都在内存中完成；
  外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

• 时间复杂度： 一个算法执行所耗费的时间。
  空间复杂度：运行完一个程序所需内存的大小。
  

• n: 数据规模

• k: “桶”的个数

• In-place: 占用常数内存，不占用额外内存

• Out-place: 占用额外内存

冒泡排序

public static int[] bubbleSort(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;
    }

平均时间复杂度: T(n) = O(n²)
最坏时间复杂度: T(n) = O(n²)：当输入的数据是反序时
最好时间复杂度: T(n) = O(n)：当输入的数据已经有序时，只需遍历一遍用于确认数据已有序。
空间复杂度: O(1)
稳定性: 稳定

选择排序

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

public static int[] selectSort(int[] arr) {
    if (arr.length == 0) {
        return arr;
    }

    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
    return arr;
}

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

• 初始状态：无序区为R[1…n]，有序区为空；
• 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
• n-1趟结束，数组有序化了。

平均时间复杂度: T(n) = O(n²)
最坏时间复杂度: T(n) = O(n²)
最好时间复杂度: T(n) = O(n²)
空间复杂度: O(1)
稳定性: 不稳定

插入排序

工作原理 是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

public static int[] insertSort(int[] arr) {
    if (arr.length == 0) {
        return arr;
    }

    for (int i = 0; i < arr.length - 1; i++) {
        int current = arr[i + 1];
        int preIndex = i;
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

平均时间复杂度: T(n) = O(n²)
最坏时间复杂度: T(n) = O(n²)：输入数组按降序排列（完全逆序）
最好时间复杂度: T(n) = O(n)：输入数组按升序排列（基本有序）
空间复杂度: O(1)
稳定性：稳定

希尔排序

该方法实质上是一种分组插入方法，希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
   

public static int[] shellSort(int[] arr) {
    int len = arr.length;
    int gap = len / 2;
    while (gap > 0) {
        int temp;
        for (int i = gap; i < len; i++) {
            int preIndex = i - gap;
            temp = arr[i];
            // 寻找前面已排序队列中比temp大的，向后移动，这里和插入排序一直，只是间距不一样
            while (preIndex >= 0 && arr[preIndex] > temp) {
                arr[preIndex + gap] = arr[preIndex];
                preIndex -= gap; 
            }
            arr[preIndex + gap] = temp;
        }
        gap /= 2;
    }
    return arr;
}

平均时间复杂度：T(n) = O(n^1.5)

最坏时间复杂度：T(n) = O(nlog²n）

空间复杂度: O(1)

稳定性: 不稳定，由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

堆排序

堆排序（Heapsort） 是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法描述

1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

public static void heapSort(int[] arr) {
    for (int i = (arr.length / 2) - 1; i >= 0; i--) {
        adjust(arr, i, arr.length);
    }

    for (int i = 0; i < arr.length; i++) {
        swap(arr, 0, arr.length - 1 -i);
        adjust(arr, 0, arr.length - 1 - i);
    }
}

private static void adjust(int[] arr, int index, int len) {
    int leftIndex = 2 * index + 1;
    int rightIndex = 2 * index + 2;
    int bigIndex = index;

    if (leftIndex < len && arr[bigIndex] < arr[leftIndex]) {
        bigIndex = leftIndex;
    }

    if (rightIndex < len && arr[bigIndex] < arr[rightIndex]) {
        bigIndex = rightIndex;
    }

    if (bigIndex != index) {
        swap(arr, index, bigIndex);
        adjust(arr, bigIndex, len);
    }
}

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

算法分析
调堆：O(h)
建堆：O(n)
循环调堆：O(nlogn)
总运行时间T(n) = O(nlogn) + O(n) = O(nlogn)。对于堆排序的最好情况与最坏情况的运行时间，因为最坏与最好的输入都只是影响建堆的运行时间O(1)或者O(n)，而在总体时间中占重要比例的是循环调堆的过程，即O(nlogn) + O(1) =O(nlogn) + O(n) = O(nlogn)。因此最好或者最坏情况下，堆排序的运行时间都是O(nlogn)。而且堆排序还是 原地算法（in-place algorithm） 。

平均情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
最佳情况：T(n) = O(nlogn)
空间复杂度：O(1)
稳定性：不稳定

归并排序

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法描述

1. 把长度为n的输入序列分成两个长度为n/2的子序列；
2. 对这两个子序列分别采用归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

public static void mergeSort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        mergeSort(arr, low, mid);
        mergeSort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }
}

private static void merge(int[] arr, int low, int mid, int high) {
    int[] help = new int[high - low + 1];
    int left = low;
    int right = mid + 1;

    int index = 0;
    while (left <= mid && right <= high) {
        if (arr[left] < arr[right]) {
            help[index++] = arr[left++];
        } else {
            help[index++] = arr[right++];
        }
    }

    while (left <= mid) {
        help[index++] = arr[left++];
    }

    while (right <= high) {
        help[index++] = arr[right++];
    }

    for (int i = 0; i < help.length; i++) {
        arr[low + i] = help[i];
    }
}

算法分析
平均情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
最佳情况：T(n) = O(n)
空间复杂度: O(n)，归并排序需要一个与原数组相同长度的数组做辅助来排序
稳定性: 稳定

快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

1. 从数列中挑出一个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int mid = partition(arr, low, high);
        quickSort(arr, low, mid - 1);
        quickSort(arr, mid + 1, high);
    }
}

private static int partition(int[] arr, int low, int high) {
    int key = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= key) {
            high--;
        }
        swap(arr, low, high);
        while (low < high && arr[low] <= key) {
            low++;
        }
        swap(arr, low, high);
    }
    return low;
}

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

算法分析
最佳情况：T(n) = O(nlogn)，快速排序最优的情况就是每一次取到的元素都刚好平分整个数组
最差情况：T(n) = O(n²)，最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
平均情况：T(n) = O(nlogn)
稳定性：不稳定

排序总结

• 稳定的排序：冒泡排序，插入排序，归并排序
  不稳定的排序：选择排序，堆排序，快速排序，希尔排序

• 平均时间复杂度T(n) = O(nlogn)：希尔排序，归并排序，快速排序，堆排序
  平均时间复杂度T(n) = O(n²)：冒泡排序，简单选择排序，插入排序

• 最好时间复杂度T(n) = O(n)：冒泡排序，插入排序
  最好时间复杂度T(n) = O(nlogn)：归并排序，快速排序，堆排序
  最好时间复杂度T(n) = O(n²)：简单选择排序

• 最坏时间复杂度T(n) = O(nlogn)：归并排序，堆排序
  最坏时间复杂度T(n) = O(n²)：冒泡排序，简单选择排序，插入排序，快速排序

• 空间复杂度O(1)：冒泡排序，简单选择排序，插入排序，希尔排序，堆排序
  空间复杂度O(n)：归并排序
  空间复杂度O(nlogn)：快速排序