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次。
关于堆的知识还有很多，后面单独再写一个章节来详细堆的相关特性。