宝安网站建设推广,建设网站的教程,集团公司网站建设方案,免费搭建博客网站算法
定义#xff1a;算法是解决特定问题的明确步骤集合。算法的效率通常用时间复杂度和空间复杂度来衡量。
排序算法
定义#xff1a;排序算法是计算机科学中用于对元素序列进行排序的一系列算法。排序算法在各种应用中都非常常见#xff0c;从简单的数据处理到复杂的数…算法
定义算法是解决特定问题的明确步骤集合。算法的效率通常用时间复杂度和空间复杂度来衡量。
排序算法
定义排序算法是计算机科学中用于对元素序列进行排序的一系列算法。排序算法在各种应用中都非常常见从简单的数据处理到复杂的数据库和搜索引擎优化。分类冒泡排序Bubble Sort、选择排序Selection Sort、插入排序Insertion Sort、归并排序Merge Sort、快速排序Quick Sort、堆排序Heap Sort、希尔排序Shell Sort、计数排序Counting Sort、桶排序Bucket Sort、基数排序Radix Sort等等。
冒泡排序 Bubble Sort
定义冒泡排序Bubble Sort是一种简单的排序算法它通过重复遍历要排序的数列比较每对相邻元素并在顺序错误的情况下交换它们。这个过程会重复进行直到没有再需要交换的元素为止这意味着数列已经排序完成。冒泡排序的名字来源于较小的元素会逐渐“冒泡”到数列的顶端开始位置。步骤 比较相邻的元素从数列的开始位置比较每对相邻元素如果第一个比第二个大则交换它们的位置。遍历数列继续比较下一对相邻元素直到到达数列的末尾。重复遍历重复上述步骤但每次遍历都从上一次遍历停止的位置开始因为最后的元素已经是最大的不需要再比较。优化在每次遍历中如果一次完整的遍历都没有发生交换说明数列已经排序完成可以提前结束排序。 复杂度 时间复杂度冒泡排序的平均和最坏情况时间复杂度都是 (O(n^2))其中 (n) 是数列的长度。这是因为算法需要进行多次遍历和比较。空间复杂度冒泡排序的空间复杂度是 (O(1))因为它只需要一个额外的空间来存储交换的元素。 示例
#include iostream
#include vector
#include algorithm // 用于std::swap// 冒泡排序函数
void bubbleSort(std::vectorint arr) {int n arr.size();bool swapped;for (int i 0; i n - 1; i) {swapped false;for (int j 0; j n - i - 1; j) {if (arr[j] arr[j 1]) {// 使用std::swap交换两个元素std::swap(arr[j], arr[j 1]);swapped true;}}// 如果在这一轮排序中没有发生交换说明数组已经有序可以提前结束if (!swapped) {break;}}
}// 打印数组的函数
void printArray(const std::vectorint arr) {for (int num : arr) {std::cout num ;}std::cout std::endl;
}// 主函数
int main() {std::vectorint arr {64, 34, 25, 12, 22, 11, 90};std::cout Original array:\n;printArray(arr);bubbleSort(arr);std::cout Sorted array:\n;printArray(arr);return 0;
}快速排序 Quick Sort
定义由英国计算机科学家托尼·霍尔Tony Hoare在1960年提出。它的基本思想是分治法Divide and Conquer通过一个称为“基准”pivot的元素将数组分成两个子数组使得左边子数组的所有元素都比基准小右边子数组的所有元素都比基准大然后递归地对这两个子数组进行快速排序。基本步骤 选择基准从数组中选择一个元素作为基准pivot。选择基准的方法可以有多种例如选择第一个元素、最后一个元素、中间元素或者随机选择一个元素。分区操作Partitioning重新排列数组使得所有比基准小的元素都在基准的左边所有比基准大的元素都在基准的右边。这个过程结束后基准元素就处于其最终位置。递归排序递归地对基准左边和右边的子数组进行快速排序。返回当子数组的大小减少到1或0时递归结束整个数组变为有序。 复杂度平均时间复杂度为 O(nlogn)但在最坏情况下例如数组已经是有序的或者所有元素都相等时间复杂度会退化到 O(n^2)。示例
#include iostream
#include vector// 交换两个元素
void swap(int* a, int* b) {int t *a;*a *b;*b t;
}// 选择基准并进行分区
int partition(std::vectorint 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; // 增加小于基准元素的索引swap(arr[i], arr[j]);}}swap(arr[i 1], arr[high]);return (i 1);
}// 快速排序函数
void quickSort(std::vectorint arr, int low, int high) {if (low high) {// pi 是分区后的基准索引可以直接选择 lowhigh/2 位置作为分区索引int pi partition(arr, low, high);// 分别对基准左边和右边的子数组进行快速排序quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}
}// 打印数组
void printArray(const std::vectorint arr) {for (int num : arr) {std::cout num ;}std::cout std::endl;
}// 主函数
int main() {std::vectorint arr {10, 7, 8, 9, 1, 5};int n arr.size();std::cout Original array: ;printArray(arr);quickSort(arr, 0, n - 1);std::cout Sorted array: ;printArray(arr);return 0;
}选择排序 Selection Sort
定义是一种简单直观的排序算法。它的工作原理是首先在未排序的元素中找到最小或最大的元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小或最大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。基本步骤 从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置。从剩余未排序元素中寻找最小或最大元素然后放到已排序序列的末尾。重复第二步直到所有元素均排序完毕。 示例
#include iostream
#include vector
#include algorithm // For std::swap()void selectionSort(std::vectorint arr) {int n arr.size();for (int i 0; i n - 1; i) {// 找到从i到数组末尾部分的最小元素的索引int min_idx i;for (int j i 1; j n; j) {if (arr[j] arr[min_idx]) {min_idx j;}}// 交换当前位置i和找到的最小元素的位置std::swap(arr[i], arr[min_idx]);}
}int main() {std::vectorint arr {64, 25, 12, 22, 11};selectionSort(arr);std::cout Sorted array: ;for (int num : arr) {std::cout num ;}std::cout std::endl;return 0;
}插入排序 Insertion Sort
定义是一种简单直观的排序算法它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。插入排序在实现上通常采用in-place排序即只需用到O(1)的额外空间的排序因而在从后向前扫描过程中需要反复把已排序元素逐步向后挪位为新元素提供插入空间。基本步骤 从第一个元素开始该元素可以认为已经被排序。取出下一个元素在已经排序的元素序列中从后向前扫描。如果该元素已排序小于新元素将该元素移到下一位置。重复步骤3直到找到已排序元素小于或者等于新元素的位置。将新元素插入到该位置后。重复步骤2~5。 复杂度时间复杂度是O(n2)在小规模数据或基本有序的数据中插入排序可以表现得非常好因为它的最好情况和平均情况时间复杂度分别为O(n)和O(n2)。此外插入排序是稳定的排序算法这意味着相等的元素之间的相对顺序不会改变。示例
#include iostream
#include vectorvoid insertionSort(std::vectorint arr) {int n arr.size();for (int i 1; i n; i) {int key arr[i];int j i - 1;// 将比key大的元素向后移动一位while (j 0 arr[j] key) {arr[j 1] arr[j];j j - 1;}// 将key插入到正确的位置arr[j 1] key;}
}
/* 推算
n 5
第一次循环
for(i1; i5; i)
{keyarr[i]arr[1]5ji-1 1-1 0while(00 95){arr[j1]arr[1]a[0]9j j-1 -1}arr[j1] arr[0] key 5
}
第二次循环
for(i2; i5; i)
{key arr[i] arr[2] 1j i-1 2-1 1//第一次whilewhile(10 arr[1]1){arr[j1]arr[2] arr[1] 9j j-10}//第二次whilewhile(00 arr[0] 1){arr[1] arr[0] 5j j-1 -1}arr[j1] arr[0] key 1
}
...以此类推...*/int main() {std::vectorint arr {9, 5, 1, 4, 3};insertionSort(arr);std::cout Sorted array: ;for (int num : arr) {std::cout num ;}std::cout std::endl;return 0;
}归并排序 Merge Sort
定义是一种分治算法其基本思想是将两个已经排序的序列合并成一个排序的序列。归并排序的效率很高对于大数据集来说归并排序通常比插入排序和选择排序更快。归并排序是稳定的排序算法这意味着相等的元素之间的相对顺序不会改变。基本步骤 将当前序列分成两个等长的部分。对两个部分分别进行归并排序。将两个已排序的部分合并成一个排序的序列。 复杂度归并排序的时间复杂度是O(n log n)其中n是数组的长度。由于归并排序需要额外的存储空间来存储临时数组因此它的空间复杂度是O(n)。示例
#include iostream
#include vector// 合并两个子序列的函数
void merge(std::vectorint arr, int left, int mid, int right) {int n1 mid - left 1; // 左子序列的长度int n2 right - mid; // 右子序列的长度// 创建临时数组std::vectorint L(n1), R(n2);// 拷贝数据到临时数组 L[] 和 R[]for (int i 0; i n1; i)L[i] arr[left i];for (int j 0; j n2; j)R[j] arr[mid 1 j];// 合并临时数组回到 arr[left..right]int i 0; // 初始索引第一个子数组int j 0; // 初始索引第二个子数组int k left; // 初始索引合并的子数组while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];i;} else {arr[k] R[j];j;}k;}// 拷贝 L[] 的剩余元素while (i n1) {arr[k] L[i];i;k;}// 拷贝 R[] 的剩余元素while (j n2) {arr[k] R[j];j;k;}
}// l 是数组的左边界r 是右边界
void mergeSort(std::vectorint arr, int left, int right) {if (left right) {// 同 [left, mid] 和 [mid1, right] 两个子序列int mid left (right - left) / 2;// 分别对两个子序列进行归并排序mergeSort(arr, left, mid);mergeSort(arr, mid 1, right);// 合并两个子序列merge(arr, left, mid, right);}
}int main() {std::vectorint arr {12, 11, 13, 5, 6};int arr_size arr.size();mergeSort(arr, 0, arr_size - 1);std::cout Sorted array: ;for (int i 0; i arr_size; i) {std::cout arr[i] ;}std::cout std::endl;return 0;
}堆排序 Heap Sort
定义是一种基于比较的排序算法使用二叉堆数据结构。堆排序分为两个阶段建立堆Build Max Heap和排序Heapsort。堆是一个满足以下性质的完全二叉树对于最大的堆大顶堆父节点的键值总是大于或等于其子节点的键值对于最小的堆小顶堆父节点的键值总是小于或等于其子节点的键值。基本步骤 建立最大堆将无序序列构建成一个最大堆即每个父节点的值都大于或等于其子节点的值。排序交换堆顶元素当前最大值和数组末尾元素然后对堆进行调整堆化使其满足最大堆的性质。重复这个过程直到数组完全有序。 复杂度堆排序的时间复杂度是O(n log n)其中n是数组的长度。堆排序是原地排序不需要额外的存储空间因此空间复杂度是O(1)。示例
#include iostream
#include vector
#include algorithm // For std::swap()// 调整堆保持最大堆性质
void heapify(std::vectorint arr, int n, int i) {int largest i; // 初始化最大元素为根int left 2 * i 1; // 左子节点int right 2 * i 2; // 右子节点// 如果左子节点比根大则更新最大元素if (left n arr[left] arr[largest])largest left;// 如果右子节点比最大元素大则更新最大元素if (right n arr[right] arr[largest])largest right;// 如果最大元素不是根交换它们并继续调整堆if (largest ! i) {std::swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}// 堆排序
void heapSort(std::vectorint arr) {int n arr.size();// 构建最大堆for (int i n / 2 - 1; i 0; i--)heapify(arr, n, i);// 一个个从堆顶取出元素for (int i n - 1; i 0; i--) {// 将当前最大元素堆顶与末尾元素交换std::swap(arr[0], arr[i]);// 调整堆heapify(arr, i, 0);}
}int main() {std::vectorint arr {12, 11, 13, 5, 6};heapSort(arr);std::cout Sorted array: ;for (int num : arr) {std::cout num ;}std::cout std::endl;return 0;
}希尔排序 Shell Sort
定义是插入排序的一种优化版本也称为缩小增量排序。它的基本思想是将原始数据分成若干子序列这些子序列中的元素之间存在一定的间隔称为增量对每个子序列分别进行插入排序。随着增量逐渐减小整个序列最终变为有序序列。基本步骤 选择一个增量序列增量序列的选择对算法的性能有很大影响。常见的增量序列有原始长度的一半、原始长度除以某个常数等。对子序列进行插入排序以增量为间隔将原始序列分割成多个子序列并对每个子序列进行插入排序。减小增量减小增量的值重复步骤2直到增量为1此时对整个序列进行插入排序。 复杂度时间复杂度在平均情况下是O(n log n)但在最坏情况下是O(n^2)。希尔排序是不稳定的排序算法.示例:
#include iostream
#include vector
#include algorithm // For std::swap()// 希尔排序
void shellSort(std::vectorint arr) {int n arr.size();// 增量序列可以自定义增量序列std::vectorint gaps {1, 4, 10, 23, 57, 132, 316};// 也可以使用动态计算增量序列例如gaps[i] n/2^ifor (int gap : gaps) {for (int i gap; i n; i) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}
}int main() {std::vectorint arr {12, 11, 13, 5, 6, 7, 2, 3, 4, 1};shellSort(arr);std::cout Sorted array: ;for (int num : arr) {std::cout num ;}std::cout std::endl;return 0;
}计数排序 Counting Sort
定义是一种非比较型排序算法适用于一定范围内的整数排序。它的基本思想是使用一个额外的数组来统计每个值的出现次数然后根据这些计数来确定每个元素在排序后数组中的位置。基本步骤 找出待排序数组中的最大值和最小值确定排序的范围。创建计数数组初始化计数数组长度为最大值和最小值之差再加1。填充计数数组遍历待排序数组对于每个元素增加计数数组中对应位置的计数。调整计数数组将计数数组中的每个值调整为累积计数这将给出每个元素在排序后数组中的位置。构建排序数组根据调整后的计数数组构建排序后的数组。 复杂度计数排序的时间复杂度是O(n k)其中n是数组的长度k是数值的范围。计数排序是稳定的排序算法并且由于它不需要比较所以在处理大量数据且数值范围不大时非常高效。然而当数值范围非常大时计数排序可能会消耗大量内存示例:
#include iostream
#include vector
#include algorithm
#include climits// 计数排序
void countingSort(std::vectorint arr) {int n arr.size();int maxVal *std::max_element(arr.begin(), arr.end());int minVal *std::min_element(arr.begin(), arr.end());// 计数数组的大小int range maxVal - minVal 1;std::vectorint count(range, 0);// 填充计数数组for (int num : arr) {count[num - minVal];}// 调整计数数组为累积计数for (int i 1; i count.size(); i) {count[i] count[i - 1];}// 构建排序数组std::vectorint sortedArr(n);for (int num : arr) {sortedArr[count[num - minVal] - 1] num;count[num - minVal]--;}// 将排序后的数组复制回原数组for (int i 0; i n; i) {arr[i] sortedArr[i];}
}int main() {std::vectorint arr {4, 2, 2, 8, 3, 3, 1};countingSort(arr);std::cout Sorted array: ;for (int num : arr) {std::cout num ;}std::cout std::endl;return 0;
}桶排序 Bucket Sort
定义是一种分布式排序算法其基本思想是将数组分为多个“桶”每个桶负责排序数组中的一部分数据。桶排序通常用于数据服从均匀分布的情况它通过将数据分散到有限数量的桶里每个桶内使用其他排序算法如插入排序进行排序最后按顺序合并各个桶中的数据以得到有序的序列。基本步骤 确定桶的数量根据数据的范围和数据个数确定桶的数量。分配数据到桶遍历待排序数组将每个数据分配到对应的桶中。对每个桶内的数据进行排序通常使用插入排序或其他排序算法对桶内数据进行排序。合并桶中的数据按顺序合并各个桶中的数据得到最终的有序序列。 复杂度时间复杂度取决于桶的数量和使用的排序算法平均情况下是O(nk)其中n是数组的长度k是桶的数量。桶排序是稳定的排序算法并且由于它不需要比较所以在处理大量数据且数值范围不大时非常高效。然而桶排序的性能依赖于数据的分布如果数据分布不均匀性能可能会下降.示例:
#include iostream
#include vector
#include algorithmvoid bucketSort(std::vectorint arr) {if (arr.empty()) {return;}// 找出最大值和最小值int maxVal *std::max_element(arr.begin(), arr.end());int minVal *std::min_element(arr.begin(), arr.end());// 计算桶的数量int bucketCount (maxVal - minVal) / (arr.size() 1) 1;// 创建桶std::vectorstd::vectorint buckets(bucketCount);// 分配数据到桶for (int num : arr) {int index (num - minVal) / (arr.size() 1);buckets[index].push_back(num);}// 对每个桶内的数据进行排序int idx 0; // 用于结果数组的索引for (auto bucket : buckets) {std::sort(bucket.begin(), bucket.end()); // 对每个桶进行排序for (int num : bucket) {arr[idx] num;}}
}int main() {std::vectorint arr {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};bucketSort(arr);std::cout Sorted array: ;for (int num : arr) {std::cout num ;}std::cout std::endl;return 0;
}基数排序 Radix Sort
定义是一种非比较型整数排序算法其基本思想是将整数按位数切割成不同的数字然后按每个位数分别比较。排序过程从最低位开始依次对每一位进行排序直到最高位排序完成。基本步骤 找到最大数确定数组中的最大数以确定最大位数。按位排序从最低位到最高位对每一位进行排序。使用稳定的排序算法通常使用计数排序或桶排序来对每一位进行排序。合并结果经过每一位的排序后整个数组变为有序。 复杂度时间复杂度是O(nk)其中n是数组的长度k是数值的最大位数。基数排序是稳定的排序算法并且由于它不需要比较所以在处理大量数据且数值范围不大时非常高效。基数排序适用于整数排序对于非整数数据需要进行适当的转换。示例:
#include iostream
#include vector
#include algorithm
#include climits// 计数排序辅助函数对特定位数进行排序
void countSort(std::vectorint arr, int exp) {const int kMax 10; // 0-9std::vectorint output(arr.size());std::vectorint count(kMax, 0);// 统计每个数字的出现次数for (int i 0; i arr.size(); i) {int index (arr[i] / exp) % kMax;count[index];}// 计算累积出现次数for (int i 1; i kMax; i) {count[i] count[i - 1];}// 填充输出数组for (int i arr.size() - 1; i 0; --i) {int index (arr[i] / exp) % kMax;output[count[index] - 1] arr[i];count[index]--;}// 将输出数组复制回原数组for (int i 0; i arr.size(); i) {arr[i] output[i];}
}// 基数排序
void radixSort(std::vectorint arr) {// 找到最大数确定最大位数int maxVal *std::max_element(arr.begin(), arr.end());int exp 1; // 从最低位开始while (maxVal / exp 0) {countSort(arr, exp); // 对每一位进行排序exp * 10; // 移动到下一位}
}int main() {std::vectorint arr {170, 45, 75, 90, 802, 24, 2, 66};radixSort(arr);std::cout Sorted array: ;for (int num : arr) {std::cout num ;}std::cout std::endl;return 0;
}
