算法>排序算法系列目录
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;
}
>>>>>>>>>>>>优化代码>>>>>>>>>>>>>
/* for(j=i-1;j>=0 && a[j]>tmp;j--)
{
a[j+1] = a[j];
} */
>>>>>>>>>>>>>>>>>>>>>>>>>>>
}
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的多组同时排序，而不是一组一组的排序
时间复杂度：O(log3NN)
gap=n
gap = gap/3+1 ；则N/3/3/3/3…=1 每进行一次分组，n/3，
分了log3N 次 3为底。分组后的插入排序为近似0(n),整体则为时间复杂度为O(log3NN)。
3：直接选择排序
基本思想是：
1.第一遍选出最小的数放在第一个位置
2.第二遍选出最小的数放在第二个位置
…
void SelectSort(int *a, int n) {
for (int begin = 0; begin < n - 1; begin++)
{
int minIndex = begin;
for (int i = begin + 1; i < n; i++)
{
if (a[minIndex] > a[i])
{
minIndex = i;
}
}
swap(&a[begin],&a[minIndex]);
}
}
3：堆排序
直接选择排序的优化
3.1 堆的定义：
1.结构上是用数组表示的完全二叉树
2.有序性：满足大堆或者小堆的要求
大堆定义：树中所有父亲都要大于等于孩子
小堆定义：树中所有父亲都要小于等于孩子
堆结构在下标上：父子在下标上的关系
leftchild = parent *2 +1
rightchild = parent *2 +1
parent = (child-1)/2
3.2 堆排序的流程
升序：
1.采用向下调整算法，将数组变成一个大堆(根为最大值)。
2.将大堆的第一个数(最大值)和最后一个数交互，将最大值放在最后一个位置。
3.此时左子树和右子树都是大堆，采用向下调整算法，选出次大的。
void AdjustDwon(int *a , int n , int root)
{
int parent = root;
int child = parent *2 + 1;
while(child <n)
{
if
}
}
