杭州市富阳区建设局网站,好的漂亮的淘宝客网站,广告投放媒体,做网站专题页需要注意什么冒泡排序
冒泡排序是一种 稳定 的排序算法。
它的工作原理是每次检查相邻两个元素#xff0c;如果前面的元素与后面的元素满足给定的排序条件#xff0c;就将相邻两个元素交换。当没有相邻的元素需要交换时#xff0c;排序就完成了。
假设我们想要从小到大进行排序#…冒泡排序
冒泡排序是一种 稳定 的排序算法。
它的工作原理是每次检查相邻两个元素如果前面的元素与后面的元素满足给定的排序条件就将相邻两个元素交换。当没有相邻的元素需要交换时排序就完成了。
假设我们想要从小到大进行排序 第一次冒泡将最大值放到了数组的最后一位 第二次冒泡将第二大值放在数组的倒数第二位 以此类推。
void BubbleSort(int arr[], int num)
{// 需要 num-1 次冒泡for (int i 0; i num - 1; i){for (int j 0; j num - i - 1; j){if (arr[j] arr[j 1]) swap(arr[j], arr[j 1]);}}
}复杂度分析
当序列完全有序时冒泡排序只需遍历一遍数组不用执行任何交换操作时间复杂度为 $ O(N)$;
在最坏情况下冒泡排序要执行 ( n − 1 ) ⋅ n / 2 (n-1)·n/2 (n−1)⋅n/2次交换操作时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)
冒泡排序的平均时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。
选择排序
每次选择一个最大/最小的数与当前位置的数进行交换。
由于 swap交换两个元素操作的存在可能打乱相等数的相对顺序因此选择排序是一种 不稳定 的排序算法。
void SelectionSort(int arr[], int num)
{// 需要 num-1 次选择for (int i 0; i num - 1; i){int mini i;for (int j i; j num; j){if (arr[j] arr[mini]) mini j;}swap(arr[i], arr[mini]);}
}复杂度分析
最优时间复杂度、平均时间复杂度和最坏时间复杂度均为 O ( N 2 ) O(N^{2}) O(N2)。
插入排序
插入排序是一种 稳定 的排序算法。
插入排序的思想将当前元素与已经排好序的子数组中的元素逐个比较找到合适的位置插入当前元素。
void InsertionSort(int arr[], int num)
{// 从下标 1 开始for (int i 1; i num; i){int cur arr[i];int index i;// 将大于 cur 的元素向右移动while (index - 1 0 arr[index - 1] cur){arr[index] arr[index - 1];index--;}// 将 cur 插入到正确的位置arr[index] cur;}
}复杂度分析
最优时间复杂度为 $ O(N)$最坏时间复杂度和平均时间复杂度都为 O ( N 2 ) O(N^{2}) O(N2)。
希尔排序(**)
希尔排序是一种改进版的插入排序其基本思路如下 选择增量 选择一个增量来决定元素之间的间隔通常增量选择数组总长度的一半 分组排序 根据选定的增量将数组元素分成若干组对于每一组使用插入排序的方法进行排序 逐步缩小增量 逐步减小增量并重复上述分组和排序步骤直至增量为 1。
当增量减小至 1 时相当于进行一次普通的插入排序此时数组已经被排好序了。
因为希尔排序进行了分组可能打乱相等数的相对位置希尔排序是一种 不稳定 的排序算法。
void ShellSort(int arr[], int num)
{// 选择增量int dist num / 2;while (dist){for (int i dist; i num; i){int cur arr[i];int index i;while (index - dist 0 arr[index - dist] cur){arr[index] arr[index - dist];index - dist;}arr[index] cur;}dist / 2; }
}复杂度分析
通常情况下希尔排序的时间复杂度介于 O ( n log 2 n ) O(n \log^2 n) O(nlog2n) 和 O ( n 2 ) O(n^2) O(n2) 之间。
