程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> c/c++常用算法(10) -- 基本排序算法(選擇排序)

c/c++常用算法(10) -- 基本排序算法(選擇排序)

編輯:C++入門知識

選擇排序


選擇排序(SelectionSort)的基本思想是:每次從當前待排序的記錄中選取關鍵字最小的記錄表,然後與待排序的記錄序列中的第一個記錄進行交換,直到整個記錄序列有序為止。


1.簡單選擇排序


簡單選擇排序(Simple Selection Sort,又稱為直接選擇排序)的基本操作是:通過n-i次關鍵字間的比較,從n-i+1個記錄中選取關鍵字最小的記錄,然後和第i個記錄進行交換,i=1,2, …n-1 。


1 .1 排序示例


例:設有關鍵字序列為:7,4, -2, 19, 13, 6,直接選擇排序的過程如下圖10-8所示。


\


1.2 算法實例


//選擇排序
#include 
#include 

#define SIZE 10

void SelectionSort(int *a,int len)
{
    int i,j,k,h;
    int temp;
    
    for (i=0; i
運行結果如圖:

\


2.堆排序


<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8aDI+Mi4xICC20bXEtqjS5TwvaDI+CjxwPjwvcD4KPHA+PGJyPgo8L3A+CjxwPiAgICAgICAgysduuPbUqsvYtcTQ8sHQSD17azEsIGsyICwgoa1rbn0go6zC+tfjo7o8L3A+CjxwPjxicj4KPC9wPgo8cD48aW1nIHNyYz0="http://www.Bkjia.com/uploadfile/Collfiles/20131224/20131224104656238.jpg" alt="\">


由堆的定義知,堆是一棵以k1為根的完全二叉樹。若對該二叉樹的結點進行編號(從上到下,從左到右),得到的序列就是將二叉樹的結點以順序結構存放,堆的結構正好和該序列結構完全一致。


2.2 堆的性質


① 堆是一棵采用順序存儲結構的完全二叉樹,k1是根結點;

② 堆的根結點是關鍵字序列中的最小(或最大)值,分別稱為小(或大)根堆;

③ 從根結點到每一葉子結點路徑上的元素組成的序列都是按元素值(或關鍵字值)非遞減(或非遞增)的;

④堆中的任一子樹也是堆。

利用堆頂記錄的關鍵字值最小(或最大)的性質,從當前待排序的記錄中依次選取關鍵字最小(或最大)的記錄,就可以實現對數據記錄的排序,這種排序方法稱為堆排序。


2.3 堆排序思想


① 對一組待排序的記錄,按堆的定義建立堆;

② 將堆頂記錄和最後一個記錄交換位置,則前n-1個記錄是無序的,而最後一個記錄是有序的;

③ 堆頂記錄被交換後,前n-1個記錄不再是堆,需將前n-1個待排序記錄重新組織成為一個堆,然後將堆頂記錄和倒數第二個記錄交換位置,即將整個序列中次小關鍵字值的記錄調整(排除)出無序區;

④ 重復上述步驟,直到全部記錄排好序為止。


結論:排序過程中,若采用小根堆,排序後得到的是非遞減序列;若采用大根堆,排序後得到的是非遞增序列。

4.4 堆的調整——篩選


⑴ 堆的調整思想

輸出堆頂元素之後,以堆中最後一個元素替代之;然後將根結點值與左、右子樹的根結點值進行比較,並與其中小者進行交換;重復上述操作,直到是葉子結點或其關鍵字值小於等於左、右子樹的關鍵字的值,將得到新的堆。稱這個從堆頂至葉子的調整過程為“篩選”,如圖10-10所示。

注意:篩選過程中,根結點的左、右子樹都是堆,因此,篩選是從根結點到某個葉子結點的一次調整過程。


\

2.5 代碼實現:

//堆排序
#include 
#include 

#define SIZE 10

void HeapSort(int a[],int n)
{
    int i,j,h,k;
    int t;
    
    for (i = n/2-1; i >= 0; i--)
    {
        while (2*i + 1 < n)
        {
            j = 2*i + 1;
            if ((j+1) < n)
            {
                if (a[j] < a[j+1])
                {
                    j++;
                }
            }
            
            if (a[i]0; i--)
    {
        t = a[0];
        a[0] = a[i];
        a[i] = t;
        k =0;
        while (2*k+1




參考書籍:《C/C++常用算法手冊》 《數據結構-清華大學嚴蔚敏》

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