【WP】2019年秋季-第16周-张巨梩

[ConnorTomato]

1.排序算法学习 A.插入排序

 #include<stdio.h>
int number[100000000];     //在外面定义数组 
void insertion_sort(int *number,int n)    //定义一个插入函数"insertion_sort" 
{
    int i=0,ii=0,temp=0;  
    for(i=1;i<n;i++)  //循环遍历 
    {
        temp=number[i];  //将temp每一次赋值为number[i] 
        ii=i-1;  
        while(ii>=0&&temp<number[ii])   //这里改顺序 (temp后的)"<"为小到大，">"为大到小 ！！！
        {
            number[ii+1]=number[ii];    //将大的元素往前放 
            ii--; 
        }
        number[ii+1]=temp;   //与"number[ii+1]=number[ii];"一起意为 
    }              //如果插入的数比之前的大,将number[ii]与number[ii+1]互换 
}
int main() 
{
    int i=0,n;
    printf("输入数字个数：\n");    
    scanf("%d",&n);       //输入要排序的数字的个数 
    printf("输入%d个数:\n",n);
    for(int j=0;j<n;j++)       //将所有数全放入number数组中 
        scanf("%d",&number[j]) ;
    insertion_sort(number,n);   //引用插入函数 
    for(i=0;i<n-1;i++)    //循环输出 
        printf("%d ",number[i]);    //格式需要  
    printf("%d\n",number[i]);
    return 0;
}

学习了原理，未操作实践.

---

B.归并排序 将初始数组分为left,right两部分，sort使两部分呈有序排列，再合并。

B站视频 学习代码（手动实现）

#include<stdio.h>
void merge(int arr[], int l, int m, int r) {
    const int left_size = m - l;
    const int right_size = r - m + 1;
    int left[left_size];
    int right[right_size];
    int i, j, k;
    for (i = l; i < m; i++)
        left[i - l] = arr[i];
    for (i = m; i <= r; i++)
        right[i - m] = arr[i];
    i = 0, j = 0, k = l;
    while (i < left_size && j < right_size)
    {
        if (left[i] < right[j])
        {
            arr[k] = left[i];
            k++;
            i++;
        }
        else
        {
            arr[k] = right[j];
            k++;
            j++;
        }
    }
    while (i < left_size)
    {
        arr[k] = left[i];
        k++;
        i++;
    }
    while (j < right_size)
    {
        arr[k] = right[j];
        k++;
        j++;
    }

}
void mergesort(int arr[], int l, int r) {
    if (l == r)  return;
    else {
        int  m = (l + r) / 2;
        mergesort(arr, l, m);
        mergesort(arr, m + 1, r);
        merge(arr, l, m + 1, r);

    }
}
int main()
{
    int n;
    int arr[1000000];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    mergesort(arr, 0, n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
}

网上PO的优化代码（复制粘贴）

    #include<stdio.h>

void Merge_Sort(int* arr, int* temparr, int start, int mid, int end)
{
    int left_start = start;
    int left_end = mid;

    int right_start = mid + 1;
    int right_end = end;

    int index = start;

    while (left_start <= left_end && right_start <= right_end)
    {
        if (arr[left_start] > arr[right_start])
            temparr[index++] = arr[right_start++];
        else
            temparr[index++] = arr[left_start++];
    }

    while (left_start <= left_end)
        temparr[index++] = arr[left_start++];

    while (right_start <= right_end)
        temparr[index++] = arr[right_start++];

    for (index = start; index <= end; ++index)
        arr[index] = temparr[index];
}
void Sort_Message(int* arr, int* temparr, int start, int end)
{
    if (start < end)
    {
        int mid = (start + end) / 2;
        Sort_Message(arr, temparr, start, mid);
        Sort_Message(arr, temparr, mid + 1, end);
        Merge_Sort(arr, temparr, start, mid, end);
    }
}

int main(void)
{
    int a[1000000];
    int i, temp[1000000];
    int n;
    scanf_s("%d", &n);
    for (i = 0; i < n; ++i)
        scanf_s("%d", &a[i]);
    Sort_Message(a, temp, 0, n - 1);
    for (i = 0; i < n; ++i)
    printf("%d ", a[i]);
    return 0;
}

手动实现，全文背诵.

题目：排序找第三大的数字

1.冒泡外层走3三趟可以找出（174ms)。

2. 冒泡n-1趟【超时】； 3.插入排序【超时】； 4.只有归并(304ms)可以强行全排序完输出，可以过机器。

---

问题：用排序算法排序八百万个数的最快时间是多少？

单位是毫秒。显示“没有测试”的是因为慢到没朋友，直接跳过。Release模式下，开的o2优化： 来源是知乎！

---

2.新生赛补题 已补3个题。 后知后觉

• 买笔、可持续都是数学题， 字符串检索比对的下来花1-2h补充知识。

---

3.数据结构 目标：

• AVL 哈希表 堆这些简单的数据结构得自己实现过。
• 链表、线性表必须熟悉到不能再熟悉。

---

4.学习外的生活 到期末，课渐少，我可支配的时间越来越多。 总结

• 运动：哑铃每次1.5h（周一、周三） ————————————————【完成】
• 自私的基因（15/15） ——————————————————————【完成】 -———决定要去阅读相关专业书籍，就加快速度阅读，为此专门学习的阅读技巧及如何做读书笔记。
• 排序算法（插入、归并）—————————————————————【完成】 ————排序算法就只学这两个，下一步熟练运用。
• AVL(二叉树）—————————————————————————【未完成】
• 奇葩说最新的两期期——————————————————————【未完成】 ————用的碎片化时间每次看十几分钟，鬼知道看到什么时候。

同情心、同理心和你对世界的认知有关。 ——————黄执中