程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 堆排序算法(選擇排序改良)

堆排序算法(選擇排序改良)

編輯：關於C++

堆排序算法(選擇排序改良)。本站提示廣大學習愛好者：（堆排序算法(選擇排序改良)）文章只能為提供參考，不一定能成為您想要的結果。以下是堆排序算法(選擇排序改良)正文

起首要懂得堆的寄義：要末一切節點都不年夜於其子孩子節點數據，要末都不小於其子孩子節點數據

堆排序的焦點思惟：就是要知足一切節點都知足下面兩點，若何完成，看上面

堆排序的步調：

1.起首要建成一個年夜頂堆或許小頂堆，在建的進程中其實就是調劑節點的地位，起首要從最初最初一個節點的母親節點開端，依照堆的寄義調劑。為何不是最初一個或許其他？由於要包管完全性和不用要性，所以只需從最初一個的母親節點開端便可（上面的堆默許存在次序構造，從索引0開端的，所以有些二叉樹的特征請查閱二叉樹），直至索引節點為0的節點。調劑完成後即成為一個堆，然則這裡的數據並沒有排序好，所以下一部調劑次序。

2.從最初一個數據開端，與第一個數據停止交流，然後依照堆的寄義調劑第一個數據。為何先選擇最初一個數據？由於默許情形下，最初一個或許是較年夜或許是較小，可以知足調劑請求。這時候就斟酌以後一切數據減去最初一個，由於這個已經是最年夜或許是最小，不用再斟酌.。直至調劑沒有任何數據，此時已完成排序。

詳細圖例不再標識，有此喜好可以參考其他書本或許網上的引見，上面看堆排序代碼：

int HeapSort(MergeType* L)
{
int i = 0;
if (!L->elem)
{
return -1;
}

//創立堆
for (int i = L->len/2-1; i >= 0; i--)
{
HeapAdjust(L, i, L->len-1);
}

//堆排序
for (i = L->len-1; i >= 0; i-- )
{
swap(L->elem[i], L->elem[0]);
HeapAdjust(L, 0, i-1);
}
return 0;
}

留意：
1）因為父子節點的關系，for輪回第一個數據索引實際上是L,len-1，然則其怙恃節點（i）與以後節點（p）的關系：p = 2i+1 或許2i+2；假如存儲數據的節點第一個索引不是0而是1，這裡p=2i或許p=2i+1，請參看有關書本的證實，所以以後怙恃節點：i =（p-1）/ 2 = (L.len-1-1)/2 = L.len/2-1

2）因為再次調劑數據的時刻是從最初一個數據，所以須要交流數據swap，再停止以後極點數據也就是第一個數據的堆調劑，然則此時調劑的對象只是（0~i）這些數據，其他曾經排序好，所以不再須要調劑

上面看一下調劑代碼，以下：

int HeapAdjust(MergeType* L, int nPos, int nEnd)
{
for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
{
  if (L->elem[i] <= L->elem[i+1])
  {
   i++;
  }
  if (L->elem[nPos] >= L->elem[i])
  {
   break;
  }
  swap(L->elem[nPos], L->elem[i]);
  nPos = i;
}
return 0;
}

這裡應用的是在一個條理上是數據直接交流，其實這不是必需的，由於最初才把數據放到最初的地位，所以也能夠應用上面的代碼，削減復制的次數

int HeapAdjustEx(MergeType* L, int nPos, int nEnd)
{
int nTempkey = L->elem[nPos];

for (int i = nPos*2+1; i < nEnd ; i = 2*i+1)
{
  if (L->elem[i] <= L->elem[i+1])//選出最年夜的子孩子
  {
   i++;
  }
  if (nTempkey >= L->elem[i]) //假如以後節點年夜於最年夜子孩子加入
  {
   break;
  }
  L->elem[nPos] = L->elem[i]; //不然停止數據交流
  nPos = i;
}
L->elem[nPos] = nTempkey;
return 0;
}

這裡便可以削減較多的復制操作，也就是俗稱的挪動操作次數;這裡for輪回的肇端節點依照下面的推論，子節點應當為p=2i+1，所以第一個應當為2*nPos+1，對應該前要比擬節點的做孩子，右孩子為2*nPos+2，也就是左孩子+1，其他請看正文。
時光龐雜度：O（nlogn），剖析進程暫略

public string ApplicationName { get; set; }

//模塊ID
public string ModuleCode { get; set; }

//模塊稱號
public string ModuleName { get; set; }
}

遞歸辦法，讀取每一個模塊和模塊下的菜單：

protected void GetChildMenuList(XElement root, List<MenuTreeSearchModel> menuTreeList)
{
    var firstNode = root.FirstNode as XElement;//讀取root節點內的第一個節點
    if (null != firstNode)
    {
//讀取root節點上面同級的一切節點
var appList =
  from ele in root.Element(firstNode.Name.LocalName).Elements()
  select ele;

bool thisVisible = true;//默許節點是可見的
XAttribute thisAttr = root.Attribute("Display");
if (null != thisAttr)//假如菜單的下級模塊有顯示屬性
{
string thisDisplay = thisAttr.Value;
thisVisible = thisDisplay.ToLower() == "false" ? false : true;
}

foreach (var application in appList)
{
     //模塊Display屬性
     XAttribute modAttr = application.Attribute("Display");
     bool visible = true;
     if (null != modAttr)
     {
  string display = application.Attribute("Display").Value;
  visible = display.ToLower() == "false" ? false : true;
     }
     var nextNode = application.FirstNode as XElement;//該節點的上級節點

     string itemType = "Folder";//目次照樣菜單
     string itemUrl = null;//鏈接地址
     string parentItem = null;//上一節點ID
     string applicationCode = null;//平台編碼
     string applicationName = null;//平台稱號
     string moduleCode = null;//模塊編碼
     string moduleName = null;//模塊稱號

     if (application.Name.LocalName == "Application")
     {
  applicationCode = application.Attribute("ID").Value;
  applicationName = application.Attribute("Text").Value;
     }

     if (application.Name.LocalName == "Module")
     {
  moduleCode = application.Attribute("ID").Value;
  moduleName = application.Attribute("Text").Value;
  applicationCode = root.Attribute("ID").Value;
  applicationName = root.Attribute("Text").Value;

  if (thisVisible) //假如該模塊的所屬平台中的Display屬性設置為可見true（留意：沒有設置則默許為可見），則模塊的下級為Application的ID
  {
      parentItem = root.Attribute("ID").Value;
  }
     }

     if (application.Name.LocalName == "Menu")
     {
  itemType = "Menu";
  itemUrl = application.Attribute("URL").Value;
  moduleCode = root.Attribute("ID").Value;
  moduleName = root.Attribute("Text").Value;
  applicationCode = root.Parent.Parent.Attribute("ID").Value;
  applicationName = root.Parent.Parent.Attribute("Text").Value;

  if (thisVisible) //假如該菜單的所屬模塊中的Display屬性設置為可見true（留意：沒有設置則默許為可見），則菜單的下級為Module的ID
  {
      parentItem = root.Attribute("ID").Value;
  }
  else//假如該菜單的所屬模塊中的Display屬性設置為弗成見false，則菜單的下級為Application的ID
  {
      parentItem = root.Parent.Parent.Attribute("ID").Value;
  }
     }

     MenuTreeSearchModel model = new MenuTreeSearchModel();
     model.ItemCode = application.Attribute("ID").Value;
     model.ItemName = application.Attribute("Text").Value;
     model.ItemType = itemType;
     model.ItemOrder = 0;
     model.Visible = visible;
     model.ItemUrl = itemUrl;
     model.ParentItem = parentItem;
     model.ApplicationCode = applicationCode;
     model.ApplicationName = applicationName;
     model.ModuleCode = moduleCode;
     model.ModuleName = moduleName;
     menuTreeList.Add(model);

     if (null != nextNode)//假如還有上級節點
     {
     　　　　　　　　//挪用遞歸
   GetChildMenuList(application, menuTreeList);
     }
}
    }
}

從XML文檔讀取：

/// <summary>
/// 從XML文件讀取菜單節點
/// </summary>
/// <returns></returns>
public List<MenuTreeSearchModel> GetMenuTreeByReadXML()
{
    List<MenuTreeSearchModel> list = new List<MenuTreeSearchModel>();
//讀取XML文檔途徑，這裡我把XML放在網站的bin目次裡
    string xmlPath = AppDomain.CurrentDomain.BaseDirectory + "Foundation.xml";
    XElement root = XElement.Load(xmlPath);
    var appList =
  from ele in root.Element("Applications").Elements()
  select ele;
//按體系平台挑選
    foreach (var application in appList)
    {
MenuTreeSearchModel model = new MenuTreeSearchModel();
model.ItemCode = application.Attribute("ID").Value;
model.ItemName = application.Attribute("Text").Value;
model.ItemType = "Folder";
model.ItemOrder = 0;
model.Visible = true;
model.ItemUrl = null;
model.ParentItem = null;
model.ApplicationCode = application.Attribute("ID").Value;
model.ApplicationName = application.Attribute("Text").Value;
model.ModuleCode = null;
model.ModuleName = null;
list.Add(model);

//遞歸挪用
GetChildMenuList(application, list);

}

return list;
}

以下是在挪用辦事契約辦法時停止的實體類：

public class PublicUserMenuTreeData
{
//菜單ID
public string ItemCode { get; set; }

//菜單稱號
public string ItemName { get; set; }

//菜單顯示類型
public string ItemType { get; set; }

//排序
public int ItemOrder { get; set; }

//能否顯示
public bool Visible { get; set; }

//菜單鏈接
public string ItemUrl { get; set; }

//下級ID
public string ParentItem { get; set; }

//體系平台ID
public string ApplicationCode { get; set; }

//體系平台稱號
public string ApplicationName { get; set; }

//模塊ID
public string ModuleCode { get; set; }

    //模塊稱號
        public string ModuleName { get; set; }
    //以後菜單下的菜單聚集
    public List<PublicUserMenuTreeData> UserMenuTreeDatas { set; get; }
}

實體轉換辦法：

public PublicUserMenuTreeData TransferUserMenuTreeToPublicUserMenu(MenuTreeData userMenuTreeData)
{
    PublicUserMenuTreeData pubUserMenuTreeData = new PublicUserMenuTreeData();
    pubUserMenuTreeData.ItemCode = userMenuTreeData.ItemCode;
    pubUserMenuTreeData.ItemName = userMenuTreeData.ItemName;
    pubUserMenuTreeData.ItemType = userMenuTreeData.ItemType;
    pubUserMenuTreeData.ItemOrder = userMenuTreeData.ItemOrder;
    pubUserMenuTreeData.Visible = userMenuTreeData.Visible;
    pubUserMenuTreeData.ItemUrl = userMenuTreeData.ItemUrl;
    pubUserMenuTreeData.ParentItem = userMenuTreeData.ParentItem;
    pubUserMenuTreeData.ApplicationCode = userMenuTreeData.ApplicationCode;
    pubUserMenuTreeData.ApplicationName = userMenuTreeData.ApplicationName;
    pubUserMenuTreeData.ModuleCode = userMenuTreeData.ModuleCode;
    pubUserMenuTreeData.ModuleName = userMenuTreeData.ModuleName;
    return pubUserMenuTreeData;
}

用戶權限菜雙方法：

/// <summary>
/// 有效戶權限樹獲得共用的用戶菜單列表
/// </summary>
/// <param name="listAllUserMenu"></param>
/// <returns></returns>
public List<PublicUserMenuTreeData> GetPublicUserMenuFromUserMenuTreeData(List<MenuTreeData> listAllUserMenu)
{
    List<PublicUserMenuTreeData> listPublicUserMenuTreeData = new List<PublicUserMenuTreeData>();
    List<MenuTreeData> list = listAllUserMenu.FindAll(d => string.IsNullOrEmpty(d.ParentItem)).ToList();
    foreach (var userMenuTreeData in list)
    {
PublicUserMenuTreeData pubUserMenuTreeData = TransferUserMenuTreeToPublicUserMenu(userMenuTreeData);
pubUserMenuTreeData.UserMenuTreeDatas = GetChildData(pubUserMenuTreeData.ItemCode, listAllUserMenu);
listPublicUserMenuTreeData.Add(pubUserMenuTreeData);
    }
    return listPublicUserMenuTreeData;
}
public List<PublicUserMenuTreeData> GetChildData(string parentId, List<MenuTreeData> listUserMenuTreeData)
{

    List<MenuTreeData> list = listUserMenuTreeData.FindAll(d => d.ParentItem == parentId).ToList();
    if (list.Count > 0)
    {
List<PublicUserMenuTreeData> listPublicUserMenuTreeData = new List<PublicUserMenuTreeData>();
foreach (var userMenuTreeData in list)
{
     PublicUserMenuTreeData pubUserMenuTreeData = TransferUserMenuTreeToPublicUserMenu(userMenuTreeData);
     pubUserMenuTreeData.UserMenuTreeDatas = GetChildData(pubUserMenuTreeData.ItemCode, listUserMenuTreeData);
     listPublicUserMenuTreeData.Add(pubUserMenuTreeData);
}
return listPublicUserMenuTreeData;
    }
    return null;
}

體系菜單類：

/// <summary>
/// 體系菜單
/// </summary>
[DataContract()]
public class MenuTreeData
{

[DataMember()]
public string ItemCode { get; set; }

[DataMember()]
public string ItemName { get; set; }

[DataMember()]
public string ItemType { get; set; }

[DataMember()]
public int ItemOrder { get; set; }

[DataMember()]
public bool Visible { get; set; }

[DataMember()]
public string ItemUrl { get; set; }

[DataMember()]
public string ParentItem { get; set; }

[DataMember()]
public string ApplicationCode { get; set; }

[DataMember()]
public string ApplicationName { get; set; }

[DataMember()]
public string ModuleCode { get; set; }

[DataMember()]
public string ModuleName { get; set; }

}

後台頁面加載Load代碼：

string menuData = string.Empty;

var treeList= GetMenuTreeList();
if (treeList!= null)
{
         List<MenuTreeData> listAllUserMenu = treeList.FindAll(d => d.Visible).OrderBy(d => d.ItemOrder).ToList();
         List<PublicUserMenuTreeData> listPublicUserMenuTreeData = GetPublicUserMenuFromUserMenuTreeData(listAllUserMenu);
          menuData = JsonConvert.SerializeObject(listPublicUserMenuTreeData);
}

頁面加載劇本，這裡應用Jquery：

var obj = menuData;
GetMenuInfo(obj);
function GetMenuInfo(obj) {
    var str = "";

    var objInfo = "";
    if (obj) {
objInfo = obj.split("|");
if (objInfo[0] != "") {
     var PublicUserMenuTreeData = JSON.parse(objInfo[0]);
     for (var i = 0; i < PublicUserMenuTreeData.length; i++) {
  str += ("<li>");
  var tempmenu= PublicUserMenuTreeData[i];
  if (tempmenu.ItemType && tempmenu.ItemType == "Menu") {
      str += ("<a href='#' onclick='" + tempmenu.ItemCode + "()' id='" + tempmenu.ItemCode + "'>" + tempmenu.ItemName + "</a>");
      str += ("<script> function " + tempmenu.ItemCode);
      str += ("() { tabframe1.newTab({ title: '" + tempmenu.ItemName + "',");
      if (tempmenu.ItemUrl.indexOf('?') != -1) {
   str += ("src: '" + tempmenu.ItemUrl + "&applicationid=" + tempmenu.ApplicationCode + "&moduleid=" + tempmenu.ModuleCode + "',");
      } else {
   str += ("src: '" + tempmenu.ItemUrl + "?applicationid=" + tempmenu.ApplicationCode + "&moduleid=" + tempmenu.ModuleCode + "',");
      }

      str += (" id: 'oa-system-" + tempmenu.ItemCode + "',");
      str += (" closable: true }); jQuery('#mainmenulist').hide(); return false; }<\/script>");
  } else {
      str += ("<a href='#' id='" + PublicUserMenuTreeData[i].ItemCode + "'>" + PublicUserMenuTreeData[i].ItemName + "</a>");
  }

  if (PublicUserMenuTreeData[i].UserMenuTreeDatas) {
      str += GetRecurrenceData(PublicUserMenuTreeData[i].UserMenuTreeDatas);
  }
  str += (" </li>");
     }
}
    }

    function GetRecurrenceData(listPublicUserMenuTreeData) {
    var str = "";
    if (listPublicUserMenuTreeData && listPublicUserMenuTreeData.length>0) {
str += (" <ul>");
for (var j = 0; j < listPublicUserMenuTreeData.length; j++) {
     str += ("<li class='divFontWeight'>");
     if (listPublicUserMenuTreeData[j].ItemType && listPublicUserMenuTreeData[j].ItemType == "Menu") {
  str += ("<a href='#' onclick='" + listPublicUserMenuTreeData[j].ItemCode + "()' id='" + listPublicUserMenuTreeData[j].ItemCode + "'>" + listPublicUserMenuTreeData[j].ItemName + "</a>");
  str += ("<script> function " + listPublicUserMenuTreeData[j].ItemCode);
  str += ("() { tabframe1.newTab({ title: '" + listPublicUserMenuTreeData[j].ItemName + "',");
  if (listPublicUserMenuTreeData[j].ItemUrl.indexOf('?') != -1) {
      str += ("src: '" + listPublicUserMenuTreeData[j].ItemUrl + "&applicationid=" + listPublicUserMenuTreeData[j].ApplicationCode + "&moduleid=" + listPublicUserMenuTreeData[j].ModuleCode + "',");
  } else {
      str += ("src: '" + listPublicUserMenuTreeData[j].ItemUrl + "?applicationid=" + listPublicUserMenuTreeData[j].ApplicationCode + "&moduleid=" + listPublicUserMenuTreeData[j].ModuleCode + "',");
  }

  str += (" id: 'oa-system-" + listPublicUserMenuTreeData[j].ItemCode + "',");
  str += (" closable: true }); jQuery('#mainmenulist').hide(); return false; }<\/script>");
     } else {
  str += ("<a href='#' id='" + listPublicUserMenuTreeData[j].ItemCode + "'>" + listPublicUserMenuTreeData[j].ItemName + "</a>");
     }

var ListMenuDatas = listPublicUserMenuTreeData[j].UserMenuTreeDatas;
str += GetRecurrenceData(ListMenuDatas);

     str += ("</li>");
}
str += (" </ul>");
    }
    return str;
}

後果圖：

這裡彌補一下：菜單中假如在模塊Module裡設置屬性Display="false"，則模塊不顯示出來，可是模塊下的菜單可顯示出來。

itemType="Folder"顯示類型是目次，itemType="Menu"顯示類型是菜單

願望本文所述對年夜家的C#法式設計有所贊助。