宣传类的网站怎么做,免费企业建站模板,哈尔滨公共资源信息网,专注做动漫的门户网站文章目录排序算法计数排序选择排序冒泡排序插入排序排序算法
排序算法是解决问题中常见且非常重要的一环#xff0c;针对相应的问题选择相应的排序算法#xff0c;能够提高问题解决速度#xff0c;节省时间#xff01;#xff01;#xff01;
常见的排序算法有#xf…
文章目录排序算法计数排序选择排序冒泡排序插入排序排序算法
排序算法是解决问题中常见且非常重要的一环针对相应的问题选择相应的排序算法能够提高问题解决速度节省时间
常见的排序算法有
排序算法关键步骤时间复杂性最好最坏计数排序比较n(n - 1)/2 nn(n - 1)/2 2n - 1移动06(n - 1)选择排序及时终止的比较n - 1n(n - 1)/2移动33(n - 1)冒泡排序及时终止的比较n - 1n(n - 1)/2移动03n(n - 1)/2插入排序比较n - 1n(n - 1)/2移动2(n - 1)2(n - 1) n(n - 1)/2
下面就这些排序算法进行实现及分析。
计数排序
主要思路及实现 步骤一先对数组中的元素计算相应的名次并将相应的名次保存在 rank 数组中 如何计算名次 每一个元素 a[k]a[k]a[k] 都和它前面的 k−1k - 1k−1 个元素进行比较若 a[k]a[i](i∈[0,k−2])a[k] a[i](i \in [0, k - 2])a[k]a[i](i∈[0,k−2])则 rank[k]反之则 rank[i]for (int i 1; i n; i){for (int j 0; j i; j){if (a[i] a[j])rank[j];elserank[i];}}步骤二根据对应的名字对原数组中的元素进行原地重排 怎样进行重排 当 rank[i]!irank[i] ! irank[i]!i 时使用 swap() 函数对 a[i]a[i]a[i] 和 a[rank[i]]a[rank[i]]a[rank[i]] 进行交换即可注意交换不只是 a 数组要进行交换rank 数组也要跟着一起for (int i 0; i n; i){while (rank[i] ! i){swap(a[i], a[rank[i]]);swap(rank[i], rank[rank[i]]);}}具体实现//计数排序
templatetypename T
void countSort(T* a, int n)
{//计算名次int* rank new int[n] ();for (int i 1; i n; i){for (int j 0; j i; j){if (a[i] a[j])rank[j];elserank[i];}}//按照名次进行原地重排for (int i 0; i n; i){while (rank[i] ! i) //注意 swap 中 a 和 rank 都得换哦{swap(a[i], a[rank[i]]);swap(rank[i], rank[rank[i]]);}}delete[] rank;
}时间复杂性分析 比较次数 在计算名次的时候每一个元素都要和它前面的元素进行比较因此此时经历了compare1n(n−1)2次比较compare_1 \frac{n(n - 1)}{2} \text{次比较}compare12n(n−1)次比较 在原地重排时我们需要考虑最好和最坏两种情况不考虑循环变量的比较。 最好情况下 所有元素开始均已有序因此 r[i] ! i 只需要执行 n 次即可 最坏情况下 每一次交换都会是一个元素到达正确的位置假设第 1 个位置在不停地进行交换那么进行 n - 1 次后所有的元素都会到达其正确的位置。此后只需进行 n 次 r[i] ! i 判断即可。因此共 2n - 1 次 交换次数与移动次数 在按照名次进行原地重排时 最好情况下 一次交换也不做因此此时交换次数为 0 最坏情况下 每次都要作交换并且 n 个元素进行 n - 1 次交换之后第 n 个元素必有序此时只需 n - 1 次 swap 即可 因此交换次数0−2(n−1)0 - 2(n - 1)0−2(n−1)由于每次交换涉及 3 次移动所以移动次数0−3∗2(n−1)0 - 3 * 2(n - 1)0−3∗2(n−1)。
选择排序
“最原始的” 选择排序 主要思路及实现 步骤一在有 n−i(i∈0,1,2,⋯,n−1)n - i(i \in {0, 1, 2, \cdots, n - 1})n−i(i∈0,1,2,⋯,n−1) 个元素的数据集中找出最大元素步骤二将这个最大元素与数据集中最后一个元素进行交换重复步骤一、二直到得到只有 1 个元素的数据集 具体实现 //寻找数据集中的最大值对应的索引
templatetypename T
int indexOfMax(T* a, int n)
{if (n 1)return -1;int indexOfMax 0;for (int i 0; i n; i)if (a[indexOfMax] a[i])indexOfMax i;return indexOfMax;
}//选择排序
templatetypename T
void selectSort(T* a, int n)
{//找到最大元素然后与最后一个元素进行交换for (int i n; i 0; --i)swap(a[i - 1], a[indexOfMax(a, i)]);
}时间复杂性分析 比较次数在对最大值对应的索引进行求取时每个 iii 都要在 indexOfMax() 函数中比较 i - 1 次因此compare112⋯n−1n(n−1)2次compare_1 1 2 \cdots n - 1 \frac{n(n - 1)}{2} \text{次}compare112⋯n−12n(n−1)次交换次数与移动次数 同理进行 n - 1 次交换之后第 n 个元素必在该在的位置上因此交换次数n−1n - 1n−1移动次数3(n−1)3(n - 1)3(n−1)。 “及时终止” 的选择排序 有时候不一定要一直进行排序到只剩下一个元素当某一次函数执行时数据已经有序了那么此时便可以不进行下面的过程了。 主要思路及实现 步骤一设置 bool 值 sorted 来表示序列是否已经有序并赋初始值为 false步骤二在 for 循环中寻找最大索引时我们假设序列已经有序sorted true若 if 中条件一直满足说明假设成立最终 sorted true不再进行下一次循环 若序列仍无序则必会进入 else 语句sorted false。从而达到了及时退出的目的。 具体实现 //及时终止的选择排序
templatetypename T
void improved_selectSort(T* a, int n)
{bool sorted false;for (int i n; !sorted i 0; --i){int indexOfMax 0;//假设已经有序了sorted true;//找最大索引for (int j 0; j i; j){ //如果是有序的就会一直走 if从而 sorted true下次不再进入循环只要有一个不满足sorted 就会置为false说明无序if (a[indexOfMax] a[j])indexOfMax j;elsesorted false;}swap(a[i - 1], a[indexOfMax]);}
}时间复杂性分析 比较次数只考虑 a 数组中的元素的比较 最好情况下即序列已经有序只需进行 if 判断即可故 comparebest(n−1)次compare_{best} (n - 1)\text{次}comparebest(n−1)次 最坏情况下每次都要进行 if 判断共需 compareworstn−1n−2⋯1n(n−1)2次compare_{worst} n - 1 n - 2 \cdots 1 \frac{n(n - 1)}{2}\text{次}compareworstn−1n−2⋯12n(n−1)次交换次数 最好情况下只需进行一次交换即可即第一次的时候故swapbest1次swap_{best} 1\text{次}swapbest1次 最坏情况下每次都需要进行交换故需 swapworst(n−1)次swap_{worst} (n - 1) \text{次}swapworst(n−1)次
冒泡排序
“最原始的” 冒泡排序 主要思路及实现 步骤一每次对 n−i(i∈0,1,2,⋯,n−1)n - i(i \in {0, 1, 2, \cdots, n - 1})n−i(i∈0,1,2,⋯,n−1) 个元素集中的相邻元素进行比较若不满足顺序则交换反之保持原样。每次冒泡过程结果为对应数据集中的最大值被放到序列的最右端步骤二重复步骤一 n - 1 次即可 具体实现 //冒泡排序
//一次冒泡过程
templatetypename T
void bubble(T* a, int n) //一次冒泡过程
{for (int i 0; i n; i){if (a[i] a[i 1])swap(a[i], a[i 1]);}
}templatetypename T
void bubbleSort(T* a, int n)
{for (int i n; i 0; --i)bubble(a, i);
}时间复杂性分析 比较次数针对 a 数组中的元素 这样的比较主要发生在一次冒泡过程中每一次都有 n−i(i∈0,1,2,⋯,n−1)n - i (i \in {0, 1, 2, \cdots, n - 1})n−i(i∈0,1,2,⋯,n−1) 进行比较因此comparen−1n−2⋯21n(n−1)2次compare n - 1 n - 2 \cdots 2 1 \frac{n(n - 1)}{2} \text{次}comparen−1n−2⋯212n(n−1)次交换次数 最好情况下所有元素开始就已经有序无需交换故comparebest0次compare_{best} 0\text{次}comparebest0次 最坏情况下所有元素都得两两进行比较故compareworstn−1n−2⋯21n(n−1)2次compare_{worst} n - 1 n - 2 \cdots 2 1 \frac{n(n - 1)}{2}\text{次}compareworstn−1n−2⋯212n(n−1)次 “及时终止的” 冒泡排序 主要思路及实现 与 “及时终止的” 选择排序一样也是用一个 bool 值变量在 if 循环中控制循环的进行 具体实现 //及时终止的冒泡排序
templatetypename T
void improved_bubbleSort(T* a, int n)
{bool stopped false;for (int i n; !stopped i 0; --i){stopped true;for (int j 0; j i; j){if (a[j] a[j 1])swap(a[j], a[j 1]);elsestopped false;}}
}时间复杂性分析 比较次数 最好情况下只需在第一趟冒泡时进行元素的比较即可因此comparebest(n−1)次compare_{best} (n - 1)\text{次}comparebest(n−1)次 最坏情况下每一次都会进行比较因此compareworstn(n−1)2次compare_{worst} \frac{n(n - 1)}{2}\text{次}compareworst2n(n−1)次交换次数 交换次数和 “最原始的” 冒泡排序一样并无变化。
插入排序 主要思路及实现 步骤一假设第 kkk 个元素 x 之前的序列是有序的将第 kkk 个元素 x 它们进行比较步骤二若 x a[i]则 a[i] 及之后的元素都向后移直接某个元素 x那么 x 就应该插入在第 i 1 个位置 具体实现 //插入排序
templatetypename T
void insert(T* a, int n, int key)
{int i;for (i n - 1; i 0 key a[i]; --i)a[i 1] a[i];a[i 1] key;
}templatetypename T
void insertSort(T* a, int n)
{for (int i 1; i n; i)insert(a, i, a[i]);
}时间复杂性分析 比较次数 最好情况下只需与最后一个元素进行比较即可故 comparebestn−1次compare_{best} n - 1\text{次}comparebestn−1次 最坏情况下每个元素均需进行比较故 compareworstn−1n−2⋯21n(n−1)2次compare_{worst} n - 1 n - 2 \cdots 2 1 \frac{n(n - 1)}{2}\text{次}compareworstn−1n−2⋯212n(n−1)次移动次数 最好情况下只有在传参和最后 key 的赋值时进行了移动因此movebest2(n−1)次move_{best} 2(n - 1)\text{次}movebest2(n−1)次 最坏情况下在 comparebestcompare_{best}comparebest 的基础上还要进行 a 数组元素向后移的操作因此moveworstmovebestn−1n−2⋯212(n−1)n(n−1)2次move_{worst} move_{best} n - 1 n - 2 \cdots 2 1 \\ 2(n - 1) \frac{n(n - 1)}{2}\text{次}moveworstmovebestn−1n−2⋯212(n−1)2n(n−1)次
后续的排序方法还会进行补充
