seo网站优化培训多少价格,国家企业信用网官网,模板 网站,沈阳网站文章目录 一、排序的基本概念算法的稳定性内部排序与外部排序 二、插入排序直接插入排序希尔排序 三、交换排序冒泡排序快速排序 四、选择排序简单选择排序堆排序 五、归并排序二路归并排序归并排序 六、基数排序多关键字排序链式基数排序 七、内部排序算法的比较 一、排序的基… 文章目录 一、排序的基本概念算法的稳定性内部排序与外部排序 二、插入排序直接插入排序希尔排序 三、交换排序冒泡排序快速排序 四、选择排序简单选择排序堆排序 五、归并排序二路归并排序归并排序 六、基数排序多关键字排序链式基数排序 七、内部排序算法的比较 一、排序的基本概念
算法的稳定性
关键字相同的元素经过排序后相对顺序是否会改变
内部排序与外部排序
内部排序数据都在内存中----关注时间、空间复杂度、稳定性外部排序数据太多无法全部放入内存----还需关注磁盘读取次数
二、插入排序
直接插入排序
每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中平均时间复杂度O(n^2)算法稳定性稳定
void InsertSort(int A[],int n){int i,j,temp;for(i1;in;i){if(A[i]A[i-1]){tempA[i];for(ji-1;j0A[j]temp;--j){A[j1]A[j]; // 从后往前检查比当前元素大的右移}A[j1]temp;}}
}希尔排序
先追求表中元素部分有序再逐渐逼近全局有序仅适用于顺序表算法过程 相隔增量d的元素组成同一个子表对各个子表分别进行直接插入排序缩小增量d直到d1为止 算法稳定性不稳定 相同关键字划分到不同子表可能改变相对次序
void ShellSort(int A[],int n){int i,j,temp,d;for(dn/2;d1;dd/2){for(id;in;i){if(A[i]A[i-d]){tempA[i];for(ji-d;j0A[j]temp;j-d){A[jd]A[j]; // 检查前面比当前元素大的右移}A[jd]temp;}}}
}三、交换排序
冒泡排序
从后往前或从前往后两两比较相邻元素的值若为逆序则交换平均时间复杂度O(n^2)算法稳定性稳定
void BubbleSort(int A[],int n){int i,j,temp,flag;for(i0;in-1;i){flagfalse;for(jn-1;ji;j--){if(A[j]A[j-1]){ //相等不交换保持稳定tempA[j];A[j]A[j-1];A[j-1]temp;flagtrue;}}if(flagfalse)return; //本趟遍历后没有发生交换说明已经有序}
}快速排序
用枢轴元素pivot划分待排序表算法过程 两个指针low和high向中间移动将小于pivot的元素放到左边大于pivot的元素放到右边pivot元素放到最终位置上再对左右递归 快速排序是所有内部排序算法中平均性能最优的排序算法空间复杂度 最好O(log_2n)最坏O(n)平均O(log_2n) 平均时间复杂度O(nlog_2n)稳定性不稳定
int Partition(int A[],int low,int high){int pivotA[low];while(lowhigh){while(lowhighA[high]pivot){--high;}A[low]A[high]; // 比枢轴小的元素移动到左边while(lowhighA[low]pivot){low;}A[high]A[low]; // 比枢轴大的元素移动到右边}A[low]pivot;return low;
}void Quicksort(int A[],int low,int high){if(lowhigh){ //递归跳出条件int pivotposPartition(A,low,high);Quicksort(A,low,pivotpos-1);Quicksort(A,pivotpos1,high);}}四、选择排序
简单选择排序
每一趟在待排元素中选取关键字最小或最大的元素加入有序子序列平均时间复杂度O(n^2)稳定性不稳定
void Selectsort(int A[],int n){int i,j,temp,min;for(i0;in-1;i){mini;for(ji1;jn;j){if(A[j]A[min]){minj; //得到最小关键字的索引}}if(min!i){tempA[min];A[min]A[i];A[i]temp;}}
}堆排序
将待排序列整理成大根堆或小根堆后进行选择排序大根堆根左、右建立大根堆 在顺序存储的完全二叉树中非终端节点编号i⌊n/2⌋由后向前检查所有非终端节点若不满足根左、右将当前节点与更大的一个孩子互换若元素互换破坏了下一级的堆则采用相同方法继续向下调整建堆的时间复杂度O(n) 输出堆顶元素最后一个元素替换堆顶算法过程 首先建立大根堆不断输出堆顶元素并将剩余元素序列再次调整为大根堆 堆的插入删除 插入插入到堆底后“上升”删除用堆底元素替换后“下坠” 平均时间复杂度O(nlog_2n)稳定性不稳定
//建立大根堆
void BuildMaxHeap(int A[],int len){int i;for(ilen/2;i0;i--){ //从后往前调整所有非终端节点HeadAdjust(A,i,len);}
}//将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){int i;A[0]A[k]; //A[0]暂存防止覆盖for(i2*k;ilen;i*2){if(ilenA[i]A[i1]){i; //获取左右孩子中更大的}if(A[0]A[i])break;else{A[k]A[i]; //A[i]调整到双亲结点上ki; //向下继续筛选}}A[k]A[0]; //注意此时k值已经改变为该节点最终位置
}// 堆排序
void HeapSort(int A[],int len){BuildMaxHeap(A,len);int temp;for(int ilen;i1;i--){tempA[i];A[i]A[1];A[1]temp; //堆顶元素和堆底元素互换HeadAdjust(A,1,i-1); //把剩余待排元素整理为大根堆}
}五、归并排序
二路归并排序
将相邻的两个有序表合并成一个
归并排序
将n个待排元素分成两个长度相等的子序列分别对两个子序列递归调用归并方法再将两有序子序列二路归并排序空间复杂度O(n)平均时间复杂度O(nlog_2n)稳定性稳定
int *B(int *)malloc((n1)*sizeof(int)); // 辅助数组Bvoid Merge(int A[],int low,int mid,int high){// mid分割两个待归并序列for(int klow;khigh;k){B[k]A[k]; //复制到辅助数组中}int i,j,k;for(ilow,jmid1,ki;imidjhigh;k){if(B[i]B[j]){A[k]B[i];}else{A[k]B[j];}}while(imid)A[k]B[i];while(jhigh){A[k]B[j];}
}void MergeSort(int A[],int low,int high){if(lowhigh){int mid(lowhigh)/2;MergeSort(A,low,mid);MergeSort(A,mid1,high);Merge(A,low,mid,high); //归并}
}
六、基数排序
多关键字排序
按照关键字各位大小排序n待排元素个数d单个元素分量的个数rd基数每个分量的取值范围单逻辑关键字文件中任意一关键字k均由d个分量构成且每个分量都是单独的关键字排序方法 最高位优先法MSD–逐层分割成若干子序列最低位优先法LSD–不必分成若干子实现排序序列不通过关键字比较通过“分配”“收集”实现排序
链式基数排序
算法过程 将关键字拆分为d位或组按照各个关键字位权重递增的次序LSD方法做d趟分配O(n)和收集O(rd) 空间复杂度O(rd)时间复杂度O(d(nrd))稳定性稳定
七、内部排序算法的比较
各算法性质比较表
排序算法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度(平均)是否稳定直接(折半)插入排序O(n)O(n2)O(n2)O(1)稳定希尔排序---O(1)不稳定冒泡排序O(n)O(n2)O(n2)O(1)稳定快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n)不稳定简单选择排序O(n2)O(n2)O(n2)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定基数排序O(d(nrd))O(d(nrd))O(d(nrd))O(rd)稳定 规律总结 每次排序确定一个最终位置插入排序冒泡排序选择排序快速排序算法复杂度与初始状态无关选择排序、堆排序、归并排序、基数排序比较次数与初始状态无关选择排序、基数排序移动次数与初始状态无关归并排序、基数排序排序趟数与初始状态有关快速排序、冒泡排序 根据关键字分布情况选择排序方法 n较小基本有序直接插入排序n较小数据项较多所占存储空间较大简单选择排序
