思勤無邪

上學時，因我年齡最小，個頭也最小，上課時，就像大猩猩堆里的猴一般。如今，這猴偶爾也把最近的一些情況寫在這里。

:: 首頁 :: 聯(lián)系 :: 聚合

:: 管理

132 Posts :: 1 Stories :: 178 Comments :: 0 Trackbacks

公告

吾日常三省吾身，曰思、曰勤、曰無邪。

隨筆分類(130)

隨筆檔案(132)

文章檔案(1)

2006年6月 (1)

相冊

積分與排名

積分 - 187326
排名 - 140

閱讀排行榜

評論排行榜

內(nèi)排序常用算法

整理以前的學習筆記，有以下的代碼片斷：

// 內(nèi)排序常用算法
// 在Microsoft Visual C++ .NET下編譯通過
#include <iostream>
#include <tchar.h>

using namespace System;
//namespace sortProgram
//{
const int MAXSIZE = 20; // 假設(shè)的順序表最大長度

typedef int KeyType; // 關(guān)鍵字類型設(shè)定關(guān)鍵字為整型

class RcdType
{
public:
KeyType key; // 關(guān)鍵字項
// 其他項
};

// 順序表類型
class SqList
{
public:
RcdType r[MAXSIZE+1]; // r[0]閑置或作為判別標志的"哨兵"單元
int length; // 順序表長度
};
//}

// *************************
// 直接插入排序
// *************************
void InsertSort(SqList &L)
{
for (int i=2; i<=L.length; i++)
{
    if (L.r[i].key < L.r[i-1].key) // 將L.r[i]插入有序表
    {

     L.r[0] = L.r[i]; //設(shè)哨兵
     // 記錄后移
     L.r[i] = L.r[i-1];
     for (int j=i-2; L.r[0].key < L.r[j].key; j--)
     {
        L.r[j+1] = L.r[j];
     }
     // 插入到正確位置
     L.r[j+1] = L.r[0];
    }
    int x = L.r[i].key;
}
}

// *************************
// 折半插入排序
// *************************
void BInsertSort(SqList &L)
{
for (int i=2; i<=L.length; i++)
{
    L.r[0] = L.r[i]; //將L.r[i]暫存到r[0]
    int low = 1;
    int high = i-1;
    // 在r[low...high]中折半查找有序插入位置
    while (low <= high)
    {
     int m = (low+high)/2; // 折半
     if (L.r[0].key < L.r[m].key) // 插入點在低半?yún)^(qū)
        high = m-1;
     else    //插入點在高半?yún)^(qū)
        low = m+1;
    }
    // 記錄后移
    for (int j=i-1; j>=low; j--)
     L.r[j+1] = L.r[j];
    // 插入
    L.r[high+1] = L.r[0];
}
}

// *************************
// 希爾排序
// *************************
// 對順序表L作一趟增量為dk的希爾排序
void ShellInsert(SqList &L, int dk)
{
for (int i=dk+1; i<=L.length; i++)
{
    if (L.r[i].key < L.r[i-dk].key) // 將L.r[i]插入有序子表
    {
     L.r[0] = L.r[i];
     L.r[i] = L.r[i-dk];
     for (int j=i-2*dk; j>0 && L.r[0].key<L.r[j].key; j-=dk)
        L.r[j+dk] = L.r[j];    //記錄后移
     L.r[j+dk] = L.r[0];    // 插入到正確位置
    }
}
}
// 按增量序列dlta[0...t-1]對順序表L作希爾排序
void ShellSort(SqList &L, int dlta[], int t)
{
for (int k=0; k<t; k++)
{
    ShellInsert(L, dlta[k]);
}
}

// *************************
// 起泡排序
// *************************
void BubbleSort(SqList &L)
{
for (int i=L.length, bool change = true; i>1 && change; --i)
{
    change = false;
    for (int j=1; j<i; j++)
    {
     if (L.r[j].key > L.r[j+1].key)
     {
        L.r[0] = L.r[j];
        L.r[j] = L.r[j+1];
        L.r[j+1] = L.r[0];
        change = true;
     }
    }
}
}

// *************************
// 起泡算法的改進
// *************************
// 記下最后進行交換的記錄的位置
// 在此位置之后的記錄已是有序, 不必進行比較
void BubbleSort_(SqList &L)
{
int i = L.length;
while (i > 1) // i>1 表明上一趟曾進行過記錄的交換
{
    int lastExchangeIndex = 1;
    for (int j=1; j<i; j++)
    {
     if (L.r[j+1].key < L.r[j].key)
     {
        // 互換記錄
        L.r[0] = L.r[j];
        L.r[j] = L.r[j+1];
        L.r[j+1] = L.r[0];
        lastExchangeIndex = j; // 記下進行交換的記錄的位置
     }
    }
    i = lastExchangeIndex; // 一趟起泡后仍處于無序狀態(tài)的最后一個記錄的位置
}
}

// *************************
// 快速排序
// *************************
// 對記錄子序列 R[low...high] 進行一趟快速排序, 并返回樞軸記錄所在位置
// 使得在它之前的記錄的關(guān)鍵字均不大于它的關(guān)鍵字,
// 而在它之前的記錄的關(guān)鍵字均不小于它的關(guān)鍵字
int Partition(RcdType R[], int low, int high)
{
R[0] = R[low];    // 將樞軸記錄移至數(shù)組的閑置分量
KeyType pivotkey = R[low].key; // 樞軸記錄關(guān)鍵字
// 從表的兩端交替地向中間掃描
while (low<high)
{
    while (low<high && R[high].key >=pivotkey)
     high--;
    if (low != high) R[low++] = R[high];    // 將比樞軸記錄大的記錄移到高端
    while (low<high && R[low].key<=pivotkey)
     low++;
    if (low < high) R[high--] = R[low];    // 將比樞軸記錄大的記錄移到高端
}
R[low] = R[0];     // 樞軸記錄移到正確位置
return low;     // 返回樞軸位置
}
// 對記錄序列 R[s...t] 進行快速排序
void QSort(RcdType R[], int s, int t)
{
if (s < t)
{
    int pivotloc = Partition(R, s, t);    // 對 R[s...t] 進行一趟快排, 并返回樞軸位置
    QSort(R, s, pivotloc-1); // 對低子序列遞歸進行排序
    QSort(R, pivotloc+1, t); // 對高子序列遞歸進行排序
}
}
// 對順序表 L 進行快速排序
void QuickSort(SqList &L)
{
QSort(L.r, 1, L.length);
}

// *************************
// 簡單選擇排序
// *************************
void SelectSort(SqList &L)
{
// 選擇第 i 小的記錄, 并交換到位
for (int i=1; i<L.length; i++)
{
    int j = i;
    // 在L.r[i...L.length]中選擇關(guān)鍵字最小的記錄
    for (int k=i+1; k<=L.length; k++)
    {
     if (L.r[k].key < L.r[j].key)
        j = k;
     if (i!=j) // 與第 i 個記錄互換
     {
        L.r[0] = L.r[i];
        L.r[i] = L.r[j];
        L.r[j] = L.r[0];
     }
    }
}
}

// *************************
// 堆排序(大頂堆)
// *************************
// 已知H.r[s...m]中記錄的關(guān)鍵字除H.r[s].key之外均滿足堆的定義,
// 本函數(shù)依據(jù)關(guān)鍵字的大小對H.r[s]進行調(diào)整, 使H.r[s...m]成為一個大頂堆
void HeapAdjust(SqList &H, int s, int m)
{
H.r[0] = H.r[s]; // 暫存根結(jié)點的記錄
// 沿關(guān)鍵字較大的孩子的結(jié)點向下篩選
for (int j=2*s; j<=m; j*=2)
{
    if (j<m && H.r[j].key<H.r[j+1].key)
     j++;    // j 為關(guān)鍵字較大的孩子記錄的下標
    if (H.r[0].key >= H.r[j].key) break; // 不需要調(diào)整, 跳出循環(huán)
    H.r[s] = H.r[j];    // 將大關(guān)鍵字記錄上調(diào)
    s = j;
}
H.r[s] = H.r[0]; // 回移篩選下來的記錄
}
// 對順序表H進行堆排序
void HeapSort(SqList &H)
{
// 將 H 建成大頂堆
for (int i=H.length/2-1; i>0; i--)
{
    HeapAdjust(H, i, H.length);
}
// 互換"堆頂"和"堆底"的記錄
H.r[0] = H.r[1];
H.r[1] = H.r[H.length];
H.r[H.length] = H.r[0];
for (int i=H.length-1; i>1; i--)
{
    HeapAdjust(H, 1, i); // 從根開始調(diào)整, 將H.r[1...i]重新調(diào)整為大頂堆
    H.r[0] = H.r[1];
    H.r[1] = H.r[i];
    H.r[i] = H.r[0];
}
}

// *************************
// 2-路歸并排序
// *************************
// 將有序的SR[i...m]和SR[m+1...n]歸并為有序的TR[i...n]
void Merge(RcdType SR[], RcdType TR[], int i, int m, int n)
{
int j, k;
// 將SR中記錄按關(guān)鍵字從小到大地復(fù)制到TR中
for (j=m+1, k=i; i<=m && j<=n; k++)
{
    if (SR[i].key <= SR[j].key)
     TR[k] = SR[i++];
    else
     TR[k] = SR[j++];
}
// 將剩余的SR[i...m]復(fù)制到TR
while (i<=m)
    TR[k++] = SR[i++];
// 將剩余的SR[j...n]復(fù)制到TR
while (j<=n)
    TR[k++] = SR[j++];
}
// 對SR[s...t]進行歸并排序, 排序后的記錄存入TR1[s...t]
void MSort(RcdType SR[], RcdType TR1[], int s, int t)
{
if (s == t)
    TR1[s] = SR[s];
else
{
    int m = (s+t)/2;    // 將SR[s...t]平分平SR[s...m] 和 SR[m+1...t]
    RcdType *TR2 = new RcdType[MAXSIZE+1];
    MSort(SR, TR2, s, m);    // 遞歸地將 SR[s...m]歸并為有序的TR2[s...m]
    MSort(SR, TR2, m+1, t);    // 遞歸地將SR[m+1...m]歸并為有序列的TR2[m+1...t]
    Merge(TR2, TR1, s, m, t); // 將TR2[s...m]和TR2[m+1...t]歸并到 TR1[s...t]
    delete[] TR2;
}
}
// 對順序表作2-路歸并排序
void MergeSort(SqList &L)
{
MSort(L.r, L.r, 1, L.length);
}

void _tmain()
{
SqList sqList;
sqList.length = MAXSIZE;
Random* random = new Random;
for (int i=1; i<(MAXSIZE+1); i++)
{
    sqList.r[i].key = random->Next(100);
}
//delete random;
std::cout << "排序前的順序表:\n";
for (int i=1; i<(MAXSIZE+1); i++)
{
    std::cout << sqList.r[i].key << " ";
}
std::cout << '\n';
//InsertSort(sqList); //直接插入排序
//BInsertSort(sqList); // 折半插入排序
// 希爾排序
//int dlta[] = {9, 5, 3, 2, 1};
//ShellSort(sqList, dlta, 5);
// 起泡排序
//BubbleSort(sqList);
//BubbleSort_(sqList);
// 快速排序
//QuickSort(sqList);
// 簡單選擇排序
//SelectSort(sqList);
// 堆排序
//HeapSort(sqList);
// 歸并排序
MergeSort(sqList);
std::cout << "排序后的順序表:\n";
for (int i=1; i<(MAXSIZE+1); i++)
{
    std::cout << sqList.r[i].key << " ";
}
std::cout << '\n';
int x;
std::cin>>x;
}

posted on 2006-05-31 17:26 思勤無邪閱讀(289) 評論(0) 編輯收藏引用所屬分類: C++

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: 網(wǎng)上看到的一個面試題：利用星號輸出畫一個任意大小的圓聊聊封裝、繼承 C++的底層機制 This case pointers cannot be used 被誤解的C++ 一個簡單的不依靠MFC的面向?qū)ο蟮腤indows程序什么是高級C++？ Ruminations on C++ 中的代理類Demo 類廠和COM類的關(guān)系使用IDropTarget接口同時支持文本和文件拖放（轉(zhuǎn)）

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品