程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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#法式設計有所贊助。

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