| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 893 人关注过本帖, 1 人收藏
标题:一些排序算法
只看楼主 加入收藏
zjl138
Rank: 1
等 级:新手上路
威 望:1
帖 子:788
专家分:0
注 册:2007-11-12
收藏(1)
 问题点数:0 回复次数:4 
一些排序算法
[size=2]写这个是为了提高自已对排序算法的理解,以前也有写,不过是分散写,没有像这样统一写在一个文件里.
这次没有写归并,基数排序,近期内再补上吧.
代码较长,不过比较容易看得懂,呵呵.发上来给大家批评指证吧.如果大家发现有什么问题,或觉得哪里应该改进,请回帖告诉我,感激万分.

本代码使用的高亮软件是雨中飞燕之作:"HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **"
[size=2]
[/color]#include<iostream>
#include<ctime>
#define Swap(i,j) {int s = (i); (i) = (j); (j) = s;}
const int MAXSIZE = 30;
int array[MAXSIZE];
/*直接插入排序
基本思想:当插入第I个元素时,前面的V[0],V[1]....V[I-1]已经排好序,这时用V[I]的排序码与
V[I-1],V[I-2]....的排序码进行比较,找到插入位置即将V[I]插入,原来位置上的元素向后移.
*/

void InsertSort(int (&array)[MAXSIZE],const int left,int const right)
{
   
for (int i=left+1;i<=right;i++)
    {
        
if (array[i] < array[i-1])
        {
            
int temp = array[i], j = i-1;
            do
            
{
               
array[j+1] = array[j]; j--;
            }
            
while (j >= left && temp < array[j]);
            array[j+1] = temp;
        }
    }
}

/*折半插入排序(二分法插入排序)
基本思想:设在数据表中有一个元素序列V[0],V[1]...V[n-1].其中V[0],V[1]...V[I-1]
是已经排好序的元素.在插入V[I]时,得用折半搜索寻找V[I]的插入位置.
*/

void BinaryInsertSort(int (&array)[MAXSIZE],int left,int right)
{
   
for (int i=left+1;i<=right;i++)
    {
        
int temp = array[i];
        while (left<=right)
        {
            
int middle = (left+right)/2;
            if (temp < array[i]) right = middle - 1;
            else left = middle + 1;
        }
        
for (int k=i-1;k>=left;k--) array[k+1] = array[k];
        array[left] = temp;
    }
}

/*希尔排序(SHELL SORT),又称缩小增量排序(diminishing-increment sort)
基本思想:设待排序元素序列有N个元素,首先取出一个整数gap<n作为间隔,将全部元素分为gap
个字序列,所有距离为gap的元素放在同一个子序列中,在每一个子序列中分别施行直接插入排序.
然后缩小间隔gap,直到gap等于 1
*/

void ShellSort(int (&array)[MAXSIZE],const int left,const int right)
{
   
int gap = right-left+1;     //增量的初始值
   
do
   
{
        
gap = gap/3 + 1;   // 求下一增量
        
for (int i=(left+gap);i<=right;i++)  //各子充列交错处理
            
if (array[i] < array[i-gap])    //逆序
            
{
               
int temp = array[i], j = i-gap;
                do
               
{
                    
array[j+gap] = array[j];     //后移元素
                    
j = j-gap;                   //现比较前一元素
               
}while (j>left &&temp < array[j]);
            }
    }
while (gap > 1);
}

/*快速排序
快速排序采用分治法(divide-and-conquer)进行排序.
基本思想:任取待排序元素序列中某个元素作基准,按照该元素排序码大小,将整个元素序列划分为左右两个
子序列,左侧都比基准元素小,右侧则大于或等于.然后分别对这两个子序列重复施行上述方法,直到所有的元素
都排在相应位置为止
*/

//快速排序的划分
int Partition(const int left,const int right)
{
   
int pivotpos = left,pivot = array[left];    //基准元素
   
for (int i=left+1;i<=right;i++)
        if (array[i] <pivot)
        {
            
pivotpos++;
            if (pivotpos != i) Swap(array[pivotpos],array[i]);
        }
   
array[left] = array[pivotpos];
    array[pivotpos] = pivot;
    return pivotpos;
}
//快速排序
void QuickSort(int(&array)[MAXSIZE],const int left,const int right)
{
   
if (right-left <= 25) InsertSort(array,0,MAXSIZE-1); //数据规模较小时,采用直接插入.
   
else
   
{
        
int pivotpos = Partition(left,right);
        QuickSort(array,left,pivotpos-1);
        QuickSort(array,pivotpos+1,right);
    }
}

//三路划分的快速排序算法
void Quick_Sort(int (&array)[MAXSIZE],int low,int high)
{
   
int pivot=array[low];
    if (low >= high) return;
    while (low<high)
    {
        
while (low<high && pivot<array[high]) high--;
        if (low<high)
        {
            
array[low]=array[high];
            low++;
        }
        
while (low<high && pivot>=array[low]) low++;
        if (low<high)
        {
            
array[high]=array[low];
            high++;
        }
    }
   
array[low]=pivot;
    Quick_Sort(array,low,low-1);
    Quick_Sort(array,low+1,high);
}

/*
选择排序
基本思想:每一趟(纺织品如第 I 趟,I = 0,1,2,...N-2)在后面 N-I个待排序元素中选出排序码
最小的元素,作为有序元素序列的第 I 个元素.待到第 N-2趟作完,待排序元素只剩下 1 个,就不用再选了.
*/
//直接选择排序
void SelectSort(int (&array)[MAXSIZE],const int left,const int right)
{
   
for (int i=left;i<right;i++)
    {
        
int k = i;
        for (int j=i+1;j<=right;j++)
            if (array[j] < array[k]) k = j;    //当前最小排序码的元素
        
if (k != i) Swap(array[i],array[k]);
    }
}
/*
堆排序
(1):根据初始输入数据,得用堆的调整算法SiftDown()形成堆
(2):通过一系列的元素交换和重新调整堆进行排序
*/
//堆调整
void MaxHeap_SiftDown(int (&heap)[MAXSIZE],const int start,const int end)
{
   
int i=start,temp = heap[start], j = 2*start + 1;
    while (j <= end)   //检查是否到最后位置
   
{
        
if (j < end && heap[j] < heap[j+1]) j++;
        if (temp >= heap[j]) break;
        else          //子女中大者上移
        
{
            
heap[i] = heap[j];
            i = j;     //i下降到子女位置
            
j = 2*j + 1;
        }
    }
   
heap[i] = temp;    //将temp中元素放到适合位置
}
//堆排序
void HeapSort(int (&heap)[MAXSIZE],const int size)
{
   
for (int i=(size-2)/2;i>=0;i--)
        MaxHeap_SiftDown(heap,i,size-i);
    for (int j=size-1;j>=0;j--)
    {
        
Swap(heap[0],heap[j]);
        MaxHeap_SiftDown(heap,0,j-1);
    }
}

//输出排序后的数列
void display(int (&array)[MAXSIZE],int size)
{
   
for (int i=0;i<size;i++)
    {
        
std::cout<<array[i]<<"  ";
        if ((i+1)%10 == 0) std::cout<<std::endl;
    }
}
int main(void)
{
   
srand(unsigned(time(NULL)));
    for (int i=0;i<MAXSIZE;i++)
        array[i] = rand()%10000;

    std::cout<<"***直接插入排序***"<<std::endl;
    InsertSort(array,0,MAXSIZE-1);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***折半插入排序(二分法插入排序)***"<<std::endl;
    BinaryInsertSort(array,0,MAXSIZE-1);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***希尔排序(SHELL SORT)***"<<std::endl;
    ShellSort(array,0,MAXSIZE);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***快速排序***"<<std::endl;
    QuickSort(array,0,MAXSIZE);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***三路划分的快速排序***"<<std::endl;
    Quick_Sort(array,0,MAXSIZE);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***直接选择排序***"<<std::endl;
    SelectSort(array,0,MAXSIZE);
    display(array,MAXSIZE);

    std::cout<<std::endl<<"***堆排序***"<<std::endl;
    HeapSort(array,MAXSIZE);
    display(array,MAXSIZE);
    return 0;
}

[/size][/size]

[[it] 本帖最后由 zjl138 于 2008-7-21 21:27 编辑 [/it]]
搜索更多相关主题的帖子: 算法 
2008-07-18 10:50
牧风
Rank: 1
等 级:新手上路
帖 子:17
专家分:0
注 册:2008-11-9
收藏
得分:0 
2008-11-23 16:00
Soul寂
Rank: 1
等 级:新手上路
帖 子:117
专家分:1
注 册:2008-9-29
收藏
得分:0 
好像就过了!

不要在你的智慧中夹杂傲慢,也不要使你们的谦卑缺乏智慧的成分!
2008-11-23 21:34
小小强12
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-11-22
收藏
得分:0 
很好,要是能够把这几种方法的比较也写出来就更好啦!!
2008-11-23 21:48
伤心小箭
Rank: 1
来 自:桂林
等 级:新手上路
帖 子:7
专家分:0
注 册:2008-11-24
收藏
得分:0 
先顶一下
2008-11-24 13:29
快速回复:一些排序算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.024753 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved