电影网站如何做,学校网络建设方案设计,做营销型网站要多少钱,wordpress帅气主题插入排序
基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为止#xff0c;得到一个新的有序序列 。 打扑克牌整理手牌用的就是插入排序的思想 代码实现 void InsertSort(int* a, int n) { assert(a); …插入排序
基本思想 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 打扑克牌整理手牌用的就是插入排序的思想 代码实现 void InsertSort(int* a, int n) { assert(a); for (int i 0; i n - 1; i)//将一个数组中所有元素升序 { //,这里必须是n-1,不然后面数组会越界 int endi; int xa[end1];//x始终指向end下一个位置的值 while (end 0)//每趟插入最多挪动end-1个数据 { if (a[end] x)//x前一个数大于x,就将数据往后移一格 { a[end 1] a[end];//这里数组的值会往后覆盖 //但是没关系,我们已经将a[end1]的值保存在x当中了 end--; } else { break;//跳出里面的while循环 } } a[end 1] x; } } 特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 2. 时间复杂度O(N^2) 3. 空间复杂度O(1)它是一种稳定的排序算法 4. 稳定性稳定 选择排序
基本思想 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 就像小学生排队一样让最矮的那个站到第一排然后让第二矮的占到第二排以此类推
代码实现 void SelectSort(int* a, int n) { int begain 0; int end n - 1; while (begain end) { int maxi begain;//初始化最值 int mini begain; for (int i begain; i end; i) { if (a[i] a[mini]) { mini i;//记录下标,否则会有数据被覆盖的问题 } if (a[i] a[maxi]) { maxi i; } } swap(a[begain], a[mini]);//将最大最小值交换 swap(a[end], a[maxi]); begain;//数组范围往中间缩小 end--; } } 代码优化
上述思想是单向的我们可以让最高的和最矮的同时排序就可以优化一下实现双向排序 void SelectSort(int* a, int n) { int begain 0; int end n - 1; while (begain end) { int maxi begain; int mini begain; for (int i begain; i end; i) { if (a[i] a[mini]) { mini i;//记录下标,否则会有数据被覆盖的问题 } if (a[i] a[maxi]) { maxi i; } } swap(a[begain], a[mini]); if (maxi begain)//当最大值为begain时,交换最小值和开头元素后,maxi指向的值不再是最大值了. { maxi mini; } swap(a[end], a[maxi]); begain; end--; } } 特性总结 1. 直接选择排序思考非常好理解但是效率不是很好。实际中很少使用 2. 时间复杂度O(N^2) 3. 空间复杂度O(1) 4. 稳定性不稳定
