数据结构分类

数据结构 - 排序算法对比

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	$O (n^{2})$	$O (n)$	$O (n^{2})$	$O (1)$	稳定
选择排序	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	不稳定
插入排序	$O (n^{2})$	$O (n)$	$O (n^{2})$	$O (1)$	稳定
希尔排序	$O (n lo g n) \sim O (n^{2})$	$O (n^{1.3})$	$O (n^{2})$	$O (1)$	不稳定
堆排序	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	不稳定
归并排序	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	稳定
快速排序	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	$O (lo g n) \sim O (n)$	不稳定

zedo2022年8月13日大约 2 分钟

数据结构 - 快排和归并(非递归)

快速排序

non-recursive，iterative

归并排序

/**
 * 归并排序，非递归版本
 *
 * 两两归并、四四归并、八八归并...
 *
 * 注意元素个数不是 2^n 的情况，右区间可能不存在，例如 9 个元素时第一次归并，10个元素时第二次归并
 * @param arr
 * @param n
 */
void merge_sort_non_r(int *arr, int n) {
    int tmp[n]; // 辅助数组
    int gap = 1; // 每组归并数据的个数
    while (gap < n) {
        for (int i = 0; i < n; i += 2 * gap) {
            // 分成需要归并的两组：[i, i+gap-1] [i+gap, i+2*gap-1]
            // 下面的代码是复制前面的。
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;

            // 修正，归并过程中右半区间不存在（begin2 越界）
            if (begin2 >= n) {
                break;
            }
            // 归并过程中，右半区间算多了（end2 越界）
            if (end2 >= n) {
                end2 = n - 1;
            }

            int index = i;
            while (begin1 <= end1 && begin2 <= end2) {
                if (arr[begin1] < arr[begin2]) {
                    tmp[index++] = arr[begin1++];
                } else {
                    tmp[index++] = arr[begin2++];
                }
            }
            // 此时一定有 1 个数组已经走“到尾”，把剩下的元素放进 tmp
            while (begin1 <= end1) {
                tmp[index++] = arr[begin1++];
            }
            while (begin2 <= end2) {
                tmp[index++] = arr[begin2++];
            }

            // 把归并部分的数据拷贝回 arr，个数不足以归并的就不管
            // for (int j = 0; j < n; j++) {
            for (int j = 0; j <= end2; j++) {
                arr[j] = tmp[j];
            }
        }

        gap *= 2;
    }
}

zedo2022年8月13日大约 1 分钟

数据结构 - 归并排序

二路归并排序

基本思想：

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

zedo2022年8月13日大约 4 分钟

数据结构 - 其他排序算法

基数排序

桶排序

这里不做介绍，可参看 []。

计数排序

zedo2022年8月13日小于 1 分钟

数据结构 - 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

zedo2022年8月12日大约 25 分钟

数据结构 - 插入排序

直接插入排序

基本思想

直接插入排序 (Straight Insertion Sort) 的基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

zedo2022年8月12日大约 11 分钟

数据结构 - 选择排序

选择排序的基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

直接选择排序

zedo2022年8月12日大约 15 分钟

栈和队列习题

用队列实现栈

225. 用队列实现栈

zedo2022年8月11日大约 3 分钟

数据结构 - 二叉树

树的概念和结构

队列

数据结构

#include <stdio.h>  
#include <stdlib.h>  
#include <stdbool.h>  
#include <assert.h>  

typedef int QDataType;

// 由于队列是 FIFO(先进先出)，采用数组会移动数据，故采用单链表(带头结点)
typedef struct QueueNode {
    QDataType data;
    struct QueueNode *next;
} QueueNode;

// 队列需要控制队头和队尾两个指针，单独用一个结构体存放
typedef struct Queue {
    QueueNode *head; // 队头
    QueueNode *tail; // 队尾
} Queue;

zedo2022年8月10日大约 2 分钟

数据结构 - 栈

栈