排序算法系列目录

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

---

1.插入排序

自定义的说法：
1.满足排序指：
当升序时，a[j]<a[j+k]，即a[j]<tmp
当降序时，a[j]>a[j+k]，即a[j]>tmp
2.有效数组：指插入数字tmp前面的所有数据构成的数组
3.当有效数组中元素和tmp相比，当不满足排序时：就向后挪动数据，并且数组下标j–；
直到找到满足排序的下标（主动break出循环，记录下标）。但是如果遍历完整个有效数组后，都不满足排序，此时j=-1（会自动出循环时的下标，记录下标）；
总结就是：不满足排序，挪动数据 满足排序记录下标，在循环外面 插入数据
4.时间复杂度为：O(n^2)
5.先选择要插入的数据：范围是[1,n）
选取插入数据tmp后，然后让要插入的数据tmp，与前面的有效数组依次进行比较。

代码：

#include <stdio.h>
void InsertSort(int* a, int n)
{
    for(int i =1;i<n;i++)
    {
        int tmp = a[i];
        int j;
        for(j=i-1;j>=0;j--)
        {
            if(a[j]>tmp)
            {
                a[j+1]=a[j];
            }
            else
            {
                break;       
            }            
        }
        a[j + 1] = tmp;
    }
}
int main()
{
    int a[10]={5,61,2,3,8,0,6,7,8};
    InsertSort(a,10);
    for(int j=0;j<10;j++)
    {
        printf("%d  ",a[j]);
    }
}

2.希尔排序

直接排序的优化：
gap=3 先分组然后再对每组进行插入排序

要插入的数据从下标从gap开始，到小于n，即 [gap，n）
当插入数据tmp=arr[x]时，有效数组下标为[0,x-gap]

void ShellSort(int *a ,int n)
{
    int gap = n;
    while(gap>1)
    {
        gap = gap / 3 + 1;
        for(int i = gap;i<n;i++)
        {
            //先拿下标为gap数据插入到前面的数据中
            //gap+1
            int tmp= a[i];
            int j;
            for (j = i - gap; j >= 0; j-=gap)
            {
                if(a[j]>tmp)
                {
                    a[j+gap] = a[j];
                }
                else
                {
                    break;
                }
            }
            a[j+gap] = tmp;
        }
    }
}
int main()
{
    int a[9]={1,3,6,2,0,7,4,9,3};
    int size = sizeof(a) / sizeof(a[0]);
    ShellSort(a, size);
    for (int j = 0; j < size; j++)
    {
        printf("%d  ",a[j]);
    }
}

代码逻辑：把间隔为gap的多组同时排序，而不是一个一个的排序

2.1

2.2

2.3

3.pandas是什么？

3.1

3.2

3.3

4.pandas是什么？

4.1

4.2

4.3