排序算法：
-
冒泡排序（Bubble Sort）：通过重复地比较相邻的元素并交换它们，使得最大（或最小）的元素逐渐移动到列表的一端，从而实现排序。
-
选择排序（Selection Sort）：在未排序的部分中，选择最小（或最大）的元素，并将其放置在已排序部分的末尾，以此方式逐步构建排序序列。
-
插入排序（Insertion Sort）：将未排序的元素逐个插入到已排序部分的正确位置，以此方式逐步构建排序序列。
-
快速排序（Quick Sort）：选择一个基准元素，通过将比基准小的元素放在基准的左边，比基准大的元素放在基准的右边，将列表分割为两个子列表。然后对子列表递归地应用快速排序，直到列表完全排序。
-
归并排序（Merge Sort）：将列表递归地分割成较小的子列表，然后将子列表进行合并，直到最终得到完全排序的列表。合并操作是将两个有序的子列表合并为一个有序列表。
-
堆排序（Heap Sort）：将列表构建为最大堆（或最小堆），然后将堆顶元素与末尾元素交换，并重新调整堆，重复该过程直到列表完全排序。
-
希尔排序（Shell Sort）：将列表按照一定的间隔分组，对每个分组内的元素进行插入排序，然后逐渐缩小间隔，重复该过程直到间隔为1，最后进行一次完全插入排序。
-
计数排序（Counting Sort）：统计列表中每个元素的出现次数，然后根据统计信息将元素放置到正确的位置上，从而实现排序。
-
桶排序（Bucket Sort）：将列表划分为一定数量的桶，每个桶存储一定范围的元素。然后对每个桶内的元素进行排序，最后按照桶的顺序依次输出所有元素，从而得到排序结果。
-
基数排序（Radix Sort）：按照元素的位数进行排序，先按照最低位排序，然后依次向高位进行排序，直到最高位排序完成。
搜索算法：
-
二分查找（Binary Search）：对于已排序的列表，通过重复地将列表分成两半，并确定目标元素可能存在的半边，从而快速定位目标元素的位置。
-
广度优先搜索（Breadth-First Search）：从起始节点开始，逐层地遍历图或树的节点，先访问当前节点的所有邻居节点，然后再依次访问邻居节点的邻居节点，以此类推，直到遍历完所有可达节点。
-
深度优先搜索（Depth-First Search）：从起始节点开始，沿着一条路径一直访问下去，直到到达最深的节点，然后回溯并选择另一条路径继续访问，直到遍历完所有可达节点。
这些排序算法和搜索算法在不同的场景和数据结构中都有广泛的应用，每个算法都有其特定的优势和适用性。选择合适的算法取决于数据的特点和排序/搜索的要求。
具体程序示例：
//冒泡排序（Bubble Sort）
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
//选择排序（Selection Sort）
void selectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
//插入排序（Insertion Sort）
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
//快速排序（Quick Sort）
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换基准元素
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
//归并排序（Merge Sort）
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int* leftArr = new int[n1];
int* rightArr = new int[n2];
for (int i = 0; i < n1; i++) {
leftArr[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
rightArr[j] = arr[mid + 1 + j];
}
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
}
else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
delete[] leftArr;
delete[] rightArr;
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
//桶排序
void BucketSort(std::vector<int>& arr, int numBuckets) {
// 创建桶
std::vector<std::vector<int>> buckets(numBuckets);
// 将元素分配到桶中
int maxValue = *std::max_element(arr.begin(), arr.end());
for (int i = 0; i < arr.size(); i++) {
int bucketIndex = (arr[i] * numBuckets) / (maxValue + 1);
buckets[bucketIndex].push_back(arr[i]);
}
// 对每个桶中的元素进行排序
for (int i = 0; i < buckets.size(); i++) {
std::sort(buckets[i].begin(), buckets[i].end());
}
// 将排序后的元素从桶中取出
int index = 0;
for (int i = 0; i < buckets.size(); i++) {
for (int j = 0; j < buckets[i].size(); j++) {
arr[index++] = buckets[i][j];
}
}
}
//堆排序（Heap Sort）
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 调整最大堆
void heapify(int arr[], int size, int root) {
int largest = root; // 最大元素的索引
int left = 2 * root + 1; // 左子节点的索引
int right = 2 * root + 2; // 右子节点的索引
// 如果左子节点大于根节点
if (left < size && arr[left] > arr[largest])
largest = left;
// 如果右子节点大于根节点
if (right < size && arr[right] > arr[largest])
largest = right;
// 如果最大元素不是根节点，则交换它与根节点
if (largest != root) {
swap(arr[root], arr[largest]);
// 递归调整子树
heapify(arr, size, largest);
}
}
// 堆排序主函数
void heapSort(int arr[], int size) {
// 构建最大堆（从最后一个非叶子节点开始）
for (int i = size / 2 - 1; i >= 0; i--)
heapify(arr, size, i);
// 从堆顶开始逐个移除最大元素并重新构建堆
for (int i = size - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
//希尔排序（Shell Sort）
void shellSort(int arr[], int size) {
// 计算初始间隔
int gap = size / 2;
while (gap > 0) {
for (int i = gap; i < size; i++) {
int temp = arr[i];
int j = i;
// 对间隔为gap的元素进行插入排序
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
// 缩小间隔
gap /= 2;
}
}
//计数排序（Counting Sort）
void countingSort(int arr[], int size) {
// 找出数组中的最大值
int max = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] > max)
max = arr[i];
}
// 创建计数数组并初始化为0
int countSize = max + 1;
int* count = new int[countSize]();
// 统计每个元素出现的次数
for (int i = 0; i < size; i++) {
count[arr[i]]++;
}
// 根据计数数组重新构建有序序列
int index = 0;
for (int i = 0; i < countSize; i++) {
while (count[i] > 0) {
arr[index++] = i;
count[i]--;
}
}
delete[] count;
}
//基数排序（Radix Sort）
int getMax(int* arr, int size) {
int max = arr[0];
for (int i = 1; i < size; i++) {
if (arr[i] > max)
max = arr[i];
}
return max;
}
// 使用计数排序对数组按照指定位数进行排序
void countingSort(int* arr, int size, int exp) {
const int radix = 10; // 基数为10，表示十进制
int* output = new int[size]; // 存储排序结果的临时数组
int* count = new int[radix](); // 存储每个桶中元素的个数的计数数组
// 统计每个桶中元素的个数
for (int i = 0; i < size; i++) {
int digit = (arr[i] / exp) % radix;
count[digit]++;
}
// 将计数数组进行累加，得到每个桶的结束位置索引
for (int i = 1; i < radix; i++) {
count[i] += count[i - 1];
}
// 从原数组中取出元素放到对应的桶中
for (int i = size - 1; i >= 0; i--) {
int digit = (arr[i] / exp) % radix;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
// 将排序结果复制回原数组
for (int i = 0; i < size; i++) {
arr[i] = output[i];
}
// 释放动态分配的内存
delete[] output;
delete[] count;
}
// 基数排序主函数
void radixSort(int* arr, int size) {
int max = getMax(arr, size); // 获取数组中的最大值
// 对每个位数进行计数排序
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, size, exp);
}
}
// 二分查找
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1; // 目标元素不存在
}
//广度优先搜索（Breadth - First Search）
void BFS(std::vector<std::vector<int>>& graph, int start) {
std::vector<bool> visited(graph.size(), false);
std::queue<int> queue;
visited[start] = true;
queue.push(start);
while (!queue.empty()) {
int current = queue.front();
queue.pop();
std::cout << current << " ";
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}
}
//深度优先搜索（Depth - First Search）
void DFS(std::vector<std::vector<int>>& graph, std::vector<bool>& visited, int current) {
visited[current] = true;
std::cout << current << " ";
for (int neighbor : graph[current]) {
if (!visited[neighbor]) {
DFS(graph, visited, neighbor);
}
}
}
void DFSTraversal(std::vector<std::vector<int>>& graph, int start) {
std::vector<bool> visited(graph.size(), false);
DFS(graph, visited, start);
}
// 打印数组元素
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
// 打印数组元素
void printArray_float(float arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
void functionWithIntArray(const int arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int arr[] = { 5, 2, 8, 1, 9, 3 };
int size = sizeof(arr) / sizeof(arr[0]);
float arr_float[] = { 0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51 };
int size_float = sizeof(arr_float) / sizeof(arr[0]);
std::vector<std::vector<int>> graph = {
{1, 2}, // Node 0 is connected to nodes 1 and 2
{0, 2, 3}, // Node 1 is connected to nodes 0, 2, and 3
{0, 1, 3}, // Node 2 is connected to nodes 0, 1, and 3
{1, 2, 4}, // Node 3 is connected to nodes 1, 2, and 4
{3} // Node 4 is connected to node 3
};
std::cout << "原始数组(float): ";
printArray_float(arr_float, size);
std::cout << "原始数组(int): ";
printArray(arr, size);
// 调用冒泡排序
bubbleSort(arr, size);
std::cout << "冒泡排序后: ";
printArray(arr, size);
// 调用选择排序
selectionSort(arr, size);
std::cout << "选择排序后: ";
printArray(arr, size);
// 调用插入排序
insertionSort(arr, size);
std::cout << "插入排序后: ";
printArray(arr, size);
// 调用快速排序
quickSort(arr, 0, size - 1);
std::cout << "快速排序后: ";
printArray(arr, size);
// 调用归并排序
mergeSort(arr, 0, size - 1);
std::cout << "归并排序后: ";
printArray(arr, size);
//调用桶排序
std::vector<int> arr_vector_int = { 29, 25, 3, 49, 9, 37, 21, 43 };
int numBuckets = 5;
std::cout << "Before sorting: ";
for (int num : arr_vector_int) {
std::cout << num << " ";
}
std::cout << std::endl;
BucketSort(arr_vector_int, numBuckets);
std::cout << "After sorting: ";
for (int num : arr_vector_int) {
std::cout << num << " ";
}
std::cout << std::endl;
//调用堆排序
heapSort(arr, size);
std::cout << "堆排序后 : ";
printArray(arr, size);
//调用希尔排序
shellSort(arr, size);
std::cout << "希尔排序后: ";
printArray(arr, size);
//调用计数排序
countingSort(arr, size);
std::cout << "计数排序后: ";
printArray(arr, size);
//调用基数排序
radixSort(arr, size);
std::cout << "基数排序后: ";
printArray(arr, size);
// 二分查找示例
std::vector<int> arr_vectoor_int = { 1, 3, 5, 7, 9, 11, 13, 15 };
int target = 13;
int result = binarySearch(arr_vectoor_int, target);
if (result != -1)
std::cout << "目标元素 " << target << " 在数组中的索引为 " << result << std::endl;
else
std::cout << "目标元素 " << target << " 不存在于数组中" << std::endl;
//广度优先搜索
std::cout << "BFS traversal starting from node 0: ";
BFS(graph, 0);
//深度优先搜索
std::cout << std::endl << "DFS traversal starting from node 0: ";
DFSTraversal(graph, 0);
return 0;
}
