常见的算法>排序算法
冒泡排序，简单排序，插入排序等算法时间复杂度为 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，则表示数组已经填充完毕，开始滑动窗滤波。
