网站建站 优化推广,重庆建设施工工程信息网,seo网络推广优化,江苏常州武进区建设局网站概述排序有内部排序和外部排序#xff0c;内部排序是数据记录在内存中进行排序#xff0c;而外部排序是因排序的数据很大#xff0c;一次不能容纳全部的排序记录#xff0c;在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。当n较大#xff0c;则应采用时间复…概述排序有内部排序和外部排序内部排序是数据记录在内存中进行排序而外部排序是因排序的数据很大一次不能容纳全部的排序记录在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。当n较大则应采用时间复杂度为O(nlog2n)的排序方法快速排序、堆排序或归并排序序。快速排序是目前基于比较的内部排序中被认为是最好的方法当待排序的关键字是随机分布时快速排序的平均时间最短1.插入排序—直接插入排序(Straight Insertion Sort)基本思想:将一个记录插入到已排序好的有序表中从而得到一个新记录数增1的有序表。即先将序列的第1个记录看成是一个有序的子序列然后从第2个记录逐个进行插入直至整个序列有序为止。要点设立哨兵作为临时存储和判断数组边界之用。直接插入排序示例如果碰见一个和插入元素相等的那么插入元素把想插入的元素放在相等元素的后面。所以相等元素的前后顺序没有改变从原无序序列出去的顺序就是排好序后的顺序所以插入排序是稳定的。算法的实现void print(int a[], int n ,int i){coutfor(int j 0; j8; j){cout}cout}void InsertSort(int a[], int n){for(int i 1; iif(a[i] int j i-1;int x a[i]; //复制为哨兵即存储待排序元素a[i] a[i-1]; //先后移一个元素while(x a[j1] a[j];j--; //元素后移}a[j1] x; //插入到正确位置}print(a,n,i); //打印每趟排序的结果}}int main(){int a[8] {3,1,5,7,2,4,9,6};InsertSort(a,8);print(a,8,8);}效率时间复杂度O(n^2).其他的插入排序有二分插入排序2-路插入排序。2. 插入排序—希尔排序(Shells Sort)希尔排序是1959 年由D.L.Shell 提出来的相对直接排序有较大的改进。希尔排序又叫缩小增量排序基本思想先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行依次直接插入排序。操作方法选择一个增量序列t1t2…tk其中titjtk1按增量序列个数k对序列进行k 趟排序每趟排序根据对应的增量ti将待排序列分割成若干长度为m 的子序列分别对各子表进行直接插入排序。仅增量因子为1 时整个序列作为一个表来处理表长度即为整个序列的长度。希尔排序的示例算法实现我们简单处理增量序列增量序列d {n/2 ,n/4, n/8 .....1}n为要排序数的个数即先将要排序的一组记录按某个增量d(n/2,n为要排序数的个数)分成若干组子序列每组中记录的下标相差d.对每组中全部元素进行直接插入排序然后再用一个较小的增量(d/2)对它进行分组在每组中再进行直接插入排序。继续不断缩小增量直至为1最后使用直接插入排序完成排序。void print(int a[], int n ,int i){coutfor(int j 0; j8; j){cout
