【数据结构C/C++】十大排序算法的实现思路以及易写易记忆版代码实现

冒泡排序

时间复杂度 O（n2）
空间复杂度 O（1）
冒泡排序的思想是，从第一个开始遍历，然后每次都把比较大的数据
移动到后面去，那么在第一次交换的时候，最大的数据已经到最后去了，
以此类推，第二次冒泡的话，倒数第二个就是倒数第二大的数据。

#include 

void bubbleSort(int arr[], int n)
{
    if (arr == NULL || n < 2)
    {
        return;
    }
    int flag = 0;
    // 这是第几轮
    for (int i = 0; i < n; i++)
    {
        flag = 0;
        // 这一层的for循环的意思就是当前轮需要包含的数据的个数
        // 因为每一次冒泡，都会有一个最大的数据到末尾去
        // 所以需要不断的减少需要参与计算的数据量
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                // 使用异或交换
                arr[j] = arr[j] ^ arr[j + 1];
                arr[j + 1] = arr[j] ^ arr[j + 1];
                arr[j] = arr[j] ^ arr[j + 1];
                flag = 1;
            }
        }
        //如果此时已经没有数据更新，那么说明已经有序，直接跳出循环
        if (flag == 0)
        {
            break;
        }
    }
}

int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组:\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    bubbleSort(arr, n);

    printf("排序后的数组:\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

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
57
58
59

选择排序

时间复杂度 O（n^2）
空间复杂度 O（1）
思路是从第一个开始遍历，然后每次都选择最小的哪一个放到前面去。
分区间： 将数组分为两部分，一部分是已排序的，另一部分是未排序的。初始时，整个数组都被视为未排序。
找最小值： 在未排序的部分中，查找最小的元素。通常，这是通过遍历未排序部分的所有元素并不断更新一个临时最小值和其索引来实现。
交换位置： 一旦找到最小元素，将其与未排序部分的第一个元素交换位置，使其成为已排序部分的一部分。
增加已排序部分的大小： 将已排序部分的大小递增，同时减少未排序部分的大小。
重复： 重复步骤2到步骤4，直到整个数组都被排序。未排序部分会不断减小，而已排序部分会逐渐增加。
完成： 当未排序部分为空时，排序过程完成，整个数组被排序。
上面是我早期写的笔记，比较书面。口语的意思其实就是，在开始排序之前，先记录下一次要插入的最小的数据的位置，一开始其实就是0，然后记录下来这个起始位置p，并且设定这个起始位置的值为暂定的min最小值，然后从起始位置开始遍历整个数组，找到最小的那个数据，并且记录下来这个位置的索引，并且更新我们暂定的min的值为这个遍历到的更小的值。
之后，我们遍历完毕一次数组之后，我们就得到了从起始位置到达数组末尾中的那个最小值的索引和最小值。
此时，我们进行交换，将这个最小值交换到我们一开始设定的其实位置p，当然，我们肯定不能直接就覆盖了这个起始位置的值，还需要将我们一开始设定的起始位置的值覆盖掉这个我们后来找到的最小值的索引，不然这个最小值就会一直参与计算了。

#include 

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = arr[i];  // 初始化最小值为当前元素
        int p = i;  // 用于记录最小值的索引

        // 在未排序部分查找最小值
        for (int j = i + 1; j < n; j++) {
            if (min > arr[j]) {
                min = arr[j];
                p = j;
            }
        }

        // 如果找到更小的值，交换它们
        if (p != i) {
            int temp = arr[p];
            arr[p] = arr[i];
            arr[i] = temp;
        }
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    selectionSort(arr, n);

    printf("排序后的数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

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

插入排序

时间复杂度 O（n2)
空间复杂度 O（1）
插入排序的概念是：每次选取一个索引，从0开始。然后判断当前数据是不是比前面一个小，
如果是，那么就开始交换，并且一直交换，直到比前面的大，或者前面没有数据了为止。
因此插入在高度有序的情况下，时间复杂度O（n），最差O（n2）
插入排序一般性能都比冒泡和选择排序好 因为他会在数据有序的时候直接结束内循环。
这里比较重点的就是，插入排序每次遍历的时候，是向前遍历，也就是每次都要确保当前元素是大于前面元素的，如果不成立，也就是arr[j]>arr[j+1]，那么插入排序就会开始向前交换元素。直到不成立或者遇到索引0.
我甚至认为插入排序最简单，因为他实际有效的代码就两行！！！

#include 

void insertSort(int arr[], int n) {
	//从第一个元素开始遍历，然后内循环比较当前元素的前面一个元素和当前元素的关系
    for (int i = 1; i < n; i++) {
        // 这里的条件判断就是 j 前面还有数据，并且前面的 j 比后面的数据大
        // 那么就需要进行一次交换
        for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
            // 使用异或交换
            arr[j] = arr[j] ^ arr[j + 1];
            arr[j + 1] = arr[j] ^ arr[j + 1];
            arr[j] = arr[j] ^ arr[j + 1];
        }
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    insertSort(arr, n);

    printf("排序后的数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

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

归并排序

数组版本

时间复杂度 O（nlogn）
空间复杂度 O（n）
归并排序的思路：
使用递归的方式不断将数组进行拆分，拆分为左右两个等大小的数组。
由于递归的特性，最后会拆分为长度最小为2的一个小区间，之后我们就对这个小区间进行排序即可。
最后，我们就可以得到多个的有序的小区间。
然后递归返回之后，又会继续对这些小区间合并后的一个区间进行合并，然后不断递归返回，
就可以得到最终有序的一个区间了。
而递归调用的一个重要思路就是，使用一个临时数组，这个临时数组用于存放左右区间里的数据，并且会按照大小进行排序。
思路为，使用p1（左指针），使用p2（右指针）的方式，左指针指向left，右指针指向mid+1，
然后左右指针不断后移，直到越界，左指针边界为left—mid，右指针边界为mid+1—right。
然后将左右指针中指向的更小的数据拷贝到临时数组中，此时临时数组中的元素在区间内有序。
之后将这个区间内有序的数据，覆盖原有的数组即可。
之所以归并排序可以把时间复杂度缩短到nlogn，是因为相对于时间复杂度n2的排序，这些排序浪费了大量的比较功能
而归并排序每次都会比较两个范围的数据，并且将其合并成一个区间内有序的数据，然后再将这个区间去和更大的区间进行
一次排序，那么这样子，他的比较的操作就没有浪费，而是保留了下来。
代码如下：

#include 

// 提前声明merge函数
void merge(int arr[], int left, int middle, int right);
void mergeSort(int arr[], int left, int right);

void mergeSort(int arr[], int left, int right)
{
    if (left == right)
    {
        return;
    }
    //划分中轴
    int mid = ((right - left) >> 1) + left;
    //对左边进行归并
    mergeSort(arr, left, mid);
    //对右边进行归并
    mergeSort(arr, mid + 1, right);
    //排序
    merge(arr, left, mid, right);
}
//对left到right这个区间上的数据进行排序
void merge(int arr[], int left, int mid, int right)
{
    // 创建一个辅助空间 left--right上有多少个数就开多大的空间
    int help[right - left + 1];
    int i = 0;        // 提供给help使用的变量
    int p1 = left;    // 左侧数据的下标
    int p2 = mid + 1; // 指向mid+1位置
    // 判断p1和p2是否越界，如果都不越界
    // 那么谁小谁就拷贝到数组help中去
    while (p1 <= mid && p2 <= right)
    {
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    // 继续判断是否有没有拷贝完毕的数据
    // 可能是左半部分的p1没有拷贝完毕
    while (p1 <= mid)
    {
        help[i++] = arr[p1++];
    }
    // 也可能是右侧的p2没有拷贝完毕
    while (p2 <= right)
    {
        help[i++] = arr[p2++];
    }
    // 将help上面有序的数据拷贝到原数组上去，就得到了区间上有序数据
    for (i = 0; i < (sizeof(help) / sizeof(help[0])); i++)
    {
        arr[left + i] = help[i];
    }
}

int main()
{
    int arr[] = {12, 11, 13,2312,123,556,887, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组:\n");
    for (int i = 0; i < arr_size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    mergeSort(arr, 0, arr_size - 1);

    printf("排序后的数组:\n");
    for (int i = 0; i < arr_size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

链表版本

相对于使用数组，使用链表的归并排序的空间复杂度为O（1）。
时间复杂度不变。
链表方式的归并排序与数组方式的归并排序有一些不同，因为链表不支持随机访问，需要特别考虑如何拆分和合并链表。
大概的实现思路如下：

分割链表： 首先，将原始链表拆分为两个子链表。可以使用快慢指针方法，即使用两个指针，一个慢指针每次前进1步，另一个快指针每次前进2步，找到链表的中点。然后，将链表从中点分为两个子链表。重复这个过程，直到链表不能再分割。

递归排序： 对分割得到的两个子链表递归应用归并排序。这将重复分割和排序的过程，直到每个子链表只包含一个元素或为空。这些子链表是已排序的。

合并有序链表： 合并两个有序链表，这是归并排序的核心操作。创建一个新的链表作为合并结果，然后从两个子链表中逐个选择较小的节点，并将其添加到新链表中，直到两个子链表都为空。这将创建一个有序的合并链表。

返回结果： 返回合并后的有序链表，这就是排序完成的链表。

#include 
#include 

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* merge(struct ListNode* l1, struct ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    struct ListNode dummy;
    struct ListNode* tail = &dummy;
    dummy.next = NULL;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    if (l1) tail->next = l1;
    if (l2) tail->next = l2;

    return dummy.next;
}

struct ListNode* findMiddle(struct ListNode* head) {
    if (!head) return NULL;

    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

struct ListNode* mergeSort(struct ListNode* head) {
    if (!head || !head->next) return head;

    struct ListNode* middle = findMiddle(head);
    struct ListNode* secondHalf = middle->next;
    middle->next = NULL;

    struct ListNode* left = mergeSort(head);
    struct ListNode* right = mergeSort(secondHalf);

    return merge(left, right);
}

void printList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }
    printf("\n");
}

void insert(struct ListNode** head, int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = *head;
    *head = newNode;
}

int main() {
    struct ListNode* head = NULL;
    int n, val;

    printf("输入链表元素的数量: ");
    scanf("%d", &n);

    printf("请开始输入链表元素：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &val);
        insert(&head, val);
    }

    printf("Original list:\n");
    printList(head);

    struct ListNode* sortedList = mergeSort(head);

    printf("Sorted list:\n");
    printList(sortedList);

    return 0;
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

归并排序-内部缓存法

使用这个方法，可以让归并排序的空间复杂度变为O（1），但是归并排序将会失去稳定性。
既然如此，还不如直接用堆，反正也是不稳定，而且空间复杂度也为O（1）。
有兴趣的可以自己搜索一下

快速排序（重点讲解）

时间复杂度O（nlogn）
空间复杂度O（n）
快速排序是我们最常用的排序算法，也是性能比较好的一种时间算法。
因此我会重点讲解快速排序的实现思路。
在上面我们提到了归并排序，其实现的思想是将对整个数组的操作，通过递归的方式，变为对一小块区间的排序操作，也就是说，合理的使用递归等过程，是可以优化性能的。那么快排也可以。
可以思考如下一个场景，假设有一个数组，元素内容是：1，3，5，3，4，6，7，1，2，6。
假设我们有一个需求，是通过给定一个数据，然后要求我们的代码使得数组中的小于等于这个数据的元素出现在这个元素的左边，而如果是大于这个数据的元素，出现在数组的右边。
也就是相当于我们通过给定的这个数，对数组进行了一个划分，对于给出的数target，恒有
数组左侧于target的数据，小于target，数组右侧于target的数据，大于target。
那么很容易通过双指针的方式得到这样子的代码：

 //指定一个数据 然后比这个数据大的数据放在右边，比这个数据小于等于的放在左边。
   void smallLeftBigRight(int arr[],int target){
        int slow = 0;
        int fast = 0;
        while (fast<arr.length){
            if (arr[fast]<=target){
                arr[slow]^=arr[fast];
                arr[fast]^=arr[slow];
                arr[slow]^=arr[fast];
                slow++;  
            }
            fast++;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

输入一个数组之后，我们就可以发现，数组中某个位置左右的数据是小于和大于我们给出的数据的，如下：

可以发现，经过我们简单的这样子的操作，数据好像看起来有了那么一点顺序。
是的，快排就是基于这样子的一个思想：设定一个基准，要求基准值左边的数据小于等于基准值，基准值右边的数据大于基准值。并且通过递归的方式，直到所有的区间符合要求。
那么如果我们要实现上面的说法，应该如何实现呢：
实现思路1：
依旧是上面的数组，我们选定最后的一个数据为基准（设定为target），然后要求小于等于这个数据的出现在这个数据的左边，大于这个数据的出现在这个数据的右边。
然后我们通过遍历的方式，从左到右遍历这个数组，如果遇到的值小于target，就继续后移，因为合理，如果遇到的值大于target，我们就将这个值交换到数组的末尾去，这样子大的值就放到后面了，当然，如果是这种情况，由于我们不确定换过来的数据是否大于target，我们的指针是不能增加的，然后在进行一次上面的比较才确定是否增加。循环往复，直到右边交换的值都已经比当前target大。
那么此时我们就按照上面的代码中得到了这样子一个部分有序的数据了，然后此时我们将大于这个数据的第一个数据与这个最后一个数据进行交换（交换后target的索引为index），那么我们此时就得到了，这个target数据左边的数据都小于这个数据，右边的都大于这个数据。
然后我们继续缩短这个范围，根据这个数据划分出来的左右边界，继续执行这个流程，左边的那一边从最左边的索引开始left，然后右侧范围为index， 而右边也重复这样子的过程，其左边界为index+1，右边界为right。不断执行这样子的递归操作，直到左指针和右指针碰撞，我们就可以返回。
按照这样子的思路，我们可以发现，其时间复杂度最差为O（n2），因为在数据高度有序的情况下，例如：1，2，3，4，5。那么我们的过程其实每次都是这个数据自己和自己交换，因为左边的都是比它小的。大概的一个流程如下：

所以，按照我们上面的意思，快排的时间复杂度在这个基准值非常差劲的时候，时间复杂度
O（n2）。压根就不快，所以我们需要解决基准值很偏的问题。
代码实现如下，我这里设定最左边的数据为中轴。

 /**
     * 下面是对代码的逐步解释：
     * 

     * public static int[] quickSortX(int[] arr, int start, int end)：这是快速排序的入口函数，
     * 它接受一个整数数组 arr 以及排序范围的起始位置 start
     * 和结束位置 end 作为参数，并返回排序后的整数数组。
     * 

     * int pivot = arr[start];：选择数组中的第一个元素作为中轴值（pivot）。
     * 

     * int left = start; 和 int right = end;：定义两个指针，left 从左向右移动，right 从右向左移动，
     * 用于在数组中找到需要交换的元素。
     * 

     * 下面的 while (left < right) 循环是快速排序的核心部分，它在数组中找到需要交换的元素，
     * 以确保中轴值左边的元素都小于等于中轴值，中轴值右边的元素都大于等于中轴值。这个循环包含以下几个部分：
     * 

     * 第一个 while 循环：从左边开始，找到一个大于或等于中轴值的元素。
     * 第二个 while 循环：从右边开始，找到一个小于或等于中轴值的元素。
     * 如果找到的左边元素等于右边元素，则继续将 left 向右移动，以避免出现无限循环。
     * 否则，交换左边元素和右边元素的值，确保左边元素小于中轴值，右边元素大于中轴值。
     * 之后，代码检查是否有需要递归排序的左半部分和右半部分。如果左半部分的起始位置小于左指针的前一个位置，
     * 递归调用 quickSortX 对左半部分进行排序。同样，如果右半部分的结束位置大于右指针的后一个位置，递归调用
     * quickSortX 对右半部分进行排序。
     * 

     * 最后，函数返回排序后的数组 arr。
     *
     * @param arr
     * @param start
     * @param end
     * @return
     */
    int[] quickSortX(int arr[], int start, int end) {
        int pivot = arr[start];
        int left = start;
        int right = end;
        //范围合法性
        while (left < right) {
            //设定pivot中轴值左边的数据要求比pivot小
            while (left < right && arr[left] < pivot) {
                left++;
            }
            //设定pivot中轴值右边的数据要比pivot大
            while (left < right && arr[right] > pivot) {
                right--;
            }
            //循环停止时 存在  arr[right]<=pivot>=arr[left]
            //如果等于 那么继续让left指针后移一位
            if (left < right && arr[left] == arr[right]) {
                left++;
            } else {//否则就是直接交换他们两个的值即可
                //此时存在 arr[left]
                //交换数据
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        if (start < left - 1) {
            arr = quickSortX(arr, start, left - 1);
        }
        if (right + 1 < end) {
            arr = quickSortX(arr, right + 1, end);
        }
        return arr;
    }
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
57
58
59
60
61
62
63
64

这个时候，按照我们上面的思想，我们肯定希望我们的中轴值没有那么偏僻，所以我们考虑使用一个随机的方式，生成我们中轴的位置。那么我们按照master方式，可以得到最快的效率O（nlogn）。
所以我们就有了目前使用的快速排序，思路如下：
实现思路2：

 /**
     * void quickSort(int[] arr)：这是公共的快速排序入口函数。
     * 它接受一个整数数组 arr 并检查是否需要排序。如果数组为空或只包含一个元素，它就不执行排序。否则，它调用
     * quickSortO2 来进行快速排序。
     * 

     * void quickSortO2(int[] arr, int left, int right)：这个函数执行实际的快速排序算法。
     * 它接受数组 arr 以及排序的范围从 left 到
     * right。该函数使用了随机选择中轴值的方法，然后调用 partition 函数来划分数组，并递归地对左右两部分进行排序。
     * 

     * swap 函数用于交换数组中的两个元素。这个函数通过位运算进行交换，是一种非常快速的方法。
     * 

     * int[] partition(int[] arr, int left, int right)：这个函数用于处理 arr[left...right]
     * 上的数据，将数组按照中轴值进行划分。它返回一个包含两个元素的整数数组，
     * 表示等于中轴值的区域的左边界和右边界。这个函数采用双指针法，其中 lessBound
     * 表示小于区的右边界，moreBound 表示大于区的左边界。
     * 

     * 首先，通过将 arr[right] 作为中轴值，初始化 lessBound 和 moreBound。
     * 使用 left 指针从左到右遍历数组元素。
     * 如果当前元素小于中轴值，将其与 lessBound 右边的元素交换，并将 lessBound 和 left 向右移动。
     * 如果当前元素大于中轴值，将其与 moreBound 左边的元素交换，并将 moreBound 向左移动。
     * 如果当前元素等于中轴值，只将 left 指针向右移动。
     * 最后，将 arr[right] 与 moreBound 处的元素交换，将数组划分为小于、等于和大于中轴值的三个部分。
     * 返回 lessBound + 1 和 moreBound，它们分别表示等于区的左边界和右边界。
     * 

     * 这里，对于partition方法，我的实现和思考思路如下：
     * 

     * 初始化 lessBound 为 left - 1，即 lessBound 初始为-1，表示小于区的右边界。
     * 

     * 初始化 moreBound 为 right，即 moreBound 初始为10，表示大于区的左边界。
     * 

     * 使用 left 指针从左到右遍历数组元素。
     * 

     * 当 arr[left]（当前元素）小于 arr[right]（中轴值）时，执行以下操作：
     * 交换 arr[left] 和 arr[lessBound + 1]，然后增加 lessBound 和 left。
     * 这表示我们将小于区的右边界向右扩展一个位置，并将当前元素放入小于区。
     * 当 arr[left] 大于 arr[right] 时，执行以下操作：
     * 交换 arr[left] 和 arr[moreBound - 1]，然后减少 moreBound。
     * 这表示我们将大于区的左边界向左扩展一个位置，并将当前元素放入大于区。
     * 当 arr[left] 等于 arr[right] 时，只将 left 指针向右移动，因为相等的元素将留在等于区。
     * 最终，left 指针遍历整个数组，将数组划分为三个部分：小于区、等于区和大于区。
     * 

     * 为了完成划分，将 arr[right]（中轴值）与 arr[moreBound]（大于区的左边界）进行交换。这将把中轴值放到正确的位置。
     * 

     * 返回一个包含两个元素的数组，[lessBound + 1, moreBound]。这个数组表示等于区的左边界和右边界。
     * 

     * 其中，对于 arr[left] > arr[right] 这种情况，我并没有left++,是因为：
     * 当前元素 arr[left] 大于中轴值 arr[right] 时，我们将它放入大于区，即 arr[moreBound - 1] 处。
     * 这意味着 moreBound 表示大于区的左边界。
     * 

     * 通过减少 moreBound 的值，我们将大于区的左边界向左移动，同时保持 left 指针不变。
     * 这是因为当前元素 arr[left] 已经被放入大于区，而在下一次迭代中，我们需要继续检查新的 arr[left]
     * 是否大于中轴值，以确保大于区包含所有大于中轴值的元素。
     * 

     * 所以，left 指针只在当前元素小于中轴值时执行 ++ 操作，表示将当前元素放入小于区，而在当前元素大于中轴值时，
     * 只需要更新大于区的左边界 moreBound，而不需要改变 left 指针。
     *
     * @param arr
     */
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSortO2(arr, 0, arr.length - 1);
    }

    public static void quickSortO2(int[] arr, int left, int right) {
        if (left < right) {
            swap(arr, left + (int) (Math.random() * (right - left + 1)), right);
            int[] p = partition(arr, left, right);
            quickSortO2(arr, left, p[0] - 1); //< 区域
            quickSortO2(arr, p[1] + 1, right); //> 区域
        }
    }

    //当前方法用于处理arr[left...right]上面的数据
    //默认以arr[right]做划分
    //返回等于区域（左边界、右边界），所以返回一个长度为2的数组res，res[0],res[1]
    public static int[] partition(int[] arr, int left, int right) {
        int lessBound = left - 1;//小于区右边界
        int moreBound = right; //大于区左边界
        while (left < moreBound) {//left表示当前数据的位置 arr[right] -->划分值
            if (arr[left] < arr[right]) { //当前数据小于划分值
                swap(arr, ++lessBound, left++);
            } else if (arr[left] > arr[right]) {
                swap(arr, --moreBound, left);
            } else {
                left++;
            }
        }
        swap(arr, moreBound, right);
        return new int[]{lessBound + 1, moreBound};
    }

    public static void swap(int[] arr, int i, int j) {
        //特别注意 如果i==j，那么会导致数据被抹除
        if (i == j) {
            return;
        }
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
    }
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

对于记忆的话，还是选择可读性比较好的方法1吧，追求性能的时候可以考虑使用方法2。

堆排序（重点理解）

堆排序的时间复杂度是稳定的O（nlogn）
空间复杂度为O（1）
堆排序的思想是基于完全二叉树的。
堆排序会使得数据满足大顶堆或者小顶堆的特性。大顶堆的意思就是非叶子节点的值大于叶子节点。小顶堆则相反。
因此对于一个堆，其插入数据不符合堆的特性的时候，是需要进行堆化的，也就是会将这个数据进行排序，移动到合理的位置，使其满足大顶堆的特性。

堆排序的详细步骤如下：
建立堆：从数组的中间元素开始，从右至左，或者从下至上，对每个元素执行下沉操作（即将元素下沉到适当的位置），以确保树的每个分支满足堆的性质。这将创建一个有效的最大堆或最小堆，取决于排序需求。

排序：堆建立完成后，根节点包含堆中的最大（或最小）元素。将根节点与堆的最后一个元素交换，然后缩小堆的范围，即排除掉最大（或最小）元素。接着，对根节点执行一次下沉操作，以确保新的根节点仍然是堆中的最大（或最小）元素。重复这个步骤，直到堆为空。

重复：重复步骤2，直到整个数组被排序。

大部分讲解堆的博客中都会明确告诉你，堆排序是需要在数组的末尾不断缩短边界的，把堆顶元素和数组末尾元素进行交换，然后在进行一次堆化，不断循环往复，就可以得到一个有序的数组。
这就是堆排序的精髓。
当然当然，堆其实最最最最重要的不是堆排序，而是堆的结构，合理利用堆的结构可以解答非常非常非常多的题目。
比如如下这题：
考研408真题

#include 

// 升序排序堆排序 --- 使用大顶堆
void adjustHeap(int arr[], int i, int length) {
    int temp = arr[i]; // 将当前非叶子结点保存
    for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
        if (k + 1 < length && arr[k] < arr[k + 1]) { // 判断左孩子大还是右孩子大
            k++; // 如果右孩子大就++获得右孩子的索引
        }
        if (arr[k] > temp) { // 判断孩子大还是当前节点大
            arr[i] = arr[k]; // 将更大的向上排
            i = k; // 大的元素就跑到了非叶子结点的索引去，然后让 i 去更小数据的索引
        } else {
            break;
        }
    }
    arr[i] = temp; // 大的数据被移上去了，但是其原有位置的数据还没有被修改
}

// 降序排序堆排序 --- 使用小顶堆
void adjustHeapDesc(int arr[], int i, int length) {
    int temp = arr[i]; // 将当前非叶子结点保存
    for (int k = 2 * i + 1; k < length; k = k * 2 + 1) {
        if (k + 1 < length && arr[k] > arr[k + 1]) { // 判断左孩子大还是右孩子大
            k++; // 如果右孩子小就++获得右孩子的索引
        }
        if (arr[k] < temp) { // 判断孩子小还是当前节点小
            arr[i] = arr[k]; // 将更小的向上排
            i = k; // 小的元素跑到了非叶子结点的索引，然后让 i 去更大数据的索引
        } else {
            break;
        }
    }
    arr[i] = temp; // 小的数据被移上去了，但是其原有位置的数据还没有被修改
}

void heapSort(int arr[], int length) {
    // 构建小顶堆
    for (int i = length / 2 - 1; i >= 0; i--) {
        adjustHeapDesc(arr, i, length);
    }
    
    printf("初始构造小顶堆: ");
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    // 将堆顶元素与末尾元素进行交换，将最小数据沉到末尾
    // 重新调整结构，使其继续满足小顶堆性质
    for (int j = length - 1; j > 0; j--) {
        int temp = arr[0];
        arr[0] = arr[j];
        arr[j] = temp;

        // 重新调整堆，排除已排序部分，使其继续满足小顶堆性质
        adjustHeapDesc(arr, 0, j);
    }
    
    printf("小顶堆排序后的数组（降序排列）: ");
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 10, 3, 5, 1};
    int length = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    heapSort(arr, length);

    return 0;
}


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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

计数排序

时间复杂度O（n），
空间复杂度O（n）。
这是一种典型的用空间换时间的排序算法，但是在数据差值非常大的情况下非常不合理。
并且这种排序由于不是基于比较的，所以他需要对代码进行定制。
比如你的数据是一个结构体比较，不是整型类型比较，那么很明显代码你就得修改了。
计数排序（Counting Sort）是一种非比较性的整数排序算法，其核心思想是通过统计每个元素在待排序数组中出现的次数，然后根据这些统计信息，构建一个有序的结果数组。

计数排序的基本思想可以概括为以下几个步骤：

确定范围：找到待排序数组中的最大值（max）和最小值（min），以便确定计数数组的大小范围。通常，范围大小为max - min + 1。

创建计数数组：创建一个大小为max - min + 1的计数数组，用于存储每个元素出现的次数。初始时，计数数组中的所有元素都初始化为0。

计数：遍历待排序数组，对于每个元素，将计数数组中对应元素的计数值加一。这样，计数数组的值表示每个元素在待排序数组中出现的次数。

累加计数：对计数数组进行累加操作。将每个计数值更新为前面所有计数值的累加和。这一步是为了确定每个元素在排序后的结果数组中的位置。

构建结果数组：创建一个与待排序数组相同大小的结果数组。然后，从待排序数组末尾开始遍历，对于每个元素，根据计数数组中的值找到其在结果数组中的位置，将其放入结果数组中，并将对应计数值减一以表示一个相同元素已经放入结果数组。

复制结果：将排序后的结果数组复制回待排序数组，完成排序过程。

计数排序的核心思想是依靠计数数组来统计元素的出现次数，并利用这些统计信息构建有序结果。它不需要进行元素的比较操作，因此具有线性时间复杂度，通常用于整数排序，尤其适用于范围较小的整数。然而，计数排序的主要限制是需要额外的内存来存储计数数组，因此在元素范围较大的情况下可能会导致内存浪费。

#include 

void countingSort(int array[], int size) {
    // 找到数组中的最大值以确定计数数组的大小
    int max = array[0];
    for (int i = 1; i < size; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }

    // 创建计数数组并初始化为0
    int countArray[max + 1];
    for (int i = 0; i <= max; i++) {
        countArray[i] = 0;
    }

    // 计算每个元素出现的次数
    for (int i = 0; i < size; i++) {
        countArray[array[i]]++;
    }

    // 根据计数数组构建排序后的结果数组
    int resultArray[size];
    int resultIndex = 0;
    for (int i = 0; i <= max; i++) {
        while (countArray[i] > 0) {
            resultArray[resultIndex] = i;
            resultIndex++;
            countArray[i]--;
        }
    }

    // 将排序后的结果复制回原数组
    for (int i = 0; i < size; i++) {
        array[i] = resultArray[i];
    }
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int size = sizeof(arr) / sizeof(arr[0]);

    countingSort(arr, size);

    printf("排序后的数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

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

基数排序

最好、平均和最坏情况下的时间复杂度都为 O(d * (n + k))，其中：
d 是最大元素的位数（或者说基数）。
n 是元素的数量。
k 是基数，通常是10（对于十进制整数）或256（对于字节）。
在最理想情况下，基数排序的时间复杂度主要受限于最大元素的位数，通常情况下是线性的。

基数排序的空间复杂度取决于存储桶和辅助数组的空间开销，通常是 O(n + k)。
n 是元素的数量。
k 是基数，通常是10（对于十进制整数）或256（对于字节）。
基数排序（Radix Sort）是一种非比较性的整数排序算法，其核心思想是根据数字的位数（位上的值）来对整数进行排序。基数排序通常从最低有效位（最右边的位）开始，逐渐向高位排序，直到最高有效位（最左边的位）。

基数排序的主要思想可以分为以下几个步骤：

准备桶：准备一个辅助数组（或桶），用于存储整数元素。通常，这个辅助数组是一个包含10个桶的数组（0到9），每个桶对应一个数字的可能取值（0到9）。

从最低有效位到最高有效位：基数排序通常从整数的最低有效位（个位）开始，依次向高位排序。对于每个位上的值，进行一轮排序。

分配元素：在每一轮排序中，遍历待排序数组，根据元素的当前位上的值将元素分配到相应的桶中。例如，如果当前轮是按个位排序，那么元素根据个位上的值放入对应的桶。

收集元素：在分配元素到桶之后，将桶中的元素按照顺序（从0到9）收集回原始数组。

重复排序：继续上述步骤，按照下一位的值进行排序，直到完成排序。通常，需要进行足够的排序轮次以确保所有位都被考虑到。

完成排序：完成所有的排序轮次后，原始数组中的元素已经按照其位上的值从小到大排列，排序完成。

基数排序的关键思想是分配和收集过程，通过多轮的分配和收集，逐渐完成整数的排序。每一轮排序都是稳定的，因为它不会改变相同位上元素的相对顺序。基数排序适用于整数排序，尤其适用于整数的位数相对较少的情况。

优点：

基数排序是稳定的排序算法，不会改变相等元素的相对顺序。
适用于整数排序，特别是位数相对较少的整数。
不需要比较操作，因此性能通常比比较排序算法更高。
缺点：

需要额外的存储空间来存储桶，因此内存消耗较大。
适用范围有限，不适合处理浮点数和字符串等非整数数据。
对于位数较多的整数，排序轮次可能较多，导致性能下降。

#include 

// 获取数组中的最大值
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// 基数排序的辅助函数，对数组按照指定位数进行计数排序
void countSort(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0}; // 0到9，用于统计每个数字出现的次数

    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 基数排序
void radixSort(int arr[], int n) {
    int max = getMax(arr, n);

    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(arr, n, exp);
    }
}

int main() {
    int n;
    printf("请输入数组的大小: ");
    scanf("%d", &n);
    int arr[n];

    printf("请输入 %d 个整数:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    printf("原始数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    radixSort(arr, n);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

如下是我Java使用基数排序的时候的代码，看起来会更好理解。

public static void radixSort(int[] arr) {
        // 找到数组中的最大值，以确定最大元素的位数
        int max = arr[0];
        int maxLength = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        maxLength = (max + "").length(); // 最大元素的位数

        // 创建桶数组，用于存储排序中间结果
        int[][] bucket = new int[10][arr.length]; // 每个桶最多能容纳数组大小个元素
        int[] bucketCount = new int[10]; // 记录每个桶中的元素个数
        int digitOfElement = 0;

        // 进行多轮排序，每轮排序根据元素的位数
        for (int i = 0, n = 1; i < maxLength; n *= 10, i++) {
            // 将元素按照当前位数的值放入对应桶中
            for (int j = 0; j < arr.length; j++) {
                digitOfElement = arr[j] / n % 10;
                bucket[digitOfElement][bucketCount[digitOfElement]] = arr[j];
                bucketCount[digitOfElement]++;
            }

            int index = 0;
            // 依次从桶中取出元素，按照顺序重组数组
            for (int k = 0; k < bucketCount.length; k++) {
                if (bucketCount[k] != 0) {
                    for (int l = 0; l < bucketCount[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                bucketCount[k] = 0;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

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

桶排序

桶排序（Bucket Sort）是一种非比较性的排序算法，它的核心思想是将待排序的元素分配到不同的桶（容器）中，然后对每个桶中的元素进行排序，最后按照顺序合并各个桶的内容，从而得到有序的结果。

桶排序的步骤如下：

确定桶的数量：首先，确定使用多少个桶，通常桶的数量是根据待排序数据的范围来确定的。如果数据范围较大，可以使用更多的桶。

分配元素：遍历待排序的元素，根据每个元素的值将其分配到对应的桶中。例如，元素值范围在0到99之间，可以将0到9分配到第一个桶，10到19分配到第二个桶，以此类推。

对每个桶进行排序：对每个非空的桶进行排序，可以使用任何合适的排序算法，如插入排序或快速排序。

合并桶：按照桶的顺序将每个桶中的元素合并，这就得到了有序的结果。

桶排序适用于特定的数据分布情况，例如，当待排序数据近似均匀分布在一定范围内时，桶排序表现良好。它是一种线性时间复杂度的排序算法，具体的性能取决于桶的数量和每个桶中元素的排序算法。桶排序通常用于外部排序（外部存储器排序），例如对大量磁盘数据进行排序。

#include 

// 定义桶的数量（这里使用固定数量的桶，也可以根据实际情况动态分配）
#define BUCKET_COUNT 10

// 桶排序函数
void bucketSort(int arr[], int n) {
    // 创建桶，每个桶是一个数组
    int buckets[BUCKET_COUNT][n];
    // 每个桶的元素数量初始化为0
    int bucketSize[BUCKET_COUNT] = {0};
    
    // 找到最大值和最小值以确定数据范围
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }

    // 计算桶的范围和尺寸
    double range = (double)(max - min + 1) / BUCKET_COUNT;
    
    // 将元素放入桶中
    for (int i = 0; i < n; i++) {
        int bucketIndex = (int)((arr[i] - min) / range);
        buckets[bucketIndex][bucketSize[bucketIndex]++] = arr[i];
    }

    // 对每个桶中的元素进行排序（这里使用插入排序）
    for (int i = 0; i < BUCKET_COUNT; i++) {
        for (int j = 1; j < bucketSize[i]; j++) {
            int key = buckets[i][j];
            int k = j - 1;
            while (k >= 0 && buckets[i][k] > key) {
                buckets[i][k + 1] = buckets[i][k];
                k--;
            }
            buckets[i][k + 1] = key;
        }
    }

    // 将排序后的元素从桶中提取到原数组
    int index = 0;
    for (int i = 0; i < BUCKET_COUNT; i++) {
        for (int j = 0; j < bucketSize[i]; j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

int main() {
    int n;
    printf("请输入数组的大小: ");
    scanf("%d", &n);
    int arr[n];

    printf("请输入 %d 个整数:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    printf("原始数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    bucketSort(arr, n);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

希尔排序

希尔排序（Shell Sort）是一种排序算法，它是插入排序的改进版本，旨在克服插入排序在大规模数据集上性能较差的问题。希尔排序是由计算机科学家Donald Shell于1959年提出的，它基于以下思想：

希尔排序的核心思想：将数组划分成若干个小的子数组，然后对这些子数组进行插入排序。这些子数组的长度逐渐缩小，最终变成1，也就是对整个数组进行一次插入排序。通过这种分阶段的排序方式，希尔排序能够在初始阶段快速减小乱序数据的规模，使得后续插入排序的工作更加高效。

希尔排序的基本步骤如下：

选择一个增量序列（通常是一系列递减的整数），最开始的增量通常是数组长度的一半。

使用选定的增量，将数组分割成多个子数组，每个子数组包含元素的索引相差增量。

对每个子数组执行插入排序，即将子数组中的元素按照插入排序的方式排序。

逐渐减小增量，重复步骤2和步骤3，直到增量减小至1。

最后一次排序时，增量为1，实际上就是对整个数组进行一次插入排序，这时的数组已经接近有序。

希尔排序的性能优点在于它具有更好的性能预测，特别是对于中等大小的数据集。它可以在较短的时间内完成大部分排序工作，然后对于仅需少量交换的有序数据集，插入排序非常高效。然而，希尔排序的性能高度依赖于所选的增量序列，不同的增量序列可能导致不同的性能表现。

#include 

void shellSort(int arr[], int n) {
    int i, j, increment;
    
    // 初始增量为数组长度的一半
    increment = n / 2;
    
    // 逐渐缩小增量，直到增量为1
    while (increment > 0) {
        for (i = increment; i < n; i++) {
            int temp = arr[i];
            // 对间隔increment的元素进行插入排序
            for (j = i; j >= increment && arr[j - increment] > temp; j -= increment) {
                arr[j] = arr[j - increment];
            }
            arr[j] = temp;
        }
        // 缩小增量
        increment = (increment + 1) / 2;
    }
}

int main() {
    int n;
    printf("请输入数组的大小: ");
    scanf("%d", &n);
    int arr[n];

    printf("请输入 %d 个整数:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    printf("原始数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    shellSort(arr, n);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

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

总结

不具备稳定性的排序：
选择、快速、堆排序，也就是选快堆。
具备稳定性的排序：
冒泡、插入、归并、一切桶排序思想下的排序。
目前没有找到时间复杂度为O（nlogn），额外空间复杂度为O（1）的排序算法。

基于上面的表，我们可以知道，在具体场景中，我们需要选择性的选择排序算法，大部分时候我们会选择使用快排，因为他确实大部分时候最快。但是如果考虑稳定性，我们就会使用归并。而如果没有额外空间可以给你使用，那么就考虑堆排序。

408考研各数据结构C/C++代码（Continually updating）

408考研各数据结构C/C++代码（Continually updating）
这个模块是我应一些朋友的需求，希望我能开一个专栏，专门提供考研408中各种常用的数据结构的代码，并且希望我附上比较完整的注释以及提供用户输入功能，ok，fine，这个专栏会一直更新，直到我认为没有新的数据结构可以讲解了。
目前我比较熟悉的数据结构如下：
数组、链表、队列、栈、树、B/B+树、红黑树、Hash、图。
所以我会先有空更新出如下几个数据结构的代码，欢迎关注。 当然，在我前两年的博客中，对于链表、哈夫曼树等常用数据结构，我都提供了比较完整的详细的实现以及思路讲解，有兴趣可以去考古。