直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、二路归并排序

所需积分/C币:34 2018-11-16 12:22:03 684KB PDF
收藏 收藏 5
举报

直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、二路归并排序的C++语言实现,亲测可行,二路归并排序未得到预期结果,望指正。
(3)平均时间复杂度:O(n2); (4)空间复杂度:O(1); 希尔排序 1、算法思想 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组。所有距离为d1的倍数 的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述 的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直 接插入排序为止 2、代码实现 void maine int art[]={68,23,34,45,-33,41,999,-1,68}; int len =9 shellSort(arr,len); void shellSort(int RI],int n)t 1 nt temp; for (int gap n/2;gap>0; gap/=2)t for(int i gap; i<n; i++)t temp R[i]: Int for(]=1;>=gap&&R[j-gap]>temp; 3-=gap)t RIJ]=R[J-gap]: R[J]= temp; outPutArr(R, n); 3、输出结果 C\ C: Windows\ system32\cmd.exe 希尔排序算法 数组长度:9 升序序列:{-33,-1,23,34,41,45,68,68,999}; 请按任意键继续 3 4、时间复杂度与空间复杂度 (1)希尔自己提出的时间复杂度:O(n2); (2)帕佩尔诺夫和斯塔舍维奇提出的时间复杂度:O(n15); (3)空间复杂度:O(1); 超泡排序 1、算法思想 起泡排序属于比较简单的排序,以非递减为例,依次遍历数组,发现R[j1]>R[j的情 况,则交换R[j-1和R[j的顺序,直到没有逆序的数据,即完成排序。 2、代码实现 a void main int arr[]={68,23,34,45,-33,41,999,-1,68} int len 9 bubbleSort(arr, len) void bubbleSort(int Rl, int n)t int 1 bool flag int temp for (i ;i>=i;--){ flag false /n1ag用来标记此趟排序是否发生了交换 for(3= 1; j<=i; j++)t if(R[j-1]>R[订]){ temp= R[j]: R[j]=R[j-1]; R[J-1]= temp f1ag=true;/如果没发生交换,则f1ag为 if(!flag)t //一趟排序过程中没有发生排序,则证明剩余序列有序,不在冒泡 outPutArr(R,n); eturn 3、输出结果 CC: Windows\ system32\cmd.exe 起泡排序算法〉 做数组长度:9 序序列:-33,-1,23,34,41,45,68,68,999 青按任意键继续 4、时间复杂度与空间复杂度 (1)最好情况时间复杂度:O(n); (2)最坏情况时间复杂度:O(n2); (3)平均时间复杂度:O(n2); (4)空间复杂度:O(1); 四、快速排序 1、算法思想 选取一个枢轴元素(通常为待排序序列的第一个数),然后通过一趟排序将比枢轴数大的放 在右边,比枢轴小的放在左边,接着对划分好的两个子序列再进行上述的排序。 2、代码实现 void main()t int arr[]={68,23,34,45,-33,41,999-1,68}; int length =9 quickSort(arr,0, length-1) outPutArr(arr, length) avoid quickSort(int R[,int low, int high)t int temp: int主=1ow,j=high if(low<high)i temp R[low]; whie(i<j){//将数组中小于temp的放在左边,大于temp的放在右边 Whi1e(j>i&&R[j]>=temp){//从右往左扫描,找到一个小于temp的关键字 if(i<3)t RLi=RIJ] //放在temp左边 1十十; //右移一位 while(i<j&&R[i]<temp){//从左往右扫描,找到一个大于temp的关键字 +十 if(i<j)t R[j]=R[i]; //放在temp右边 //左移一位 [主]=temp //将temp放在最终位置 quickSort(R,low,1-1) //递归的对temp左边的关键字排序 quickSort(R,i+1,high) //递归的对temp右边的关键字排序 3、输出结果 CA. C: Windows\system32\ cmd.exe 快速排序算法 组长度:9 升序序列:{-33,-1,23,34,41,45,68,68,999}; 请按任意键继续 4、时间复杂度与空间复杂度 (1)最好情况时间复杂度: O(nlog2n); (2)最坏情况时间复杂度:O(m2); (3)平均时间复杂度:O( nlog2n); (4)空间复杂度:O(ogn) 五、简单选择排序 1、算法思想 选择类排序的主要动作是“选择”,简单选择排序采用最简单的选择方式,从头至尾顺序 扫描序列,找出最小的一个关键字,和第一个关键字交换,接着从剩下的关键字中继续这种 选择和交换,最终使序列有序 2、代码实现 void maine ant arr[]={68,23,34,45,-33,41,999,-1,68}; int len =9 selectsort(arr,len); =void selectsort(int Rll, int n)t int i,j,k; int temp for(i =0; i<n; i++)f K=i /*下面这个循环是算法的关键,它从无序序列中挑出一个最小的关键字* for(] i+1;j<n;j++){ 立f(R[k]>R[j]) k =1 /*下面这三句完成最小关键字与无序序列第一个关键字的交换*/ temp R[i]; R[i]=R[k]; Rlk]=temp; outPutArr(R,n); 3、输出结果 Cn. C: Windows\ system32\cmd.exe 简单选择排序算法 组长度:9 序序列:-3,-1,23,34,41,45,68,68,99 按任意键继续 4、时间复杂度与空间复杂度 (1)时间复杂度:O(n2); (2)空间复杂度:O(1); 六、堆排序 1、算法思想 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结 构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点 2、代码实现 -void main(i int arr[]={68,23,34,45,-33,41,999,-1,68}; int length =9 heapSort(arr, length) E void heapSort(int R[l, int n)t int 1 int temp: for(i=n/2-1;i>=8;i-){ /建立初始堆 sift(R,i,n-1); fo(i=n-1i>8:i--){ //进行n-1次循环,完成堆排序 temp= R[0]: //一下3句换出根节点的关键字,将其放入最终位置 R[e]=R[i]; Rli]= temp sift(,0,1-1) //在减少了一个关键字的无序序列中调整 outPutArr(R, n); void sift(int Rl,int low, int high)t //关键字设定下表从8开始 int i low,] =2*1+1; //R[j是R[i]的左孩子节点 int temp =R[i] While(i<=high)( if(j<high &&R[J]<R[3+1])t //若右孩子较大,则指向右孩子 //变为2*i+2 if(temp<R[J]i R[i]=R[3]; //将R[讥调整到双亲节点的位置 ∥/修改和j的值,继续向下调整 了=2*1+1 false break //调整结束 R[i= temp; //被调整节点放入最终位置 3、输出结果 o\ C: Windows\system32\cmd.exe K堆排序算法 数组长度:9 升序序列:{-33,-1.23,34,41,45,68,68,999} 青按任意键继续 4、时间复杂度与空间复杂度 (1)时间复杂度:O( nlog2n); (2)空间复杂度:O(1); 七、二路归并排序 1、算法思想 二路归并排序是采用的分而治之的思想。将一个待排序的序列分成两个序列,分别对这 两个序列排序。而对于这两个序列排序的方式也是和之前一样,将这两个序列分别分成两个 序列分别排序。一直这样分割下去,知道序列中没有元素或者只有一个元素为止。因为没有 元素的序列和只有一个元素的序列定是一个有序的序列,所以相当于将这个序列排序完毕, 向上返回。返回的过程中做的最重要的一件事就是将两个有序的序列合并成一个有序的序 列。所以归并排序最重要的两步是分割和合并。 2、代码实现 -void main()t int arr[]={68,23,34,45,-33,41,999,-1,68}; int length =9, mergeSort(arr, 0, length-1) out PutArr(arr,length) avoid merge Sort(int RL], int low, int high)t if(low<high)t int mid =(lowthigh)/2 mergeSort(, low, mid) //归并排序前半段 mergeSort(R,mid+1,high);//归并排序后半段 merge(R,1oW,mid,high);/将R数组中1oW~mid, midwhigh两段序列归并为一个序列 void merge(int Rll,int loW,int mid, int high)t int i,j,k; int n1= mid -lc 邀两个组创進时撮。幽綸暴 int n2 = high -mid; nt leftInisrightIn2B for(i=的;i<n1i++)t left[i]=R[loW+i]: for(3 =0;j<n2; j++) right[i]=R[mid +1+J] i=6;j=6;k=1ow while(i<n1 & j<n2)t if(left[i]<=right[j])t Rikl= left[i++ false RIk]=right[3++] While(i<n1)f R[k++]=1eft[i++] while(j<n2)t RIK++]= right[3++] 10

...展开详情
试读 11P 直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、二路归并排序
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 分享宗师

      成功上传21个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、二路归并排序 34积分/C币 立即下载
    1/11
    直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、二路归并排序第1页
    直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、二路归并排序第2页
    直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、二路归并排序第3页
    直接插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、二路归并排序第4页

    试读已结束,剩余7页未读...

    34积分/C币 立即下载 >