多种昆明网站建设,陕西高速公路建设集团网站,东莞证券官方网站,广州手机软件开发摘要#xff1a;本文主要讲各种排序算法#xff0c;注意它们的时间复杂度
概念
将各元素按关键字递增或递减排序顺序重新排列
评价指标
稳定性: 关键字相同的元素经过排序后相对顺序是否会改变
时间复杂度、空间复杂度
分类
内部排序——数据都在内存中
外部排序——…摘要本文主要讲各种排序算法注意它们的时间复杂度
概念
将各元素按关键字递增或递减排序顺序重新排列
评价指标
稳定性: 关键字相同的元素经过排序后相对顺序是否会改变
时间复杂度、空间复杂度
分类
内部排序——数据都在内存中
外部排序——数据太多无法全部放入内存
一、插入排序
算法思想每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中直到全部记录插入完成
比27大的数往后挪 void InsertSort() {int i, j ,temp;for (i 1;i n;i)//将各元素插入已排好序的序列中{if (A[i] A[i - 1]){//若A[i]关键字小于前驱temp A[i];//用temp暂存A[i]for (j i - 1;j 0 A[j] temp;--j)//检查所有前面已排好序的元素{A[j 1] A[j];//所有大于temp的元素都向后挪位}A[j 1] temp;//复制到插入位置}}
}
void InsertSort() {int i, j;for (i 2;i n;i)//依次将A[2]~A[n]插入到前面已排序序列{if (A[i] A[i - 1]) {//若A[i]关键码小于其前驱将A[i]插入有序表A[0] A[i];//复制为哨兵A[0]不存放元素for (j i - 1;A[0] A[j];--j)//从后往前查找待插入位置{A[j 1] A[j];//向后挪位}}A[j 1] A[0];//复制到插入位置}}
}
优点不用每轮循环判断j0
空间复杂度O(1)
时间复杂度主要来自对比关键字、移动元素 若n个元素则需要n-1趟处理
最好时间复杂度全部有序O(n)
最坏逆序O(n^2)
平均On^2)
算法稳定性稳定
优化——折半插入排序 当lowhigh时折半查找停止应将[low,i-1]内的元素全部右移并将A[0]复制到low所指位置
当A[mid]A[0]时为了保证算法的“稳定性”应继续在mid 所指位置右边寻找插入位置
void InsertSort() {int i,j,low, high, mid;for (i 2;i n;i) {//依次将A[2]~A[n]插入前面的已排序序列A[0] A[i];//将A[i]暂存到A[0]low 1;high i - 1;//设置折半查找的范围while (low high) {//折半查找mid (low high) / 2;//取中间点if (A[mid] A[0])high mid - 1;//查找左半子表else low mid 1;//查找右半子表}for (j i - 1;j high 1;--j)A[j 1] A[j];//统一后移元素空出插入位置A[high 1] A[0];//插入操作}
}
二、希尔排序(Shell sort)
最好情况原本就有序
比较好的情况基本有序
希尔排序先追求表中元素部分有序再逐渐逼近全局有序
先将待排序表分割成若干形如L[i,id,i2d,…ikd]的“特殊”子表对各个子表分别进行直接插入排序。缩小增量d重复上述过程直到d1为止
重点给出增量序列分析每一趟排序后的状态
void ShellSort() {int d, i, j;//A[0]只是暂存单元不是哨兵当j0时插入位置已到for (d n / 2;d 1;d d / 2)//步长变化for (i d ;i n;i)if (A[i] A[i - d]) {//需将A[i]插入有序增量子表A[0] A[i];//暂存在A[0]for (j i - d;j 0 A[0] A[j];j - d)A[j d] A[j];//记录后移查找插入的位置A[j d] A[0];//插入}
}
三、交换排序
1、冒泡排序
从后往前或从前往后两两比较相邻元素的值若为逆序即A[i-1]A[i]),则交换它们直到序列比较完。称这样过程为“一趟”冒泡排序。
void BubbleSort() {for (int i 0;i n - 1;i) {bool flag false;//表示本趟冒泡是否发生交换的标志for (int jn;j i;j--)//一趟冒泡过程if (A[j - 1] A[j]) {//若为逆序swap(A[j - 1], A[j]);//交换flag true;}if (flag false)return;//本趟遍历后没有发生交换说明表已经有序}
}
2、快速排序
算法思想
在待排序表L[1,…n]中任取元素pivot作为枢轴或基准通常取首元素
通过一趟排序将待排序表划分成独立的两部分L[1…k-1]和L[k1…n], 使得L[1…k-1]中的所有元素小于pivot,L[k1…n]大于等于则pivot放在了其最终位置L(k)上这个过程称为一次“划分”。
然后分别递归地对两个子表重复上述过程直到每部分内只有一个元素或空为止即所有元素放在了最终位置上
//用第一个元素将待排序序列划分为左右两个部分
int Partition( int low, int high) {int pivot A[low];//第一个元素作为枢轴while (low high) {//用low、high搜索枢轴的最终位置while (low high A[high] pivot) --high;A[low] A[high];//比枢轴小的元素移动到左端while (low high A[low] pivot) low;A[high] A[low];//大 右}A[low] pivot;//枢轴元素存放到最终位置return low;//返回存放枢轴的最终位置
}//快速排序
void QuickSort(int low, int high) {if (low high) {//递归跳出的条件int pivotpos Partition( low, high);//划分QuickSort( low, pivotpos - 1);//划分左子表QuickSort(pivotpos 1, high);//划分右子表}
} 算法表现主要取决于递归深度若每次“划分”越均匀则递归深度越低。“划分”越不均匀递归深度越深
三、选择排序
每一趟在待排序元素中选取关键字最小或最大的元素加入有序子序列
1、简单选择排序
void SelectSort() {for (int i 0;i n - 1;i) {//一共进行n-1趟int min i;//记录最小元素位置for (int j i 1;j n;j)//在A[i…n-1]中选择最小元素if (A[j] A[min]) min j;//更新最小元素位置if (min ! i) swap(A[i], A[min]);//封装的swap()函数共移动元素3次}
}
2、堆排序
若满足L(i)L(2i)且L(i)L(2i1)(1in/2)——大根堆大顶堆
思路
把所有非终端结点都检查一遍是否满足大根堆的要求如果不满足则进行调整
顺序存储的完全二叉树中非终端结点编号i[n/2]
检查当前结点是否满足根左、右
若不满足将当前结点与更大的一个孩子互换
i的左孩子2i, 右孩子2i1,父结点[i/2]
若元素互换破坏了下一级的堆则采用相同的方法继续往下调整小元素不断“下坠”
这个比较复杂附视频8.4_2_堆排序_哔哩哔哩_bilibili
void BuildMaxHeap(int len) {for (int i len / 2;i 0;i--)//从后往前调整所有非终端结点,即非叶子结点HeadAdjust(i,len);
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int k,int len) {A[0] A[k];//A[0]暂存子树的根节点for (int i 2*k;i len;i*2) {//从左子树开始沿key较大的子结点向下筛选if (i len A[i] A[i 1])//i len 保证有右兄弟i;//取key较大的子结点的下标if (A[0] A[i]) break;//筛选结束else {A[k] A[i];//将A[i]调整到双亲结点上k i;//修改k值以便继续向下筛选}}A[k] A[0];//被筛选结点的值放入最终位置
}
结论一个结点每“下坠”一层最多只需对比关键字2次
若树高为h某结点在第i层则将这个结点向下调整最多只需要”下坠“h-i层关键字对比次数不超过 2h-i)
基于大根堆进行排序
//堆排序的完整逻辑
void HeapSort(int len) {BuildMaxHeap(len);//初始建堆for (int i len;i 1;i--) {//n-1趟的交换和建堆过程swap(A[i], A[1]);//堆顶元素和堆底元素互换HeadAdjust(1, i - 1);//把剩余的待排序元素整理成堆}
}
堆排序:每一趟将堆顶元素加入有序子序列与待排序序列中的最后一个元素交换
并将待排序序列中再次调整为大根堆小元素不断下坠
得到“递增序列”
时间复杂度O(n)O(nlog2n)O(nlog2n)
O(n)建堆O(nlog2n)排序
稳定性不稳定
堆的插入删除
插入对于小根堆新元素放到表尾与父结点对比若新元素比父结点更小则将二者互换。新元素就这样一路“上升”直到无法继续上升为止。
删除被删除的元素用堆底元素替代然后让该元素不断“下坠“直到无法下坠为止
关键字对比次数
每次“上升”调整只需对比关键字1次
每次“下坠”调整可能需要对比关键字2次也可能只需对比1次
四、基数排序
要求得到按关键字“递减”的有序序列
基数排序不是基于“比较”的排序算法
第一趟以“个位”进行“分配”
第一趟“收集”结束得到按“个位”递减排序的序列 算法思想
将整个关键字拆分为d位组
按照各个关键字位权重递增的次序如个、十、百做d趟“分配”和“收集”若当前处理的关键字位可能取得r个值则需要建立r个队列
分配顺序扫描各个元素根据当前处理的关键字位将元素插入相应队列。一趟分配耗时On)
收集把各个队列中的结点依次出队并链接。一趟收集耗时Or
性能
空间复杂度 Or)
时间复杂度 Od(nr)) (一趟分配O(n)一趟收集O(r)
稳定
擅长处理
1、数据元素的关键字可用方便地拆分为d组且d较小
2、每组关键字的取值范围不大即r较小
3、数据元素个数n较大
五、归并排序
归并把两个或多个已经有序的序列合并成一个
2路合并 k路合并
空间复杂度On)
时间复杂度Onlogn)
稳定
//B是辅助数组
const int SIZE sizeof(A) / sizeof(A[0]);
int B[SIZE]; void Merge(int A[], int low, int mid, int high) {for (int k low; k high; k)B[k] A[k]; int i low, j mid 1, k i;while (i mid j high) {if (B[i] B[j])A[k] B[i]; elseA[k] B[j];}while (i mid) A[k] B[i];while (j high) A[k] B[j];
}void MergeSort(int A[], int low, int high) {if (low high) {int mid (low high) / 2; MergeSort(A, low, mid); MergeSort(A, mid 1, high); Merge(A, low, mid, high); }
}
