image.png
排序算法相关代码实现
插入类
直接插入排序
/* 插入排序 */
void InsertSort(int *array,int array_lenth)
{
int i = 0,j = 0;
int temp = 0;
for(i = 1;i < array_lenth;i++)
{
if (array[i] < array[i-1]) /* 需将array[i]插入有序子表 */
{
temp = array[i]; /* 设置比较对象 */
for(j = i-1; j >= 0 && array[j] > temp; j--)/* 将大于array[i]的向后移动*/
array[j+1] = array[j];
/* 循环结束后，array[i]为第一个小于guard的值，所以将guard插入起后*/
array[j+1] = temp;
}
}
}
从插入排序的实现，可以发现另外的关键特征。
1.在没有完成最终排序之前，没有一个元素位于目标位置。
算法复杂度和空间复杂度等相关内容可以结合之前2.1部分的内容对比一下，加深理解和记忆。
希尔排序
/* 希尔排序 */
void ShellSort(int *array,int array_lenth)
{
int i = 0,j = 0,k = 0;
int inc = array_lenth;
int temp = 0;
do
{
inc = inc/2;/* 增量序列 n/2向下取整*/
/* 选定增量后，以增量为递增做插入排序，下面两个for循环实现是插入排序，不再赘述*/
for(i = inc;i < array_lenth;i++)
{
if (array[i] < array[i-inc])
{
temp = array[i];
for(j = i - inc; j >= 0 && temp < array[j] ; j -= inc)
array[j+inc] = array[j];
array[j+inc] = temp;
}
}
while(inc > 1);
}
从插希尔排序的实现，可以发现希尔排序是做了增量变化的 直接插入排序，关于增量如何选择可以得到最优解，也是有很多的数学论证的。
交换类
冒泡略去
快速排序
#include <stdio.h>
void print(int *array, int array_length)
{
int i;
for(i = 0;i < array_length;i++)
printf("%d ",array[i]);
printf("\n");
}
void swap(int *array,int i,int j)
{
int temp = array[i];
array[i] = array[j];
array[j]=temp;
}
/* 找到该子序列的分裂中轴 ，注解1*/
int split(int *array,int low,int high){//5,4,8,19,6,7,10,2,3,5}
int pivot;
pivot = array[low]; /* 选择第一个元素 */
while(low < high) /* 从两端向中间扫描 */
{
while(low < high && array[high] >= pivot)//优先从对端开始扫描
high--;
swap(array,low,high);/* 找到比pivot小的元素交换到前面 */
while(low < high && array[low] <= pivot)
low++;
swap(array,low,high);/* 找到比pivot大的元素交换到后面 */
}
return low; /* 返回pivot所在索引 */
}
/* 从low到high作快速排序 */
void qsort(int *array,int low,int high)
{
int pivot;
if(low < high)
{
pivot = split(array,low,high); /* 按中轴分裂原序列 */
qsort(array,low,pivot-1); /* 对低子序列递归排序 */
qsort(array,pivot+1,high); /* 对高子序列递归排序 */
}
}
void quicksort(int *array,int array_length){
qsort(array ,0 ,array_length-1);
}
int main() {
int array[10] = {5,4,8,19,6,7,10,2,3,5};//2,3,4,5,5,6,7,8,10,19
int array_length = 10;
quicksort(array,array_length);
print(array,array_length);
return 0;
}
注解1
扫描方式不一定是从头或者尾开始，也可以将中轴设置在任意位置，最终通过比较和交换，以中轴为界分离两个子序列。
选择类
选择排序略去
堆排序
堆排序也会引入树的相关操作，在一般的demo级排序算法中，也是以数组方式实现排序算法。
#include <stdio.h>
void print(int *array,int array_lenth)
{
int i;
for(i = 0;i < array_lenth;i++)
printf("%d,",array[i]);
printf("\n");
}
void swap(int *array,int i,int j)
{
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
//生成大顶堆
void HeapAdjust(int *array,int s,int array_lenth)
{
int temp,j;
if(s < 1) return;
temp = array[s-1];
for(j = 2*s; j<=array_lenth ; j*=2) //从上往下循环树的每一层遍历，构建大顶堆
{
if(j < array_lenth && array[j-1] < array[j])
++j;
if(temp >= array[j-1])
break;
array[s-1] = array[j-1];
s=j;//这里交换并没有完成最后一步赋值，留到最后再做处理
}
array[s-1]=temp; //这里最后做一次赋值，减少重复赋值次数
}
void HeapSort(int *array,int array_lenth)
{
int i;
for(i = array_lenth/2; i > 0;i--) /*把array数组构生成一个大顶堆 注解*/
HeapAdjust(array,i,array_lenth);
print(array,array_lenth);
for(i = array_lenth;i > 1;i--)
{
swap(array,0,i-1); /* 注解 ，每次交换根节点与尾节点*/
print(array,array_lenth);
HeapAdjust(array,1,i-1); /* 将剩余节点调整为大顶堆 */
}
}
int main(int argc, char *argv[])
{
int array[10] = {9,5,8,4,6,3,2,5,12,10};//{2,3,4,5,5,6,8,9,10,12};
int array_length = 10;
HeapSort(array,array_length);
print(array,array_length);
}
注解1：
完全二叉树由于其结构上的特点，通常采用顺序存储方式存储。一棵有n个结点的完全二叉树的所有结点从1到n编号，就得到结点的一个线性系列。
完全二叉树除最下面一层外，各层都被结点充满了，每一层结点的个数恰好是上一层结点个数的2倍，因此通过一个结点的编号就可以推知它的双亲结点及左，右孩子结点的编号：
① 当 2i ≤ n 时，结点 i 的左孩子是 2i，否则结点i没有左孩子；
② 当 2i+1 ≤ n 时，结点i的右孩子是 2i+1，否则结点i没有右孩子；
③ 当 i ≠ 1 时，结点i的双亲是结点 i/2；
上述特性是二叉树遍历的关键，然其中n是从1开始的。但是数组下标是从0开始，所以遍历二叉树的时候i从1~n，而每次访问array的时候需要对i做减一。
for(i = array_lenth/2; i > 0;i--) 该循环是对全部的非叶节点从下往上构建堆，基于完全二叉树特性，需要循环array_lenth/2次。
关于堆的知识还有很多，后面单独再写一个章节来详细堆的相关特性。
