注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HongMain 的博客

关注编程技术: Linux, Windows, C/C++

 
 
 

日志

 
 
 
 

内排序常用算法  

2011-08-05 23:03:36|  分类: 编程语言(主要是 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

整理以前的学习笔记,有以下的代码片断:

 

// 内排序常用算法
// 在Microsoft Visual C++ .NET下编译通过
#include <iostream>
#include <tchar.h>

using namespace System;
//namespace sortProgram
//{
 const int MAXSIZE = 20;    // 假设的顺序表最大长度

 typedef int KeyType;    // 关键字类型 设定关键字为整型

 class RcdType
 {
 public:
    KeyType key;     // 关键字项
    // 其他项
 };

 // 顺序表类型
 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]; //设哨兵
     // 记录后移
     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) // 插入点在低半区
        high = m-1;
     else    //插入点在高半区
        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; // 一趟起泡后仍处于无序状态的最后一个记录的位置
 }
}

// *************************
// 快速排序
// *************************
// 对记录子序列 R[low...high] 进行一趟快速排序, 并返回枢轴记录所在位置
// 使得在它之前的记录的关键字均不大于它的关键字,
// 而在它之前的记录的关键字均不小于它的关键字
int Partition(RcdType R[], int low, int high)
{
 R[0] = R[low];    // 将枢轴记录移至数组的闲置分量
 KeyType pivotkey = R[low].key; // 枢轴记录关键字
 // 从表的两端交替地向中间扫描
 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]中选择关键字最小的记录
    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]中记录的关键字除H.r[s].key之外均满足堆的定义,
// 本函数依据关键字的大小对H.r[s]进行调整, 使H.r[s...m]成为一个大顶堆
void HeapAdjust(SqList &H, int s, int m)
{
 H.r[0] = H.r[s]; // 暂存根结点的记录
 // 沿关键字较大的孩子的结点向下筛选
 for (int j=2*s; j<=m; j*=2)
 {
    if (j<m && H.r[j].key<H.r[j+1].key)
     j++;    // j 为关键字较大的孩子记录的下标
    if (H.r[0].key >= H.r[j].key) break; // 不需要调整, 跳出循环
    H.r[s] = H.r[j];    // 将大关键字记录上调
    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); // 从根开始调整, 将H.r[1...i]重新调整为大顶堆
    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中记录按关键字从小到大地复制到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]复制到TR
 while (i<=m)
    TR[k++] = SR[i++];
 // 将剩余的SR[j...n]复制到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;
}

  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017