惠州企业网站建设,明年做那个网站致富,电子购物网站开发,在线绘画软件目录 1.排序的概念及其运用1.1排序的概念1.2排序运用1.3常见的七大排序 2.直接插入排序2.1基本思想2.2直接插入排序2.3动图助解2.4直接插入排序源码2.5直接插入排序的特性总结 3.希尔排序( 缩小增量排序 )3.1希尔… 目录 1.排序的概念及其运用1.1排序的概念1.2排序运用1.3常见的七大排序 2.直接插入排序2.1基本思想2.2直接插入排序2.3动图助解2.4直接插入排序源码2.5直接插入排序的特性总结 3.希尔排序( 缩小增量排序 )3.1希尔排序概念及思想3.2希尔排序图解3.3希尔排序源码3.4希尔排序的两种预排序图解3.5希尔排序的特性总结 1.排序的概念及其运用
1.1排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 1.2排序运用 1.3常见的七大排序
2.直接插入排序 从1.3的图中我们也可以发现插入排序有两种类型—【直接插入排序】、【希尔排序】 它们都属于插入排序希尔排序是直接插入排序的优化形式。 2.1基本思想 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。 实际中我们玩扑克牌时就用了插入排序的思想 2.2直接插入排序 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移。 2.3动图助解 插入排序动图 2.4直接插入排序源码
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){// [0,end]有序把end1位置的值插入保持有序int end i;int tmp a[end 1];//插入的值和前面[0,end]的值进行比较while (end 0){if (tmp a[end])//插入的值小就往前挪一下{a[end 1] a[end];--end;}else//到这里就是数组中的值插入的值 || 整个[0,end]的值都插入的值{break;}}a[end 1] tmp;//放入插入值}
} 2.5直接插入排序的特性总结 元素集合越接近有序直接插入排序算法的时间效率越高 ①最优顺序有序/接近顺序有序 —O(N)时间复杂度 ②最坏逆序—O(N^2)空间复杂度O(1)它是一种稳定的排序算法 稳定性稳定 3.希尔排序( 缩小增量排序 )
【希尔排序】是对上面【直接插入排序】的最坏情况进行优化。
3.1希尔排序概念及思想 希尔排序法又称缩小增量法。 希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 3.2希尔排序图解 【希尔排序】And【直接插入排序】单趟排序的区别 3.3希尔排序源码
void ShellSort(int* a, int n)
{//方法一双层循环不太推荐/*int gap 3;*//*for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}*/
/////方法二单层for循环推荐// gap 1时是预排序// gap 最后一次等于1是直接插入排序int gap n;while (gap 1){gap gap / 3 1;//保证最后一次gap1就是【直接插入排序】了。for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
} 3.4希尔排序的两种预排序图解
方法一【双层for循环控制】 这种排序将这个数组分成3组数 红色——9 6 4 1 蓝色——8 5 3 紫色——7 5 2 排序的顺序是先排序完红色的4个数再排序蓝色的3个数最后排序紫色的3个数 方法二【单层for循环控制】 这个方法下就是排序完红色的第1个数再排序完蓝色的第1个数最后排序紫色的第1个数—在轮到红色的第2个数… 3.5希尔排序的特性总结 希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的。 4.希尔排序的时间复杂度都不固定这边给个大概的平均时间复杂度—O(N^1.3)
