婴儿衣服做的网站好,链接买卖是什么意思,常德网站网站建设,郑州网站制作工具一、直接插入排序 (Insertion Sort)
基本思想
直接插入排序是一种简单直观的排序算法#xff0c;就像我们打扑克牌时的操作#xff1a;每次摸到一张牌#xff0c;都会把它插入到手中已排好序的牌的正确位置。通过这种方式#xff0c;逐步构建一个有序序列。
步骤 从第一…一、直接插入排序 (Insertion Sort)
基本思想
直接插入排序是一种简单直观的排序算法就像我们打扑克牌时的操作每次摸到一张牌都会把它插入到手中已排好序的牌的正确位置。通过这种方式逐步构建一个有序序列。
步骤 从第一个元素开始该元素可以认为已经被排序。 取出下一个元素在已经排序的元素序列中从后向前扫描。 如果该元素已排序大于新元素将该元素移到下一位置。 重复步骤3直到找到已排序的元素小于或等于新元素的位置。 将新元素插入到该位置后。 重复步骤2~5直到所有元素都被排序。
C语言代码示例
void InsertSort(int* a, int n) {for (int i 1; i n; i) { // 从第二个元素开始int temp a[i]; // 当前要插入的元素int j i - 1; // 从已排序部分的最后一个元素开始比较while (j 0 a[j] temp) {a[j 1] a[j]; // 如果当前元素大于新元素向后移动j--;}a[j 1] temp; // 找到插入位置后插入新元素}
}
算法分析 时间复杂度 最好情况已排好序O(n)每个元素只需比较一次。 平均情况和最坏情况逆序O(n²)。 空间复杂度O(1)只需要一个临时变量。 稳定性稳定。相等元素的相对位置不会改变。 适用场景适用于小型数据集或基本有序的数据集效率较高。 二、冒泡排序 (Bubble Sort)
基本思想
冒泡排序是一种简单但效率较低的排序算法。它的名字来源于其工作方式通过重复遍历待排序的数列比较相邻的两个元素如果顺序错误就交换它们。每次遍历后最大的元素会像气泡一样“浮”到数列的末尾。
步骤 比较相邻的元素。如果第一个比第二个大就交换它们。 对每一对相邻元素做同样的操作从第一个元素到最后一个元素。经过这一轮后最大的元素会移动到数列的末尾。 重复上述步骤但每次减少比较的范围因为最后的元素已经排好序。 继续重复直到整个数列有序。
C语言代码示例
void bubbleSort(int arr[], int n) {for (int i 0; i n - 1; i) { // 遍历 n-1 次for (int j 0; j n - i - 1; j) { // 每次减少比较范围if (arr[j] arr[j 1]) { // 如果顺序错误交换int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}
}
算法分析 时间复杂度 最好情况已排好序O(n)因为只需要遍历一次。 平均情况和最坏情况逆序O(n²)。 空间复杂度O(1)只需要一个临时变量。 稳定性稳定。相等元素的相对位置不会改变。 适用场景由于效率较低通常只用于教学示例不适合实际应用。 三、希尔排序 (Shell Sort)
基本思想
希尔排序是插入排序的一种改进版本通过引入“增量”来分组排序减少数据的移动次数。它将待排序的元素分成若干组每组内的元素间距为某个增量然后对每组进行插入排序。随着增量逐渐减小最终增量为1时整个序列基本有序此时再进行一次直接插入排序即可完成。
步骤 选择一个增量序列例如 [n/2, n/4, ..., 1]。 按增量序列的个数进行多趟排序。 每趟排序中根据当前增量将序列分成若干子序列对每个子序列进行插入排序。 增量逐步减小直到增量为1完成排序。
C语言代码示例
void shellSort(int arr[], int n) {for (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;}}
}
算法分析 时间复杂度 最好情况O(n log n)。 平均情况取决于增量序列通常在 O(n log² n) 到 O(n^(3/2)) 之间。 最坏情况O(n²)。 空间复杂度O(1)。 稳定性不稳定。由于分组排序可能会破坏元素的相对顺序。 适用场景适用于中等规模的数据集性能优于简单排序算法。 四、选择排序 (Selection Sort)
基本思想
选择排序是一种简单直观的排序算法。它的核心思想是每次从未排序的部分中找到最小或最大的元素放到已排序部分的末尾。通过逐步缩小未排序部分的范围最终完成排序。
步骤 在未排序的序列中找到最小元素。 将最小元素与未排序部分的第一个元素交换。 将已排序部分的边界向后移动一位。 重复上述步骤直到所有元素都被排序。
C语言代码示例
void selectionSort(int arr[], int n) {for (int i 0; i n - 1; i) { // 遍历 n-1 次int min_idx i; // 假设当前元素为最小值for (int j i 1; j n; j) { // 找到未排序部分的最小值if (arr[j] arr[min_idx]) {min_idx j;}}// 交换最小值与当前元素int temp arr[min_idx];arr[min_idx] arr[i];arr[i] temp;}
}
算法分析 时间复杂度 最好、平均和最坏情况O(n²)。 空间复杂度O(1)。 稳定性不稳定。交换操作可能会破坏相等元素的相对顺序。 适用场景实现简单适合小型数据集或教学示例。 五、堆排序 (Heap Sort)
基本思想
堆排序是一种基于堆数据结构的排序算法。堆是一种特殊的完全二叉树分为大顶堆和小顶堆。堆排序利用堆的性质快速找到最大或最小元素并逐步构建有序序列。
步骤 将待排序的序列构建成一个大顶堆升序排序或小顶堆降序排序。 将堆顶元素最大值或最小值与末尾元素交换。 将剩余的元素重新调整为堆。 重复上述步骤直到所有元素都被排序。
C语言代码示例
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) {// 交换当前节点与最大值节点int temp arr[i];arr[i] arr[largest];arr[largest] temp;// 递归调整子树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--) {// 交换堆顶元素与末尾元素int temp arr[0];arr[0] arr[i];arr[i] temp;// 调整剩余元素为堆heapify(arr, i, 0);}
}
算法分析 时间复杂度 最好、平均和最坏情况O(n log n)。 空间复杂度O(1)。 稳定性不稳定。交换操作可能会破坏相等元素的相对顺序。 适用场景适合大数据量的排序性能稳定。
