# 数据结构：排序与查找算法

> 发布时间: 2026-08-02 18:27

# 数据结构

## 排序算法

### 直接插入排序

```C++
//直接插入排序，逐一遍历，彽者前移，高者向后
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;
	}
}
```

### 冒泡排序

```C++
//冒泡排序，顺降逆升
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;
		}
	}
}
```

### 简单选择排序

```C++
//简单选择排序，逐个寻最小
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;
	}
}
```

### 希尔排序（缩小增量排序）

```C++
//希尔排序&缩小增量排序，指定增量，隔数比较互换，逐步说小增量值直至为一
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;
		}
	}
}
```

### 快速排序

```C++
//快速排序，来回扫描，低着前移，高者向后
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)

```C++
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(log~2~n)
* 空间复杂度：O(1)

```C++
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)

```C++
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;
}
```

### 动态查找表

#### 二叉树查找
#### 哈希查找