360网站提交入口地址,wordpress newsletter 插件,电子商务有限公司是干什么的,一个公司做两个网站的多吗1. 排序的稳定性 排序是我们生活中经常会面对的问题#xff0c;小朋友站队的时候会按照从矮到高的顺序排列#xff1b;老师查看上课出勤情况时#xff0c;会按照学生的学号点名#xff1b;高考录取时#xff0c;会按照成绩总分降序依次录取等等。那么对于排序它是如何定义…1. 排序的稳定性 排序是我们生活中经常会面对的问题小朋友站队的时候会按照从矮到高的顺序排列老师查看上课出勤情况时会按照学生的学号点名高考录取时会按照成绩总分降序依次录取等等。那么对于排序它是如何定义的呢 排序是将一批无序的记录数据根据关键字重新排列成有序的记录序列的过程。 在工作和编程过程中我们经常接触的有八种经典的排序算法分别是
冒泡排序冒泡排序在排序过程中通过相邻元素的交换将较大的元素逐步“冒泡”到序列的末尾。在相等元素的情况下冒泡排序不会改变它们的相对顺序因此是稳定的。选择排序选择排序在每一轮选择最小或最大元素并将其与当前未排序部分的首元素交换。在相等元素的情况下这种交换可能会改变它们的相对顺序因此选择排序是不稳定的。插入排序插入排序通过将每个元素插入到已排序部分的正确位置来完成排序。在处理相等元素时新元素总是插入到已有元素之后因此相等元素的相对顺序不会改变插入排序是稳定的。希尔排序希尔排序是插入排序的改进版通过逐步减少增量来排序子序列最后使用增量为1的插入排序。然而在排序过程中元素的位置会发生变化可能会改变相等元素的相对顺序因此希尔排序是不稳定的。快速排序快速排序通过选择一个基准元素将数组分成两部分分别对两部分进行递归排序。在分区过程中相等元素的相对顺序可能会被改变因此快速排序是不稳定的。归并排序归并排序通过将数组分割成两个子数组分别排序后再合并。在合并阶段归并排序会确保相等元素的相对顺序保持不变因此归并排序是稳定的。堆排序堆排序通过构建堆并反复提取堆顶元素来排序。由于在堆构建和排序过程中可能会对相等元素的相对顺序进行重新排列因此堆排序是不稳定的。基数排序基数排序是一种非比较排序方法通过对数字的每一位进行排序来实现整体排序。在每一位的排序过程中基数排序会保持相等元素的相对顺序因此是稳定的。 关于排序还有另一个大家需要掌握的概念就是排序的稳定性。排序的稳定性指的是在排序算法中如果两个元素的键值相等排序后它们的相对顺序是否会保持不变。
如果排序算法是稳定的那么在排序之前和之后相同键值元素的相对顺序是相同的如果排序算法是不稳定的那么相同键值元素的相对顺序可能会发生变化。
在选择排序算法时了解排序的稳定性有助于根据具体需求选择合适的算法。如果稳定性很重要应该选择稳定的排序算法如果稳定性不重要可以选择更高效但不稳定的排序算法。
总结
稳定的排序算法冒泡排序、插入排序、归并排序、基数排序不稳定的排序算法选择排序、希尔排序、快速排序、堆排序
2. 冒泡排序 冒泡排序Bubble Sort是一种简单且直观的排序算法。它通过重复地遍历要排序的列表一次比较两个相邻的元素并交换它们的位置来排序列表。这个过程会一直重复直到列表变得有序为止。由于每次遍历列表时最大的元素会“冒泡”到列表的末端故称为冒泡排序。
关于冒泡排序的详细过程如下按照升序描述
从列表的第一个元素开始依次比较相邻的两个元素。如果前一个元素比后一个元素大则交换它们的位置。继续向后比较直到列表的末尾。这时最大的元素被放置到列表的末尾。重新从列表的第一个元素开始重复上述过程但不再处理已排序的最后一个元素。持续重复步骤 1-4直到没有需要交换的元素表示列表已完成排序。
在下图中为大家展示冒泡排序的整个过程整形数组中有6个元素int array[6] { 6, 5, 4, 3, 2, 1 };对其进行了升序排列 #include iostream
#include vector
using namespace std;// 升序
void bubbleSort(vectorint vec)
{int size vec.size();bool swapped false;for (int i 0; i size - 1; i){swapped false;for (int j 0; j size - i - 1; j){if (vec[j] vec[j 1]){swap(vec[j], vec[j 1]); // 交换swapped true;}}if (!swapped){break; // 提前结束排序}}
}int main()
{srand(time(NULL));vectorint data;cout 排序前的原始数据: ;for (int i 0; i 10; i){data.push_back(rand() % 100);cout data.back() ;}cout endl;bubbleSort(data);cout 排序之后的数据: ;for (const auto item : data){cout item ;}cout endl;return 0;
}
冒泡排序的时间复杂度取决于输入数组的初始状态
最坏情况下每次遍历都需要进行比较和交换操作因此时间复杂度为 O(n2)。最优情况下如果输入数组已经有序只需进行一次遍历时间复杂度为 O(n)。平均情况下每次遍历都需要进行部分比较和交换操作时间复杂度为 O(n2)。
冒泡排序是一种稳定的排序算法。即相等的元素在排序后不会改变相对顺序。原因在于当两个相邻的元素相等时冒泡排序不会交换它们的位置从而保持了相对顺序的稳定性。
3. 选择排序 选择排序Selection Sort是一种简单直观的排序算法。其基本思想是每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。虽然选择排序的时间复杂度较高但其实现简单适用于小规模数据的排序。
关于选择排序的具体步骤如下按照升序描述:
初始状态将整个序列分为已排序区间和未排序区间。初始时已排序区间为空未排序区间为整个序列。选择最小值在未排序区间中找到最小的元素。交换位置将这个最小元素和未排序区间的第一个元素交换位置使其成为已排序区间的最后一个元素。重复步骤重复步骤2和步骤3直到未排序区间为空。
在下图中为大家展示了整个选择排序的过程 #include iostream
#include vector
using namespace std;void selectionSort(vectorint vec)
{int size vec.size();for (int i 0; i size - 1; i){int minPos i; for (int j i 1; j size; j){if (vec[j] vec[minPos]) {minPos j; }}if (minPos ! i){swap(vec[i], vec[minPos]);}}
}int main()
{srand(time(NULL));vectorint data;cout 排序前的原始数据: ;for (int i 0; i 10; i){data.push_back(rand() % 100);cout data.back() ;}cout endl;selectionSort(data);cout 排序之后的数据: ;for (const auto item : data){cout item ;}cout endl;return 0;
}
选择排序的时间复杂度不受输入数据的初始状态影响始终为 O(n2)。具体分析如下
最坏情况下每次选择最小元素都需要遍历未排序部分的所有元素因此时间复杂度为 O(n2)。最优情况下即使输入数据已经有序选择排序仍需遍历所有元素因此时间复杂度依旧为 O(n2)。平均情况下每次选择最小元素的操作与最坏情况类似时间复杂度为 O(n2)。
选择排序是一种不稳定的排序算法。即相等的元素在排序后可能改变相对顺序。原因在于当选择最小元素并进行交换时可能会将相等元素的相对位置改变。例如数组 [5, 3, 5, 2] 经过第一次选择后变为 [2, 3, 5, 5]两个 5 的相对顺序发生了改变。
4. 插入排序 插入排序Insertion Sort是一种简单直观的排序算法。它的基本思想是将未排序部分的元素插入到已排序部分的适当位置从而逐步构建有序列表。插入排序在小规模数据集和部分有序数据集上的表现较好具有稳定性和简单性。
关于插入排序的具体步骤如下按照升序描述:
初始化从第二个元素索引为1开始将其视为待插入元素。默认第一个元素是已经排好序的有序序列。遍历从未排序部分的第一个元素开始逐一将每个元素插入到已排序部分的适当位置。插入操作
将当前元素称为“待插入元素”与已排序部分的元素从后向前进行比较。如果已排序的元素大于待插入元素则将该已排序元素向右移动一位。重复上述比较和移动操作直到找到一个已排序元素小于或等于待插入元素的位置。将待插入元素插入到这个位置。
4.重复步骤2和步骤3直到所有元素都排序完成。
为了便于理解下图为大家展示是插入排序的过程 #include iostream
#include vector
using namespace std;void insertionSort(vectorint vec)
{int size vec.size();for (int i 1; i size; i){int key vec[i];int j i - 1; while (j 0 vec[j] key){vec[j 1] vec[j];j--;}vec[j 1] key;}
}int main()
{srand(time(NULL));vectorint data;cout 排序前的原始数据: ;for (int i 0; i 10; i){data.push_back(rand() % 100);cout data.back() ;}cout endl;insertionSort(data);cout 排序之后的数据: ;for (const auto item : data){cout item ;}cout endl;return 0;
}
插入排序的时间复杂度取决于输入数组的初始状态
最坏情况下数组是反向排序的需要进行最大次数的比较和移动操作时间复杂度为 O(n2)。最优情况下数组已经有序只需进行 n-1 次比较时间复杂度为 O(n)。平均情况下需要进行部分比较和移动操作时间复杂度为 O(n2)。
插入排序是一种稳定的排序算法。即相等的元素在排序后不会改变相对顺序。原因在于当插入相等的元素时只需插入到相等元素之后即可不会改变其相对位置。
5. 希尔排序 希尔排序Shell Sort是插入排序的一种改进版本旨在提高插入排序在大规模数据集上的效率。它通过将数据集分割成多个子序列分别进行插入排序逐步减少子序列的间隔最终在整个序列上进行插入排序从而减少数据移动的次数提升排序效率。
关于希尔排序的具体步骤如下按照升序描述:
选择间隔序列选择一个逐步减小的间隔序列 h例如n/2, n/4, ..., 1直到 h1。最常见的间隔序列是希尔原始提出的 h h / 2。对每个间隔执行插入排序 对于每个间隔 h将数组分成若干个子数组每个子数组中的元素之间的间隔为 h。对这些子数组应用插入排序使得所有的元素在当前间隔 h 下部分有序。最终的插入排序 当间隔减小到 1 时整个数组基本有序此时的插入排序效率更高。
下图为大家展示的是希尔排序的过程 #include iostream
using namespace std;// 希尔排序函数
void shellSort(int arr[], int n) {// 选择间隔序列初始间隔为 n/2for (int gap n / 2; gap 0; gap / 2) {// 对每个间隔进行插入排序for (int i gap; i n; i) {int temp arr[i];int j i;// 将当前元素插入到已排序的部分while (j gap arr[j - gap] temp) {arr[j] arr[j - gap];j - gap;}arr[j] temp;}}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}int main() {int arr[] {12, 34, 54, 2, 3};int n sizeof(arr) / sizeof(arr[0]);shellSort(arr, n);cout Sorted array: ;printArray(arr, n);return 0;
}
希尔排序的时间复杂度依赖于间隔序列的选择
最坏情况下时间复杂度O(n2)。最优情况下时间复杂度为 O(n)。平均情况下时间复杂 O(n1.3)。
希尔排序是一种不稳定的排序算法。即相等的元素在排序后可能改变相对顺序。原因在于当使用较大间隔进行交换时相等元素的相对顺序可能会被打乱。
6.快速排序
快速排序是一种高效的排序算法采用分治策略来排序数组。它通过选择一个“基准”元素将数组分成两个子数组分别对这两个子数组进行递归排序从而实现整体排序。快速排序在大多数情况下具有良好的性能是实际应用中常用的排序算法。
关于快速排序的具体步骤如下按照升序描述
选择基准从数组中选择一个基准元素通常选择第一个元素、最后一个元素、或中间元素。基准元素的选择方法可以影响排序的效率。分区操作 遍历数组将比基准元素小的元素移到基准元素的左边比基准元素大的元素移到右边。分区完成后基准元素位于其最终位置。递归排序 对基准元素左边的子数组和右边的子数组分别递归调用快速排序。终止条件当子数组的大小小于等于1时递归结束数组已排序完成。
为了便于理解下图描述了快速排序的全过程 #include iostream
using namespace std;// 分区操作函数选择基准元素并对数组进行分区
int partition(int arr[], int low, int high) {int pivot arr[high]; // 选择最后一个元素作为基准int i low - 1; // i 是已排序部分的最后一个元素的索引// 遍历未排序部分将小于基准的元素移到左边for (int j low; j high; j) {if (arr[j] pivot) { // 如果当前元素小于等于基准i; // 增加已排序部分的元素计数swap(arr[i], arr[j]); // 交换元素将小于基准的元素移到左边}}// 将基准元素放到正确的位置swap(arr[i 1], arr[high]);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);}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}int main() {int arr[] {10, 7, 8, 9, 1, 5};int n sizeof(arr) / sizeof(arr[0]);quickSort(arr, 0, n - 1); // 调用快速排序函数cout Sorted array: ;printArray(arr, n); // 打印排序后的数组return 0;
}
快速排序的时间复杂度受基准选择的影响
最坏情况下如果每次选择的基准都是当前数组中的最小或最大值则每次只能将一个元素放在正确的位置时间复杂度为 O(n2)。这种情况在数组已经有序或逆序时可能出现。最优情况下每次选择的基准都能将数组平分时间复杂度为 O(n log n)。平均情况下在多数情况下快速排序的时间复杂度为 O(n log n)。
快速排序是一种不稳定的排序算法。即相等的元素在排序后可能改变相对顺序。原因在于分区操作中可能会交换相等的元素从而改变它们的相对位置。
7.归并排序 归并排序Merge Sort是一种基于分治法的高效排序算法。它的基本思想是将数组分成两个子数组分别进行排序然后合并这两个有序子数组。归并排序的时间复杂度为 O(n log n)且具有稳定性因此在实际应用中广泛使用。
关于归并排序的具体步骤如下按照升序描述:
分割数组
如果数组的长度大于1将数组从中间分割成两部分。对每一部分再递归进行分割直到每个子数组的长度为1。
合并排序
合并两个有序的子数组成一个有序的数组。具体做法是比较两个子数组的第一个元素将较小的元素放入合并结果中并移到下一个元素重复这个过程直到一个子数组为空然后将另一个子数组剩下的元素全部放入合并结果中。
递归合并
对每个子数组重复上述步骤直到所有子数组合并为一个完整的有序数组。
为了便于理解下图展示了归并排序的过程 #include iostream
using namespace std;// 合并两个已排序的子数组的函数
void merge(int arr[], int left, int mid, int right) {int n1 mid - left 1; // 左子数组的大小int n2 right - mid; // 右子数组的大小// 创建临时数组int* L new int[n1];int* R new int[n2];// 复制数据到临时数组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];// 合并临时数组int i 0, j 0, k left;while (i n1 j n2) {if (L[i] R[j]) {arr[k] L[i];} else {arr[k] R[j];}}// 复制剩余的元素while (i n1) {arr[k] L[i];}while (j n2) {arr[k] R[j];}// 释放临时数组的内存delete[] L;delete[] R;
}// 归并排序函数
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 printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}int main() {int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr) / sizeof(arr[0]);mergeSort(arr, 0, n - 1); // 调用归并排序函数cout Sorted array: ;printArray(arr, n); // 打印排序后的数组return 0;
}归并排序的时间复杂度可以通过递归方程来分析
最坏情况下归并排序的时间复杂度为 O(n log n)因为每次分割数组的操作都是对半分递归深度为 log n每层的合并操作时间复杂度为 O(n)。最优情况下时间复杂度同样为 O(n log n)因为归并排序的过程与数组的初始顺序无关始终需要进行分割和合并操作。平均情况下归并排序的时间复杂度也是 O(n log n)因为它在任何情况下都需要进行相同数量的分割和合并操作。
8. 堆排序 堆排序Heap Sort是一种基于二叉堆数据结构的比较排序算法。堆排序利用堆这种数据结构的性质来实现排序分为构建初始堆和反复从堆中取出最大元素对于升序排序两个主要步骤。堆排序的时间复杂度为 O(n log n)且不需要额外的内存空间因此在实际应用中非常有效。
在进行堆排序的时候使用的二叉堆有两种分别是最大堆和最小堆它们有以下特性需要大家掌握
最大堆Max Heap对于每个节点 i其父节点 parent(i) 的值都不小于节点 i 的值。换句话说堆中任意节点的值都大于或等于其子节点的值。最小堆Min Heap对于每个节点 i其父节点 parent(i) 的值都不大于节点 i 的值。也就是说堆中任意节点的值都小于或等于其子节点的值。
关于堆排序的具体步骤如下按照升序描述:
堆化Heapify操作
最大堆的堆化操作的目的是在子树中选择一个最大元素并让父节点的值大于或等于其子节点的值。具体步骤如下
初始化最大值假设当前节点 i 是最大值。比较左子节点如果左子节点存在且其值大于当前节点的值将左子节点的值更新为最大值。比较右子节点如果右子节点存在且其值大于当前最大值将右子节点的值更新为最大值。交换值并递归如果最大值不是当前节点将当前节点与最大值节点交换位置并对新的子树进行堆化。
构建最大堆
步骤 1从最后一个非叶子节点开始我们需要找到数组中最后一个非叶子节点的位置。对于一个长度为 n 的数组最后一个非叶子节点的位置是 n/2 - 1向下取整。步骤 2自下而上调整从最后一个非叶子节点开始向前遍历整个数组对每个节点进行堆化操作确保该节点及其子树满足最大堆的性质。
堆排序过程
交换根节点与最后一个节点将堆顶元素即最大元素与堆的最后一个元素交换位置这样最大元素就被移到数组末尾。缩小堆的范围将堆的有效范围缩小忽略末尾已排序的部分对新的根节点进行堆化重新调整成最大堆。重复以上步骤重复交换和堆化过程直到堆的有效范围缩小到1。
#include iostream
using namespace std;// 堆化函数维护最大堆性质
void heapify(int 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) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}// 堆排序函数
void heapSort(int arr[], int n) {// 构建最大堆for (int i n / 2 - 1; i 0; --i)heapify(arr, n, i);// 从堆中提取元素并进行排序for (int i n - 1; i 0; --i) {// 将堆顶元素最大值交换到数组的末尾swap(arr[0], arr[i]);// 维护堆的性质heapify(arr, i, 0);}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i 0; i size; i) {cout arr[i] ;}cout endl;
}int main() {int arr[] {12, 11, 13, 5, 6, 7};int n sizeof(arr) / sizeof(arr[0]);heapSort(arr, n); // 调用堆排序函数cout Sorted array: ;printArray(arr, n); // 打印排序后的数组return 0;
}堆排序的时间复杂度可以通过以下分析得出
最坏情况下构建最大堆的时间复杂度为 O(n)每次调整堆的时间复杂度为 O(log n)因此总时间复杂度为 O(n log n)。最优情况下时间复杂度同样为 O(n log n)因为无论数组初始状态如何都需要进行构建堆和调整堆的操作。平均情况下堆排序的时间复杂度也是 O(n log n)与数组初始状态无关。
堆排序是一种不稳定的排序算法。即相等的元素在排序后可能改变相对顺序。原因在于堆的调整过程中可能会交换相等元素的位置从而改变它们的相对顺序。
9. 基数排序
基数排序Radix Sort是一种非比较排序算法通过逐位处理数字来排序数组。它利用桶排序的思想对数字的每一位进行排序从最低有效位到最高有效位。基数排序特别适用于处理大量的整数或字符串数据。其时间复杂度为 O(d*(nk))其中 d 是数字的位数n 是数组的长度k 是基数【使用十进制基数 ( k 10 )】。
关于基数排序的具体步骤如下按照升序描述: 确定最大位数 找到数组中最大数字的位数。 按位排序 从最低位到最高位进行排序每次按当前位的值将数字分配到桶中并使用稳定的排序算法如计数排序对这些桶中的数字进行排序。 合并桶 根据每位的排序结果将所有桶中的数字按顺序重新合并到数组中。
#include iostream
#include vector
#include algorithm
using namespace std;// 使用计数排序对数组的特定位进行排序
void countSort(vectorint arr, int exp) {int n arr.size();vectorint output(n); // 输出数组vectorint count(10, 0); // 计数数组// 计算每个数字在当前位的出现次数for (int i 0; i n; i)count[(arr[i] / exp) % 10];// 计算计数数组中每个元素的累计值for (int i 1; i 10; i)count[i] count[i - 1];// 从后往前遍历输入数组按当前位的值填充输出数组for (int i n - 1; i 0; --i) {output[count[(arr[i] / exp) % 10] - 1] arr[i];count[(arr[i] / exp) % 10]--;}// 将排序后的结果复制回原数组for (int i 0; i n; i)arr[i] output[i];
}// 基数排序函数
void radixSort(vectorint arr) {int maxVal *max_element(arr.begin(), arr.end()); // 找到最大值for (int exp 1; maxVal / exp 0; exp * 10) {countSort(arr, exp); // 按当前位进行计数排序}
}// 打印数组的函数
void printArray(const vectorint arr) {for (int num : arr) {cout num ;}cout endl;
}int main() {vectorint arr {170, 45, 75, 90, 802, 24, 2, 66};radixSort(arr); // 调用基数排序函数cout Sorted array: ;printArray(arr); // 打印排序后的数组return 0;
}基数排序的时间复杂度可以通过以下分析得出
最坏情况下时间复杂度为 O(d*(nk))其中 d 是最大数的位数n 是数组的大小k 是基数。最优情况下时间复杂度同样为 O(d*(nk))因为无论数组初始状态如何都需要对每一位进行排序。平均情况下基数排序的时间复杂度也是 O(d*(nk))。
10. 总结
对于以上讲解的八种排序算法最后我们把它们的空间复杂度和时间复杂度全部罗列出来做一个对比
