辽宁省网站建设,对伊利网站建设建议,国内知名公关公司,网站模板源代码下载文章目录 #x1f4dd;选择排序是什么#xff1f;#x1f320;选择排序思路#x1f309; 直接选择排序#x1f320;选择排序优化#x1f320;优化方法#x1f309;排序优化后问题 #x1f320;选择排序效率特性 #x1f309;插入排序#x1f320;插入排序实现 #… 文章目录 选择排序是什么选择排序思路 直接选择排序选择排序优化优化方法排序优化后问题 选择排序效率特性 插入排序插入排序实现 总结 选择排序是什么
选择排序是一种简单直观的排序算法。它的工作原理如下在未排序序列中找到最小(大)元素,交换到起始位置,该元素为已排序序列的起始元素继续在剩余未排序元素中找到最小(大)元素,交换到未排序序列起始位置重复第二步,直到所有元素均排序完毕。
选择排序思路
在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素若它不是这组元素中的最后一个(第一个)元素则将它与这组元素中的最后一个第一个元素交换在剩余的array[i]–array[n-2]array[i1]–array[n-1]集合中重复上述步骤直到集合剩余1个元素
简单来说就是在每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 直接选择排序
例如定义一个数组 int a[6] { 9,5,7,2,3,6 };
首先遍历第一趟数组找出数组的最小值与第一个数据交换 然后遍历第二趟数组继续找出最小值与第二个数据交换 然后遍历第三趟数组继续找出最小值与第三个数据交换 如此重复然后当i等于n-1次选择时排完序最后一个也有序排序完成。
… 代码 上方观察 选择要找几次? 6个数一次选择1个然后有序第五次选择5个都有序最后一个有序。 n个数选择n-1次最后一个自然有序。 第一趟选择下标范围是[0 ~ n-1] 第一趟选择下标范围是[1 ~ n-1] 第一趟选择下标范围是[2 ~ n-1] . . .
void Swap(int* px, int* py)
{int tmp *px;*px *py;*py tmp;
}void SelectSort(int*arr,int n) {for (int i 0; i n - 1; i)//从0开始选选到n-2次 {int mini i;//设最小值是第1位for (int j i 1; j n; j)//首次从1开始到n-1每次比较 { //查找是否有比最小值小的mini arr[j] arr[mini] ? j : mini;}Swap(arr[i], arr[mini]);}
}思路总结 在一个有n个元素中进行排序下标范围是0 ~ n-1然后我们要在0 ~ n-1中找到最小的数与0下标的数进行交换接着在1 ~ n - 1下标中找最小值与1下标交换然后下次就是2 ~ n - 1找最小值与2交换每次找到最小值丢到最前面接着交换随即下标3,45…直到n - 1次选择都排完序前n-1之前有序了最后一个也有序。
特性总结
时间复杂度: 外层for循环从0到n-2,共执行n-1次。内层for循环每次从i1到n,共执行n-i-1次。所以总时间复杂度为:T(n) Σ(n-1)(n-i-1) Θ(n^2)选择排序的时间复杂度是O(n ^ 2)。 空间复杂度: 该算法只使用了一个临时变量mini来记录每次循环找到的最小元素的下标。且不需要额外的数组空间。所以空间复杂度为O(1)。
直接选择排序的特性总结
直接选择排序思考非常好理解但是效率不是很好。实际中很少使用时间复杂度O(N^2)空间复杂度O(1)稳定性不稳定
选择排序优化
优化方法
以上算法是每次找出最小的值放在指定位置一共要找n-1次。如果我们每次不仅找到最小的值还找到最大的值将最小的与左端交换最大的与右端交换那么就少了一半的遍历次数从而提高效率。 变量begin和变量end是数组的两端Min和Max在0位置min和max分别找小和大的下标ibegin1,让begin1到end的数都与begin比较。 先交换min与begin位置的数值再交换max与end位置的数值 begin右移end左移继续找大找小继续交换 重复上述操作直到遍历完所有数组
排序优化后问题
若是max的位置与begin重合,则先让begin与min的位置交换,此时原max位置上的最大值已经被交换走,如果直接让end与现max位置交换,交换的值将是错误的。
当max与begin重合时min在最小值位置 begin先与min的位置交换数据此时max位置的已经不是最大值了 当max再与end位置交换数据排序就会出错 解决方法
当max与begin重合时,先让begin与min交换,此时max原指向的最大值位置已改变,应对max进行修正,让其重新指向数组中真正的最大值位置。然后才能完成end与新max位置元素的交换。
当max与begin重合并且begin此时完成了交换此时最大值已经交换到了min所指向的位置 修改max让max来到min位置 然后再让max与end交换 代码实现
void SelectSort(int* a, int n)
{int begin 0, end n - 1;while (begin end){int mini begin, maxi begin;//选出最小值和最大值的位置for (size_t i begin 1; i end; i){if (a[i] a[mini]){mini i;}if (a[i] a[maxi]){maxi i;}}Swap(a[begin], a[mini]);if (maxi begin){maxi mini;}Swap(a[end], a[maxi]);begin;--end;}
}选择排序效率特性
时间复杂度O(N^2) 空间复杂度O(1) 稳定性不稳定
插入排序
直接插入排序是一种简单的插入排序法其基本思想是**把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。**实际中我们玩扑克牌时就用了插入排序的思想 如动图 步骤
从第一个元素开始,该元素可以认为已经被排序取出下一个元素,在已经排序的元素序列中从后向前扫描如果该元素(已排序)大于新元素,将该元素移到下一位置重复步骤3,直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5
通过不断地将当前元素插入到已经排好序的有序序列中,直到全部元素排完,即完成整个排序过程。
插入排序实现
思路第一个数天然有序第二个数与代排有序序列第一个比较小与插入第三个数与前面两个元素比较依次比较前面元素然后比较完依次将后面元素依次插入到前面有序序列中直到序列停止。 代码如下
void InsertSort(int* arr, int n)
{for (int i 0; i n - 1; i){//[0,end] end1//end记录当前要插入的元素位置 //end1就是待插入元素的下标int end i; int temp arr[end 1];//temp临时存储arr[end1]这个待插入元素while (end 0){//如果temp小于arr[end],说明待插入元素应该插入在这个位置//将元素后移一位if (temp arr[end]){arr[end 1] arr[end];end--;}//否则直接跳出循环else{break;}}//将待插入元素插入到正确位置arr[end 1] temp;}
}时间复杂度 最坏情况下为O(N*N)此时待排序列为逆序或者说接近逆序 最好情况下为O(N)此时待排序列为升序或者说接近升序。 元素集合越接近有序直接插入排序算法的时间效率越高 空间复杂度O(1)它是一种稳定的排序算法 总结
