C语言

1.常见使用

int i; // 整数类型变量，通常为32位（4字节）
short s; // 短整数类型变量，通常为16位（2字节）
long l; // 长整数类型变量，通常为32位或64位（4或8字节）
short int i1; // 等同于 short s; ，为16位（2字节）
long int i2; // 等同于 long l; ，为32位或64位（4或8字节）
unsigned int i3; // 无符号整数类型变量，通常为32位（4字节）
signed int i4; // 有符号整数类型变量，通常为32位（4字节）
unsigned u; // 无符号整数类型变量，大小取决于系统（一般为4字节）
signed s1; // 有符号整数类型变量，大小取决于系统（一般为4字节）
unsigned short us; // 无符号短整数类型变量，通常为16位（2字节）
总结：
int、unsigned int、signed int 通常为4字节；
short、unsigned short 通常为2字节；
long、long int 一般为4或8字节，取决于编译环境；
字节大小可能因编译环境、操作系统和编译器的不同而有所变化。

c++
#include<stdio.h>

// 定义链表
struct ListNode{
    int name;
    char b;
    char c[10];
    struct ListNode* next;
};

int main(){
    int a;
    char b;
    char str[10] = "zzwxxy";
    char str2[10];

    printf("please input string\n");
    gets(str2);
    printf("input string is:\n%s", str2);
}

/*
 * 定义字符串方式
char string[] = "zhang";
char string[] = {'z','h','a','n','g'};
char str[] = {“zhang”};
*/

/*
scanf和gets的区别：
使用方法：scanf("%s", str2);  gets(str2);
scanf ：当遇到回车，空格和tab键会自动在字符串后面添加’\0’，但是回车，空格和tab键仍会留在输入的缓冲区中。
gets：可接受回车键之前输入的所有字符，并用’\0’替代 ‘\n’.回车键不会留在输入缓冲区中

printf()和puts()的区别: 
printf("input string is:\n%s", str2);  和  puts(str2);
*/

2.链表定义及操作

c++
#include <stdio.h>
#include <stdlib.h>
struct  Node
{
   int data;
   struct Node* next;
};
struct Node* head;

// 在链表头节点插入一个值为x的节点
void Insert(int x){
   struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
   temp->data = x;
   temp->next = head;
   // if(head != NULL)temp->next = head;
   head = temp;
}

// 迭代法实现反转列表
struct Node* Reverse1(struct Node* head){
   struct Node *Current,*Prev,*next;
   Current = head;
   Prev = NULL;
   while(Current != NULL){
      next = Current->next;
      Current->next = Prev;
      Prev = Current;
      Current = next;
   }
   head = Prev;
   return head;
}

// 递归法实现反转列表
void Reverse2(struct Node* p){
   if(p->next ==NULL){
      head = p;
      return;
   }
   Reverse2(p->next);
   struct Node* q = p->next;
   q->next = p;
   p->next = NULL;
}

// 链表内指定区间反转  调试好了
struct Node* reverseBetween(struct Node* head, int m, int n ) {
    // write code here
    if(head == NULL)return head;
    if(head->next == NULL)return head;
    if(m == n)return head;
    struct Node *Current,*Prev,*next,*start,*start_last;
    int i;
    Current = head;
    Prev = NULL;
    next = NULL;
    // 先找到开始位置
    for (i=1; i<m; i++) {
        next = Current->next;
        // Current->next = Prev;
        Prev = Current;
        Current = next;
    }
    // 标记
    start_last = Prev;
    start = Current;
    // 反转
    for (i=0; i<(n-m+1); i++) {
        next = Current->next;
        Current->next = Prev;
        Prev = Current;
        Current = next;
    }
    // 头尾节点重指向
    if(start != head){
        start->next = next;
        start_last->next = Prev;//start!=head的情况下，需要保留start上一个指针
    }
    else {
        start->next = next;
        head = Prev;//start==head的情况下，直接将head指向待反转的最后一个
    }
    return head;
}

//打印链表的所有值
void Print(){
   struct Node* temp = head;
   printf("List is:");
   while(temp){
      printf("%d",temp->data);
      temp = temp->next;
   }
   printf("\n");
}

void Print2(struct Node*p){
   if(p ==NULL){
      printf("\n");
      return;
   }
   // 正序打印
   // printf("%d",p->data);
   // Print2(p->next);

   // 反转打印
   printf("%d",p->data);
   Print2(p->next);
}

int main(){
   head = NULL;
   int n,x,i;
   printf("Please input the number of node:\n");
   scanf("%d",&n);
   for(i = 0;i<n;i++){
      printf("Please input the value of Node:\n");
      scanf("%d",&x);
      Insert(x);
      Print();
   }
   head = Reverse1(head);
   printf("Reverse linked list is:\n");
   Print();

   Reverse2(head);
   printf("Reverse linked list is:\n");
   Print();
   
   // head = reverseBetween(head,2,4);
   // Print();

   // printf("Print2 linked list is:\n");
   // Print2(head);

   // char name[100];
   // printf("What is your name?\n");
   // scanf("%s",name);
   // printf("Hello,%s,nice to meet you!\n",name);
}

3.各种排序算法C语言

c++
#include <stdio.h>

// 1.插入排序，时间复杂度O(n2)，空间复杂度O(1)
void InsertSort(int a[], int n)
{
    for (int i = 1; i < n; i++)
    {
        // 若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
        if (a[i] < a[i - 1])
        {
            int j = i - 1;
            // 复制为哨兵，即存储待排序元素
            int x = a[i];
            // 先后移一个元素
            a[i] = a[i - 1];
            // 查找在有序表的插入位置
            while (x < a[j])
            {
                a[j + 1] = a[j];
                // 元素后移
                j--;
            }
            // 插入到正确位置
            a[j + 1] = x;
        }
    }
}

// 2.希尔排序,时间复杂度O(N^1.5),空间复杂度O(1)
void ShellInsertSort(int a[], int n, int dk)
{
    for (int i = dk; i < n; ++i)
    {
        if (a[i] < a[i - dk])
        { // 若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
            int j = i - dk;
            int x = a[i];     // 复制为哨兵，即存储待排序元素
            a[i] = a[i - dk]; // 首先后移一个元素
            while (j >= 0 && x < a[j])
            { // 查找在有序表的插入位置
                a[j + dk] = a[j];
                j -= dk; // 元素后移
            }
            a[j + dk] = x; // 插入到正确位置
        }
    }
}
void ShellSort(int a[], int n)
{

    int dk = n / 2;
    while (dk >= 1)
    {
        ShellInsertSort(a, n, dk);
        dk = dk / 2;
    }
}

// 选择排序,时间复杂度：O(N^2), 空间复杂度：O(1)
int SelectMinKey(int a[], int n, int i)
{
    int k = i;
    for (int j = i + 1; j < n; ++j)
    {
        if (a[k] > a[j])
            k = j;
    }
    return k;
}
void SelectSort(int a[], int n)
{
    int key, tmp;
    for (int i = 0; i < n - 1; ++i)
    {
        key = SelectMinKey(a, n, i); // 选择最小的元素
        if (key != i)
        {
            tmp = a[i];
            a[i] = a[key];
            a[key] = tmp; // 最小元素与第i位置元素互换
        }
    }
}

// 堆排序,时间复杂度：O(N*logN),空间复杂度：O(1)
void HeapAdjust(int H[], int s, int length)
{
    int tmp = H[s];
    int child = 2 * s + 1; // 左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    while (child < length)
    {
        if (child + 1 < length && H[child] < H[child + 1])
        { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
            ++child;
        }
        if (H[s] < H[child])
        {                    // 如果较大的子结点大于父结点
            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
            s = child;       // 重新设置s ,即待调整的下一个结点的位置
            child = 2 * s + 1;
        }
        else
        { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
            break;
        }
        H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
    }
}

/**
 * 初始堆进行调整
 * 将H[0..length-1]建成堆
 * 调整完之后第一个元素是序列的最小的元素
 */
void BuildingHeap(int H[], int length)
{
    // 最后一个有孩子的节点的位置 i=  (length -1) / 2
    for (int i = (length - 1) / 2; i >= 0; --i)
        HeapAdjust(H, i, length);
}
/**
 * 堆排序算法
 */
void HeapSort(int H[], int length)
{
    // 初始堆
    BuildingHeap(H, length);
    // 从最后一个元素开始对序列进行调整
    for (int i = length - 1; i > 0; --i)
    {
        // 交换堆顶元素H[0]和堆中最后一个元素
        int temp = H[i];
        H[i] = H[0];
        H[0] = temp;
        // 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
        HeapAdjust(H, 0, i);
    }
}

// 冒泡排序,时间复杂度：O(N^2),空间复杂度：O(1)
void BubbleSort(int r[], int n)
{
    int low = 0;
    int high = n - 1; // 设置变量的初始值
    int tmp, j;
    while (low < high)
    {
        for (j = low; j < high; ++j) // 正向冒泡,找到最大者
            if (r[j] > r[j + 1])
            {
                tmp = r[j];
                r[j] = r[j + 1];
                r[j + 1] = tmp;
            }
        --high;                      // 修改high值, 前移一位
        for (j = high; j > low; --j) // 反向冒泡,找到最小者
            if (r[j] < r[j - 1])
            {
                tmp = r[j];
                r[j] = r[j - 1];
                r[j - 1] = tmp;
            }
        ++low; // 修改low值,后移一位
    }
}

// 快速排序递归实现,时间复杂度：O(N*logN), 空间复杂度：O(logN)
int QuickSort(int *a, int low, int high)
{
    int i = low;    // 第一位
    int j = high;   // 最后一位
    int key = a[i]; // 将第一个数作为基准值-- 先找到一个基准值

    while (i < j)
    {
        while (i < j && a[j] >= key)
        {
            j--;
        }
        a[i] = a[j];

        while (i < j && a[i] <= key)
        {
            i++;
        }
        a[j] = a[i];
    }
    a[i] = key;
    if (i - 1 > low)
    {
        QuickSort(a, low, i - 1);
    }

    if (i + 1 < high)
    {
        QuickSort(a, i + 1, high);
    }

    return 0;
}

// 归并排序迭代实现,时间复杂度：O(N*logN), 空间复杂度：O(N)
void merge(int arr[], int start, int mid, int end, int len)
{
    int result[len];
    int k = 0;
    int i = start;
    int j = mid + 1;
    while (i <= mid && j <= end)
    {
        if (arr[i] < arr[j])
        {
            result[k++] = arr[i++];
        }
        else
        {
            result[k++] = arr[j++];
        }
    }
    if (i == mid + 1)
    {
        while (j <= end)
            result[k++] = arr[j++];
    }
    if (j == end + 1)
    {
        while (i <= mid)
            result[k++] = arr[i++];
    }
    for (j = 0, i = start; j < k; i++, j++)
    {
        arr[i] = result[j];
    }
}

void MergeSort(int arr[], int start, int end, int len)
{
    if (start >= end)
        return;
    int mid = (start + end) / 2;
    MergeSort(arr, start, mid, len);
    MergeSort(arr, mid + 1, end, len);
    merge(arr, start, mid, end, len);
}

int main()
{
    int i;
    int array[] = {9, 5, 6, 1, 4, 7, 3, 8, 2};
    int array2[9];
    // InsertSort(array, sizeof(array)/sizeof(array[0]));
    // ShellSort(array, sizeof(array)/sizeof(array[0]));
    // SelectSort(array, sizeof(array)/sizeof(array[0]));
    // HeapSort(array, sizeof(array)/sizeof(array[0]));
    // BubbleSort(array, sizeof(array)/sizeof(array[0]));
    // QuickSort(array, 0, 9-1);
    int len = sizeof(array) / sizeof(array[0]);
    MergeSort(array, 0, 9 - 1, len);

    printf("sort result is:");
    for (i = 0; i < 9; i++)
    {
        printf("%d", array[i]);
    }
    return 0;
}

4.二叉搜索树

c++
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct BstNode
{
   int data;
   struct BstNode *left;
   struct BstNode *right;
};

struct BstNode *GetNewNode(int data)
{
   struct BstNode *temp = (struct BstNode *)malloc(sizeof(struct BstNode));
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}

// 在二叉搜索树中插入一个节点
struct BstNode *Insert(struct BstNode *root, int data)
{
   if (root == NULL)
   {
      root = GetNewNode(data);
   }
   else if (data <= root->data)
   {
      root->left = Insert(root->left, data);
   }
   else
   {
      root->right = Insert(root->right, data);
   }
   return root;
}

// 在二叉搜索树中搜索一个节点
bool Search(struct BstNode *root, int data)
{
   if (root == NULL)
      return false;
   else if (root->data == data)
      return true;
   else if (data <= root->data)
      return Search(root->left, data);
   else
      return Search(root->right, data);
}

// 二叉搜索树的最小值
int FindMin(struct BstNode *root)
{
   struct BstNode *temp = root;
   if (temp == NULL)
   {
      printf("root is empty\n");
      return -1;
   }
   else
   {
      while (temp->left != NULL)
      {
         temp = temp->left;
      }
      return temp->data;
   }
}

// 二叉搜索树的最大值
int FindMax(struct BstNode *root)
{
   struct BstNode *temp = root;
   if (temp == NULL)
   {
      printf("root is empty\n");
      return -1;
   }
   else
   {
      while (temp->right != NULL)
      {
         temp = temp->right;
      }
      return temp->data;
   }
}
// 二叉搜索树的前序遍历
void Preorder(struct BstNode *root)
{
   if (root == NULL)
      return;
   printf("%d,", root->data);
   Preorder(root->left);
   Preorder(root->right);
}
// 二叉搜索树的中序遍历
void Inorder(struct BstNode *root)
{
   if (root == NULL)
      return;
   Inorder(root->left);
   printf("%d,", root->data);
   Inorder(root->right);
}
// 二叉搜索树的后序遍历
void Poseorder(struct BstNode *root)
{
   if (root == NULL)
      return;
   Poseorder(root->left);
   Poseorder(root->right);
   printf("%d,", root->data);
}

// 判断是否是二叉搜索树
bool IsSubtreeLesser(struct BstNode *root, int data)
{
   if (root == NULL)
      return true;
   if (root->data <= data && IsSubtreeLesser(root->left, data) && IsSubtreeLesser(root->right, data))
      return true;
   else
      return false;
}
bool IsSubtreeGreater(struct BstNode *root, int data)
{
   if (root == NULL)
      return true;
   if (root->data >= data && IsSubtreeGreater(root->left, data) && IsSubtreeGreater(root->right, data))
      return true;
   else
      return false;
}
bool IsBinarySearchTree(struct BstNode *root)
{
   if (root == NULL)
      return true;
   if (IsSubtreeLesser(root->left, root->data) && IsSubtreeGreater(root->right, root->data) && IsBinarySearchTree(root->left) && IsBinarySearchTree(root->right))
      return true;
   else
      return false;
}
// 二叉搜索树的高度
int FindHeight(struct BstNode *root)
{
   int LeftHeight = 0;
   int RightHeight = 0;
   if (root == NULL)
   {
      return -1;
   }
   LeftHeight = FindHeight(root->left);
   RightHeight = FindHeight(root->right);
   if (LeftHeight >= RightHeight)
      return LeftHeight + 1;
   else
      return RightHeight + 1;
}

int main()
{
   struct BstNode *root = NULL;
   printf("input start!\n");
   root = Insert(root, 10);
   root = Insert(root, 8);
   root = Insert(root, 7);
   root = Insert(root, 10);
   root = Insert(root, 35);
   root = Insert(root, 50);
   printf("input yes!\n");
   printf("%d", FindHeight(root));
   // Inorder(root);

   // if(IsBinarySearchTree(root) == true)printf("This is IsBinarySearchTree");
   // else printf("This is not IsBinarySearchTree");
   // if(Search(root,30) == true)printf("Found!\n");
   // else printf("Not Found!\n");

   // printf("%d\n",FindMax(root));
   // printf("%d",FindMin(root));
}

C++语言

1.常见操作

c++
#include<iostream>
#include <cstring> 
#include <string> 
using namespace std;  // 为了使用cin和cout

// 定义链表
struct ListNode
{
    int a;
    string name;
    char c;
    ListNode* next;
};

ListNode *head;

int main(){
    int a;
    char b;
    char c[8];
    string d;
    cout<<"please input string"<<endl;
    getline(cin, d);
    cout<<d<<endl;
    return 0;
}

/*
#include <cstring> 的作用：
可以使用string定义字符串
可以使用strlen获得字符串(字符串需要使用char s[10])定义的长度
int strcmp(const char *s1, const char *s2);当s1<s2时，返回为负数；当s1=s2时，返回值= 0；当s1>s2时，返回正数。
*/

/*
cin和getline的区别：
cin>>str不会读取空格； getline(cin, str); 可以读取空格，但是需要#include <string> 并且str需要通过 string定义；
*/

2.各种排序算法C++

/*
 *冒泡排序,时间复杂度O(N^2)；空间复杂度：O(1)；稳定排序
 *思路：第一趟：两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置；一共进行n-1趟这样的交换将可以把所有的元素排好。

 *插入排序，时间复杂度O(N^2)；空间复杂度O(1)；稳定排序
 *思路：假设数组除最后一个元素都有序了，那么将最后一个元素与前面的比较，如果前面的元素大则向右移动。实际过程从数组的第二个元素开始执行插入排序

 *希尔排序，时间复杂度O(N^1.5)；空间复杂度O(1)；不稳定排序。
 *思路：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。然后将gap逐渐减小重复上述分组和排序的工作。当到达gap=1时，所有元素在统一组内排好序。
 
 *选择排序，时间复杂度O(N^2); 空间复杂度O(1);不稳定排序。
 *思路：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，重复这样的步骤直到全部待排序的数据元素排完。优化：每次最大和最小同时选.

 *堆排序，时间复杂度O(N*logN)；空间复杂度O(1)；不稳定排序。
 *思路：升序为例，构建一个堆结构，然后每个父节点均替换为子节点的最大值，然后根节点就是最大值，重复这个步骤。

 *快速排序，时间复杂度O(N*logN)；空间复杂度O(logN)；不稳定排序。
 *思路：最右边的值为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。确定两个指针left 和right 分别从左边和右边向中间遍历数组。如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。然后右边的指针再走，遇到小于基准值的数就停下来。交换left和right指针对应位置的值。重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。

 *归并排序，递归实现，时间复杂度O(N*logN)；空间复杂度O(N)；稳定排序。
 *思路：采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

c++
#include<iostream>
using namespace std;

int len = 10;
int a[10] = {5,7,2,6,4,1,3,9,8,10};

/*
 *冒泡排序,时间复杂度O(N^2)；空间复杂度：O(1)；稳定排序
 *思路：第一趟：两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置；一共进行n-1趟这样的交换将可以把所有的元素排好。
*/
void MaoPao(int a[]){
    int temp;
    int flag = 0;
    // n-1趟排序
    for(int i = 0; i < len - 1; i++){
        for(int j = 0; j < len - 1 -i; j++){
            if(a[j] > a[j + 1]){
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;
            }
        }
        // 若某一趟排序中没有元素交换则说明所有元素已经有序，不需要再排序
        if(flag == 0)break;
    }
}

/*
 *插入排序，时间复杂度O(N^2)；空间复杂度O(1)；稳定排序
 *思路：假设数组除最后一个元素都有序了，那么将最后一个元素与前面的比较，如果前面的元素大则向右移动。实际过程从数组的第二个元素开始执行插入排序
*/
void ChaRu(int a[]){
    // 从第一轮就从第二个元素开始找，所以n-1轮就可以
    for(int i = 0; i < len - 1; i++){
        // 已经有序的最后一个元素
        int end = i;
        // 需要排序的元素
        int temp = a[end + 1];
        while(end >= 0){
            if(a[end] > temp){
                // 直接替换 循环外面再将被替换的值放到适当位置
                a[end + 1] = a[end];
                end--;
            }
            else{
                break;
            }
        }
        a[end + 1] = temp;
    }
}

/*
 *希尔排序，时间复杂度O(N^1.5)；空间复杂度O(1)；不稳定排序。
 *思路：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。然后将gap逐渐减小重复上述分组和排序的工作。当到达gap=1时，所有元素在统一组内排好序。
*/
void ShellSort(int a[], int n){
    int gap = n;
    while (gap > 1)
    {
        //gap /= 2;
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int x = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > x)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = x;
        }
    }
}

/*
 *选择排序，时间复杂度O(N^2); 空间复杂度O(1);不稳定排序。
 *思路：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，重复这样的步骤直到全部待排序的数据元素排完。优化：每次最大和最小同时选.
*/
void SelectSort(int a[], int n){
    //保存数组的起始位置
    int begin = 0;
    //保存换数组的末尾位置
    int end = n - 1;
    int temp;
    while (begin < end)
	{
            int maxi = begin;//保存最大元素下标
            int mini = begin;//保存最小元素下标
            //遍历数组寻找最小和最大元素
            for (int i = begin; i <= end; i++)
            {
                if (a[i] < a[mini])
                {
                    mini = i;
                }
                if (a[i] > a[maxi])
                {
                    maxi = i;
                }
            }
            //将最小元素交换到起始位置
            temp = a[begin];
            a[begin] = a[mini];
            a[mini] = temp;

            //判断最大值的位置是否在起始位置
            if (maxi == begin)
            {
                    maxi = mini;    
            }
            //将最大元素交换到末尾位置
            temp = a[end];
            a[end] = a[maxi];
            a[maxi] = temp;
            //移动数组起始和末尾位置
            begin++;
            end--;
        }
}

/*
 *堆排序，时间复杂度O(N*logN)；空间复杂度O(1)；不稳定排序。
 *思路：升序为例，构建一个堆结构，然后每个父节点均替换为子节点的最大值，然后根节点就是最大值，重复这个步骤。
*/
void HeapAdjust(int H[], int s, int length)
{
    int tmp = H[s];
    // 左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    int child = 2 * s + 1; 
    while (child < length)
    {
        if (child + 1 < length && H[child] < H[child + 1])
        { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
            child++;
        }
        if (H[s] < H[child])
        {   // 如果较大的子结点大于父结点
            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
            s = child;       // 重新设置s ,即待调整的下一个结点的位置
            child = 2 * s + 1;
        }
        else
        { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
            break;
        }
        H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
    }
}
/**
 * 初始堆进行调整
 * 将H[0..length-1]建成堆
 * 调整完之后第一个元素是序列的最小的元素
 */
void BuildingHeap(int H[], int length)
{
    // 最后一个有孩子的节点的位置 i=  (length -1) / 2
    for (int i = (length - 1) / 2; i >= 0; --i)
        HeapAdjust(H, i, length);
}
void HeapSort(int H[], int length)
{
    // 初始堆
    BuildingHeap(H, length);
    // 从最后一个元素开始对序列进行调整
    for (int i = length - 1; i > 0; --i)
    {
        // 交换堆顶元素H[0]和堆中最后一个元素
        int temp = H[i];
        H[i] = H[0];
        H[0] = temp;
        // 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
        HeapAdjust(H, 0, i);
    }
}

/*
 *快速排序，时间复杂度O(N*logN)；空间复杂度O(logN)；不稳定排序。
 *思路：最右边的值为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。确定两个指针left 和right 分别从左边和右边向中间遍历数组。如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。然后右边的指针再走，遇到小于基准值的数就停下来。交换left和right指针对应位置的值。重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。
*/
int PartSort(int a[], int left, int right){
    // 选最右面为基准
    int key = right;
    while(left < right){
	//选右边为基准值，左指针先走
        while(left < right && a[left] <= a[key]){
            left++;
        }
        //右指针再走
        while(left < right && a[right] >= a[key]){
            right--;
        }
        // 交换
        int temp = a[right];
        a[right] = a[left];
        a[left] = temp;
    }
    int temp = a[key];
    a[key] = a[left];
    a[left] = temp;
    return left;
}
void QuickSort(int a[], int left, int right){
    if(left >= right)return;
    // 第一次快排
    int keyi = PartSort(a, left, right);
    // 左子序列快排
    QuickSort(a, left, keyi - 1);
    // 右子序列快排
    QuickSort(a, keyi + 1, right);
}

/*
 *归并排序，递归实现，时间复杂度O(N*logN)；空间复杂度O(N)；稳定排序。
  *思路：采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
*/
void _MergeSort(int* a, int left, int right,int* tmp)
{
    //区间中没有元素时不再合并
    if (left >= right)
    {
        return;
    }
    //划分数组，每次一分为二
    int mid = (left + right) / 2;
    _MergeSort(a, left, mid,tmp);//划分左区间
    _MergeSort(a, mid + 1, right,tmp);//划分右区间
 
    //合并有序序列
    int begin1 = left, end1 = mid;//有序序列1
    int begin2 = mid + 1, end2 = right;//有序序列2
    int i = left;
    //注意结束条件为一个序列为空时就停止
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }

    //两序列不可能同时为空，将剩余元素合并
    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }

    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
 
    //将合并后的序列拷贝到原数组中
    //在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
    int j = 0;
    for (j = left; j <= right; j++)
    {
        a[j] = tmp[j];
    }
}
void MergeSort(int* a, int n)
{
    //因为需要将两个有序序列合并，需借助额外数组
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    _MergeSort(a, 0, n - 1,tmp);
    free(tmp);
    tmp = NULL;
}

int main(){
    // MaoPao(a);
    // ChaRu(a);
    // ShellSort(a, len);
    // SelectSort(a, len);
    // HeapSort(a, len);
    // QuickSort(a, 0, len - 1);
    // MergeSort(a, len);
    cout<<"out:"<<endl;
    for(int i = 0; i < len; i++){
        cout<<a[i];
        cout<<',';
    }
}

C++容器常见使用

vector

c++
vector<int> v;//默认初始化
vector<int> v(v1);//用v1初始化v
vector<int>v(v1.begin(),v1.end());//用v1初始化v
vector<int> v(10);//定义一个大小为10的数组！
vector<int> v(10,1)//定义个全为1而且长度为10的数组

a.front() //返回第一个元素
a.back() //末尾元素
c.begin() 返回一个迭代器，它指向容器的第一个元素
c.end() 返回一个迭代器，它指向容器的最后一个元素的下一个位置
c.rbegin() //返回一个逆序迭代器，它指向容器的最后一个元素
c.rend() 返回一个逆序迭代器，它指向容器的第一个元素前面的位置
v,push_back() //增
v.insert() //插入
    1、v.insert(p, t) //将t插到p的前面
    2、v.insert(p, n, t) //将n个t插入p之前
    3、v.insert(p, i, j) //将区间[i,j)的元素插入到p之前
v.pop_back();//删除最后一个元素
v.erase(t,k)
    1、v.erase(t,k)//删除[t,k)之间的元素
    2、v.erase(p)//删除p指向的元素
v.chear()==v.erase(begin(),end());//删除所有元素

//下标法
int length = v.size();
for(int i=0;i<length;i++)
    {
        cout<<v[i];
    }
cout<<endl;
//迭代器法
vector<int>::const_iterator iterator = v.begin();
for(;iterator != v.end();iterator++)
    {
        cout<<*iterator;
    }

set容器

set底层实现通常是平衡二叉树元素自动排序，这为查找元素提供了良好性能，但同时也造成了一个重要限制：不能直接改变元素值，因为这会打乱原本正确的顺序。

unordered_set底层实现通常是hash-table元素是无序的。

c++
#include <set>

/*set 生成*/
set<int> st;

/*set 迭代器*/
set<int>::iterator iter 
st.begin() 
st.end() 

/*set 插入*/
st.insert(2); //插入一个元素

/*set 删除*/
st.erase(st.begin()); //删除迭代器指向元素 
st.erase(2); //删除所有为2的元素 

/*set 容量*/
st.size()

/*set 查找*/
st.find(2) //从前往后找，若找到，返回指向该处的迭代器；反之，返回迭代器st.end()
st.lower_bound(x) //二分查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
st.upper_bound(x) //二分查找大于x的元素中最小的一个，并返回指向该元素的迭代器。

/*set 某元素个数*/
st.count(2); //返回容器里2的个数

/*set 判空*/
st.empty() //返回布尔值 

/*set 清空*/
st.clear();

map容器

c++
#include <map>

/*map 生成*/
map<key_type, value_type> name;
map<int, int> mp;

/*map 迭代器*/
map<int, int>::iterator iter
mp.begin() 
mp.end() 

/*map 键值*/
iter->first //key
iter->second //value

/*map 插入*/
mp[2] = 5; //直接添加
mp.insert(pair<int, int>(2, 5)); //insert一个pair

/*删除*/
mp.erase(iter); //删除迭代器所指的键值对 

/*map 容量*/
mp.size()

/*map 查找*/
mp.find(2) //从前往后找，若找到，返回指向该处的迭代器；反之，返回迭代器mp.end()

/*map 某元素个数*/
st.count(2); //返回key为2的个数（map中只可能是0或者1） 

/*map 判空*/
mp.empty() //返回布尔值 

/*map 清空*/
mp.clear();

stack 容器

c++
#include <stack>

/*stack 生成*/
stack<int> sk;

/*stack 插入*/
sk.push(2); //把一个元素放入栈 

/*stack 删除*/
sk.pop(); //删除栈顶的元素 

/*stack 栈顶*/
sk.top(); //返回栈顶元素 

/*stack 容量*/
sk.size();

/*stack 判空*/
sk.empty()

queue容器

c++
#include <queue>

/*queue 生成*/
queue<int> q;

/*queue 头尾*/
q.front();
q.back();

/*queue 插入*/
q.push(2); //在队尾插入一个元素 

/*queue 删除*/
q.pop(); //在队首删除一个元素

/*queue 容量*/
q.size();

/*queue 判空*/
q.empty()

priority_queue 容器

c++
/*
头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。其中priority_queue容器相当于大根堆（或者小根堆），大根堆每次堆顶是最大元素，小根堆每次堆顶是最小元素。（以下typename均用int举例）
*/
#include <queue>

/*priority_queue 生成*/
priority_queue<int> q; //大根堆
priority_queue<int, vector<int>, greater<int>> q; //小根堆

/*priority_queue 插入*/
q.push(2); //把一个元素插入堆 

/*priority_queue 删除*/
q.pop(); //删除堆顶的元素 

/*priority_queue 堆顶*/
q.top(); //返回堆顶元素 

/*priority_queue 容量*/
q.size();

/*priority_queue 判空*/
q.empty()

list双向链表

deque

deque是double ended queue的缩写，是一个动态数组，可以向两端发展(双向开口的连续线性空间)，因此无论在头部或者尾部安插元素都十分迅速，在中间按插元素则比较费时，因为必须移动其他元素。 双端队列的元素被表示为一个分段数组，容器中的元素分段存放在一个个大小固定的数组中，此外，容器还需要维护一个存放这些数组首地址的索引数组。

初始化与定义已经在序列要求里面，而且方法与vector类似，只是多了push_front()(),pop_front(),这里不做过多的阐述。

c++
#include <deque>

/*dequeue 生成*/
dequeue<int> dq;

/*dequeue 头尾*/
dq.front();
dq.back();

/*dequeue 迭代器*/
dq.begin() 
dq.end()

/*dequeue 插入*/
dq.push_front(2); //头插入 
dq.push_back(2); //尾插入 

/*dequeue 删除*/
dq.pop_front(); //头删除 
dq.pop_back(); //尾删除 

/*dequeue 容量*/
dq.size();

/*dequeue 判空*/
dq.empty()

/*dequeue 清空*/
dq.clear();

pair容器

c++
#include <utility>

/*pair 生成*/
pair<int, int> pr = make_pair(0,1);
pair<int, int> pr(0, 1);

/*pair 两个值*/
pr.first 
pr.second 

/*pair 多与其他容器结合使用*/
set<pair<int, int>> st;
vector<pair<int, int>> vct(mp.begin(), mp.end());