C++选择排序算法实例详解
本文实例为大家分享了C++选择排序算法的具体代码,供大家参考,具体内容如下
基本思想
每一趟从无序区中选出最小的元素,顺序放在有序区的最后,直到全部元素排序完毕。
由于选择排序每一趟总是从无序区中选出全局最小(或最大)的元素,所以适用于从大量元速度中选择一部分排序元素。例如,从10000个元素中选出最小的前10位元素。
直接选择排序
1.排序思路
从第i趟开始,从当前无序区arr[i…n-1]中选出最小元素arr[k],将它与有序区的最后一个元素,也就是无序区的第一个元素交换。每趟排序后,有序区增加一个元素,无序区减少一个元素,且有序区中所有元素均小于等于无序区中的元素。经过n-1趟排序后,无序区只剩下arr[n-1]一个元素,它必然为整个序列的最大值,故无需再排。
2.排序算法
voidSelectSort(int*arr,intsize) { if(arr==NULL) return; //1.找到无序区中最小的元素和它的下标 inti,j; for(i=0;i3.算法分析
由于要选出最小值,故无序区中的每个元素都要参与比较,所以无论初始数据序列的状态如何,总的比较次数为:
C=n-1+n-2+n-3+…+2+1=n(n-1)/2
故直接选择排序的时间复杂度为O(N^2),空间复杂度为O(1)。直接选择排序是一个不稳定的算法。例如,排序序列为{5,3,2,5,4,1},第一趟排序后得到{1,3,4,5,4,5},两个5的相对位置发生了变化。
4.优化版本
每趟排序同时找出最大值和最小值,把最小值放在序列的左边,最大值放在序列的右边,然后同时缩小左右排序范围。
//优化,每趟排序同时找出最大值和最小值 voidSelectSort1(int*arr,intsize) { if(arr==NULL) return; intleft=0; intright=size-1; while(leftarr[right]) swap(arr[i],arr[right]); } left++; right--; } } 堆排序
1.排序思路
堆排序是一种树形选择排序方法,在排序过程中,将arr[0…n-1]看成一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子结点之间的内在关系,在当前无序区中选择最大(或最小)的元素。
下标从0开始,节点i的两个孩子节点可表示为2*i+1、2*i+2。2.排序算法
voidAdjustDown(int*arr,intsize,intparent) { intchild=2*parent+1; while(child=0;root--) { AdjustDown(arr,size,root); } //2.将arr[0]与arr[n-1]交换,然后再调整arr[0...n-1],使其满足大堆,如此反复操作 for(root=size-1;root>=1;root--) { swap(arr[root],arr[0]); AdjustDown(arr,root,0); } } 3.算法分析
堆排序的时间主要由建堆和反复调整堆这两部分的时间构成,由于可以把堆看成完全二叉树的结构,所以堆排序的时间复杂度为O(N*lgN),空间复杂度为O(1),堆排序算法不稳定。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。