数据结构
排序算法
直接插入排序
//直接插入排序，逐一遍历，彽者前移，高者向后
void CSort::InsertSort(int* data, int nSize)
{
int nTmp = 0;
for (int i = 0; i < nSize; i++)
{
int nIdx = i;
nTmp = data[i];
for (int j = i - 1; j >= 0 && data[j] > nTmp; j--)
{
data[nIdx] = data[j];
nIdx--;
}
data[nIdx] = nTmp;
}
}
冒泡排序
//冒泡排序，顺降逆升
void CSort::BobbleSort(int* data, int nSize)
{
for (int i = 0; i < nSize; i++)
{
bool bChange = false;
for (int j = 0; j < nSize - 1 - i; j++)
{
if (data[j] > data[j + 1])
{
int nTemp = data[j];
data[j] = data[j + 1];
data[j + 1] = nTemp;
bChange = true;
}
}
if (!bChange)
{
break;
}
}
}
简单选择排序
//简单选择排序，逐个寻最小
void CSort::SelectSort(int* data, int nSize)
{
for (int i = 0; i < nSize; i++)
{
int nIdx = i;
int nTmp = data[i];
for (int j = i + 1; j < nSize; j++)
{
if (data[j] < nTmp)
{
nTmp = data[j];
nIdx = j;
}
}
data[nIdx] = data[i];
data[i] = nTmp;
}
}
希尔排序&缩小增量排序
//希尔排序&缩小增量排序，指定增量，隔数比较互换，逐步说小增量值直至为一
void CSort::ShellSort(int* data, int nSize)
{
int nGap = nSize;
while (true)
{
nGap = (nGap+1)/2;
for (int i = nGap; i < nSize; i++)
{
//
for(int j = i-nGap;j>=0&&data[j] > data[j+ nGap];j--)
{
int nTemp = data[j];
data[j] = data[j + nGap];
data[j + nGap] = nTemp;
}
}
if (nGap == 1)
{
break;
}
}
}
快速排序
//快速排序，来回扫描，低着前移，高者向后
void CSort::QuickSort(int* data, int nSize)
{
ST_Range stRange(0, nSize - 1);
stack<ST_Range> stackRange;
stackRange.push(stRange);
while (!stackRange.empty())
{
ST_Range _stRange = stackRange.top();
stackRange.pop();
int nLow = _stRange.nLow;
int nHigh = _stRange.nHigh;
if (nLow < 0 || nHigh < 0) continue;
if (nLow >= nSize || nHigh >= nSize) continue;
if (nLow >= nHigh)continue;
int nTmp = data[nLow];
while (nHigh > nLow)
{
for (int i = nHigh; i >= nLow && data[nHigh] > nTmp; i--)
{
nHigh = i;
}
data[nLow] = data[nHigh];
for (int i = nLow; i <= nHigh && data[nLow] < nTmp; i++)
{
nLow = i;
}
data[nHigh] = data[nLow];
}
data[nLow] = nTmp;
ST_Range _stRange_Low(_stRange.nLow, nLow - 1);
ST_Range _stRange_High(nLow + 1, _stRange.nHigh);
stackRange.push(_stRange_Low);
stackRange.push(_stRange_High);
}
}
归并排序
堆排序
计数排序
桶排序
堆排序
查找算法
静态查找表
顺序查找
- 描述：从左到右依次匹配键值，找到则返回成功，未找到则返回失败
- 时间复杂度：O(n);
- 空间复杂度：O(1);
CSelect::ST_Data* CSelect::Search_Seq(ST_Data* pArryData, int nSize,int idSearch)
{
for (int i = 0; i < nSize; i++)
{
if (pArryData[i].GetID() == idSearch)
{
return &pArryData[i];
}
}
return NULL;
}
二分查找
- 描述：只针对有序查找，从中间值开始查找，若比目标值大则向后的中间值查找，反之前向查找
- 时间复杂度：O(log2n)
- 空间复杂度：O(1);
CSelect::ST_Data* CSelect::Search_Bin(ST_Data* pArryData, int nSize, int idSearch)
{
int nLow = 0;
int nHigh = nSize - 1;
int nMid = 0;
while (nLow != nMid || nMid != nHigh)
{
if (nLow > nHigh) break;
if (nLow < 0 || nLow >= nSize) break;
if (nHigh < 0 || nHigh >= nSize) break;
nMid = (nLow + nHigh) / 2;
if (nMid < 0 || nMid >= nSize) break;
if (pArryData[nMid].GetID() > idSearch)
{
nHigh = nMid - 1;
}
else if (pArryData[nMid].GetID() < idSearch)
{
nLow = nMid + 1 ;
}
else
{
return &pArryData[nMid];
}
}
return NULL;
}
插值查找
- 描述:只针对顺序查找等差分段，根据待查值自适应中间值
- 时间复杂度:O(log(logn))~O(n)
- 空间复杂度:O(1);
CSelect::ST_Data* CSelect::Search_Insert(ST_Data* pArryData, int nSize, int idSearch)
{
int nLow = 0;
int nHigh = nSize - 1;
while (nLow != nHigh)
{
if (nLow > nHigh) break;
if (nLow < 0 || nLow >= nSize) break;
if (nHigh < 0 || nHigh >= nSize) break;
int nLowValue = pArryData[nLow].GetID();
int nHigValue = pArryData[nHigh].GetID();
int nMid = nLow + (idSearch - nLowValue) * (nHigh - nLow) / (nHigValue - nLowValue);
if (nMid < 0 || nMid >= nSize) break;
if (pArryData[nMid].GetID() > idSearch)
{
nHigh = nMid - 1;
}
else if (pArryData[nMid].GetID() < idSearch)
{
nLow = nMid + 1;
}
else
{
return &pArryData[nMid];
}
}
return NULL;
}