常见的排序算法

冒泡排序，简单排序，插入排序等算法时间复杂度为 n^2，在某些场景下如已知有序的数组中进行排序，调用这些算法可以有效地完成排序功能。

其源码如下：

/************************************************
* title     : 交换
* 算法复杂度 : 	
************************************************/
void swap(SqList *L,int i,int j)
{
	int temp = L->r[i];
	L->r[i] = L->r[j];
	L->r[j] = temp;
}

/************************************************
* title     : 冒泡排序
* 算法复杂度 : 	n^2  时间复杂度
************************************************/
void BubbleSort(SqList *L)
{
	int i,j;
	bool flag = true;
	for(i = 1;i < L->length && flag;i++)
	{
		flag = false;
		for(j = L->length-1;j >= i;j--)
		{
			if(L->r[j] > L-r[j+1])
			{
				swap(L,j,j+1);
				flag = true; /*已知有序可减少遍历次数*/
			}
		}
	}
}

/************************************************
* title     : 简单选择排序
* 算法复杂度 : 	n^2  时间复杂度 但排序性能略优于冒泡
************************************************/
void SelectSort(SqList *L)
{
	int i,j,min;
	for(i = 1;i < L->length;i++)
	{
		min = i;
		for(j = i + 1;j <= L->length;j++)
		{
			if(L->r[min]>L->r[j])
				min = j;
		}
		if(i != min)
		{
			swap(L,i,min);
		}
	}
}

/************************************************
 * title     : 直接插入排序
 * 算法复杂度 : 	n^2  时间复杂度 适用于已经有序数组
 * 的插入√
************************************************/
void InsertSort(SqList *L)
{
	int i,j;
	for(i = 2;i <= L->length;i++)
	{
		if(L->r[i] < L->r[i - 1])
		{
			L->r[0] = L->r[i]; // 设置哨兵
			for(j = i - 1;L->r[j] > L->r[0] ;j--) //遍历，直到找到比哨兵小的值，退出
			{
				L->r[j + 1] = L->r[j];
			}
			L->r[j + 1] = L->r[0];
		}
	}
}

快速排序算法

快速排序算法分为三步：

• 找基准数，为了方便我们将基准数设置为数组中第一个数。
• 从待排序的数组的头和尾放两个指针，从尾往前遍历，寻找小于基准数的成员，与基准数交换值，此时基准数位于尾指针处。在从头指针向后遍历，寻找大于基准数的成员，与基准数交换值，此时基准数位于头指针处。重复这个步骤，直到头尾指针重叠，以基准数为枢轴，所以小于基准数的都在左边，所有大于基准数的都在右边。
• 对枢轴左边和右边区域重复1 2步骤，直到所有区间排序完成。

具体代码如下：

/*对顺序表进行快速排序*/
void QuickSort(SqList *L)
{
	QSort(L,1,L->length);
}

void QSort(SqList *L,int low,int high)
{
	int pivot;
	if(low < high)
	{
		pivot = Partition(L,low,high);

		QSort(L,low,pivot-1);   //对低子表递归排序
		QSort(L,pivot+1,high);  //对高子表递归排序
	}
}

int Partition(SqList *L,int low,int high)
{
	int pivotkey;
	pivotkey = L->r[low]; //用子表的第一个记录作为枢轴

	while (low < high)
	{
		while(low < high && L->r[high] >= pivotkey)
		{
			high--;
		}
		swap(L,low,high);

		while(low < high && L->r[low] <= pivotkey)
		{
			low++;
		}
		swap(L,low,high);
	}
	return low; // pivotkey location
}

快速排序的算法复杂度从 n*logn 到 n^2，对应着最优情况到最差情况。
上面代码中我们的基准数选取是选取数组第一个，可以通过优化基准数的选取从而优化算法。
基准数的选取可以从待排序数组中，随机选取三个数，然后以这三个数中间大小的数作为基准数。这里就不做演示了。

快速排序的应用

快速排序的应用，也可以理解为对排序算法的应用，这里有一个场景，我们要对采集的编码器数据做低通滤波，要求是用滑动平均窗滤波算法实现。具体代码如下：

/*******************************************************************************
* Function Name  : MySqListAdd
* Description    : 往缓冲区填入数据，直到填满在从头开始
* Input          : L  缓冲区结构体
                   data 填入缓冲区的数据
* Output         : None
* Return         : false 缓冲区还未填满
                   true  缓冲区已经填满
*******************************************************************************/
static bool MySqListAdd(SqList *L , QuickSortElem data)
{
    static uint8_t tmp = 1;
    if(L->length < MAXSIZE)
    {
        L->r[tmp] = data;
        tmp++;
        L->length++;
        
        return false;
        
    } else if(L->length == MAXSIZE) {
        
        tmp = (tmp > MAXSIZE) ? 1 : tmp++;
        L->r[tmp] = data;
        
        return true;
        
    }
    
    return false;
    
}

/*******************************************************************************
* Function Name  : MySqListMovingAverageWindowFilter
* Description    : 滑动平均窗滤波函数
* Input          : L  缓冲区结构体
* Output         : None
* Return         : 0 表示数据还没填充完成
                   else 滤波后的结果
*******************************************************************************/
QuickSortElem MySqListMovingAverageWindowFilter(SqList *L , QuickSortElem data)
{
    uint8_t tmp;
    int32_t sum;
    if(MySqListAdd(L,data))
    {
        
        QuickSort(L);
        
        for(tmp = 2;tmp < MAXSIZE;tmp++)
        {
            sum += L->r[tmp];
        }
        sum = sum / (MAXSIZE - 2);
        
        return sum;
        
    }
    
    return 0;
}

只需要调用

MySqListMovingAverageWindowFilter( &L , data)

这个函数，就可以实现低通滤波，可以通过改变 MAXSIZE 的值，来改变滑动窗窗口大小。调用这个函数，直到返回的数不为0，则表示数组已经填充完毕，开始滑动窗滤波。