冒泡算法
-步骤
-> 比较相邻的元素，如果第一个比第二个大，就交换。
-> 对每一对元素都进行比较，从开始的第一对，到结尾的最后一对。完成后，最后的元素应该是最大的。
-> 针对所有的元素重复上面的步骤，除了最后一个。
-> 持续每次对越来越少的元素重复上面的步骤，直到没有一对数字需要比较。
void BubbleSort(int* h, size_t len)
{
if(h == NULL) return;
if(len <= 1) return;
// i是次数，j是具体下标
for(int i = 0; i < len - 1; i++)
{
for(int j = 0; j < len - 1 - i; j++)
{
if(h[j] > h[j+1])
{
Swap(h[j], h[j + 1])
}
}
}
}
选择排序
-步骤
-> 在未排序的序列中找到最小（大）的元素，存放到排序序列的最前面。
-> 从剩余未排序的序列中继续寻找最小（大）的元素，然后放到已排序的序列末尾。
-> 重复第二步，直到所有元素均排序完毕。
-理解
选择排序是在未排序的序列里每次去找最大(小)的元素。永远在矮子里面拔高个，被选出来的那一刻，就确定好了自己的位置排名。
void SelectionSort(int* h, size_t len)
{
if(h == NULL) return;
if(len <= 1) return;
int minindex, i, j;
// i是次数，也即排好的个数，j是继续排
for (i = 0; i < len; i++) // 遍历选到最小的值
{
minindex = i;
// 每轮需要比较的次数是len - i
for(int j = i + 1; j < len; j++)
{
if(h[j] < h[minindex]) minindex = j; // 一轮下来，minindex都是最小的值
}
// 将每次找到的最小值都依次放在i位置
Swap(h(i), h[minindex]); //这样依次排好了前i个数
}
}
插入排序
-步骤
-> 将待排序的序列的第一个元素看作是一个有序的序列，把第二个元素到最后一个元素的序列看作是一个未排序的序列。
-> 从头到尾依次扫描未排序的序列，将扫描到的每个元素插入到前面有序序列的正确位置。（如果待插入的序列中有与选择的元素相同的元素，那么将这个元素插入到相等元素后面。）
-理解
插入排序是，每一个值都去已经排好队的序列里找自己的位置。
每一个值都不需要等，轮到自己的时候一定会给自己安排上位置，只不过后面还有可能被挤掉就是了。
void InsertSort(int* h, size_t len)
{
if(h == null) return;
if( len <= 1) return;
// 从下标1开始，i代表已经排好序的元素个数
for (int i = 1; i < len; i++)
{
// 用拿到的每一个元素去前面比较，直到找到合适的位置break
for (int j = i; j > 0; j-- )
{
if (h[j] < h[j - 1])
{
Swap(h[j], h[j - 1])
} else
{
break;
}
}
}
return;
}
希尔排序
[理解了过程，但是用代码实现还是有点不熟悉，不理解]
-步骤
-> 选择一个增量序列，t1,t2,...,tk ,其中ti > tj, tk = 1;
-> 按增量序列的个数，对序列进行k趟排序。
-> 每趟排序，根据对应的增量值ti,将待排序序列分割成若干个长度为m的子序列，分别对各子序列进行插入排序，仅增量因子的值为1时，整个序列作为一个表来处理，表的长度即为序列的长度。
-理解
-> 希尔排序采用的是跳跃式的分组策略，通过某个增量，将数组划分为若干组子序列。然后分组进行插入排序，随后逐步缩小增量，继续这个操作，直至增量为1。
-> 这种策略，在初始阶段就可以达到基本有序的程度，然后随着缩小增量，多数情况下后面只要数据微调即可，不会涉及过多数据移动。
-> 我们实现这个算法的时候，使用的增量gap = length/2,缩小增量也以gap/2的方式，这种增量的选择我们可以使用一个序列表示 ,{n/2, (n/2)/2,...,1},这个就是增量序列。增量序列的选择和证明都是个数学难题，我们用的这个增量序列是比较常用的，也是希尔建议的增量，亦称为希尔增量，但其实这个增量不是最优的。
void ShellSort(int* h, size_t len)
{
if(h == null) return;
if(len <= 1) return;
// 增量序列的个数就是对整个序列排序的次数
// 增量gap，并逐步缩小gap
for(int div = len/2; div >= 1; div/=2 )
{
for(k = 0; k <div; k++)
{
for(int i = div + k; i < len; i+=div)
{
for(int j = i; j > k; j -= div)
{
if(h[j] < h[j - div]) swap(h[j], h[j - div]);
else break;
}
}
}
}
}
归并排序
-步骤
当我们拿到一个序列的时候：
我们先把它一份为二，像下面这样：
我们现在要做的是分别把左边的和右边的数组进行排序，然后再把两个排好的序列归并在一起。当然我们在分别排一半的序列的时候，也同样使用这种一分为二的方式，这样这个序列又被分成了下面这样：
继续这样的步骤，直到把这个细度分到每个部分只有一个元素为止：
现在每个序列里只有一个元素了，我们用不着排序了，一个元素的序列当然是已经排好序的，现在我们要做的只剩下归并了。
在从一个元素归并到两个元素的过程中，形成了含有两个元素的新序列，我们当然也要让新序列变得有序。
依次类推，我们要继续归并成有四个元素的新序列：
直至最后归并完成：
image.png
现在我们已经直到了这个算法的实现过程 ，但是分序列容易，归并这件事情该如何完成呢？当我们现在有了两个已经排好序的序列时，我们要把它们合并成一个有序的序列，要怎么办效率比较高呢？
这里我们可以申请一块内存，用来存放将要合并好的序列，因为在现代计算机中，时间复杂度是要比空间复杂度要更优先考虑的事情，毕竟内存也好，硬盘也罢，现在是变得越来越能存储了。（这里用了O(n)的额外空间来完成这件事件）
至于在归并过程中使用插入算法还是快速排序那都是很随意的。
这时我们连同额外申请的辅助内存序列外，一共有了三个序列，所以这变成了一个具有三个索引的实现方法。
-理解
归并排序是使用了分治的方法策略，将问题分成一个个小的部分然后递归求解，而治则是说将分的阶段获得的答案拼在一起。分而治之。
归并排序可以使用递归的方法实现，也可以用迭代。递归和迭代这两种算法思想也是非常基础和重要的，我会在专门的章节去学习理解。
分的阶段可以采用递归的方法去拆分子序列，递归深度为log2n.
治的阶段则是把两个已经有序的序列进行合并。
网友评论