程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 合並排序的遞歸完成與非遞歸完成代碼

合並排序的遞歸完成與非遞歸完成代碼

編輯:關於C++

合並排序的遞歸完成與非遞歸完成代碼。本站提示廣大學習愛好者:(合並排序的遞歸完成與非遞歸完成代碼)文章只能為提供參考,不一定能成為您想要的結果。以下是合並排序的遞歸完成與非遞歸完成代碼正文


合並排序
合並排序是樹立在合並操作上的一種有用的排序算法。該算法是采取分治法(Divide and Conquer)的一個異常典范的運用。值得留意的是合並排序是一種穩固的排序辦法。將已有序的子序列歸並,獲得完整有序的序列;即先使每一個子序列有序,再使子序列段間有序。若將兩個有序表歸並成一個有序表,稱為2-路合並。

算法描寫
合並操作的任務道理以下:
第一步:請求空間,使其年夜小為兩個曾經排序序列之和,該空間用來寄存歸並後的序列
第二步:設定兩個指針,最後地位分離為兩個曾經排序序列的肇端地位
第三步:比擬兩個指針所指向的元素,選擇絕對小的元素放入到歸並空間,並挪動指針到下一名置

時光龐雜度:
時光龐雜度為O(nlogn) 這是該算法中最好、最壞戰爭均的時光機能。
空間龐雜度為 O(n)
比擬操作的次數介於(nlogn) / 2和nlogn - n + 1。
賦值操作的次數是(2nlogn)。合並算法的空間龐雜度為:0 (n)
合並排序比擬占用內存,但卻效力高且穩固的算法。
(以上摘抄自百度百科)

代碼完成
自頂向上完成:
//應用幫助數組完成合並的進程

void MergeSort(int *aux, int *data, int l, int m, int h)
{
 int k=0, i=l, j=m+1;

 for(k=l; k<=h; k++)
 {
  if(i>m)     aux[k]=data[j++];
  else if(j>h)    aux[k]=data[i++];
  else if(data[i]<data[j])        aux[k]=data[i++];
  else    aux[k]=data[j++];
 }
 for(k=l; k<=h; k++)
  data[k]=aux[k];
}

用遞歸完成排序的進程(自頂向下合並)

void Sort(int *aux, int *data, int l, int h)
{
 if(l<h)
 {
  int m=l+(h-l)/2;
  Sort(aux, data, l, m);
  Sort(aux, data, m+1, h);
  MergeSort(aux,data, l, m, h);
 }
}

用非遞歸完成排序的進程(自底向上合並)

void NonRerMerSort(int *aux, int *data, int l, int h)
{
 int i=l, j;
 for(i=l; i<=h; i=2*i)
 {
  for(j=l; j<=h-i; j+=2*i)
   MergeSort(aux, data, j, i+j-1, Min(j+2*i-1,h));
 }
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved