VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 995|回复: 3

[原创] 常见排序算法

[复制链接]
38_avatar_middle
在线会员 发表于 2016-11-21 14:17:06 | 显示全部楼层 |阅读模式
本帖最后由 zhaisiyu 于 2016-11-21 14:34 编辑

/**
*简单数据交换函数
*/
void swapInt(int indexOne,int indexTwo,int* ary)
{
        int tempVal = ary[indexOne];
        ary[indexOne] = ary[indexTwo];
        ary[indexTwo] = tempVal;
}

/**
*插入排序
*/
void insterSort(int length,int* ary)
{
        for (int i = 1; i < length; i++)
        {
                for (int j = i; j > 0 && ary[j] < ary[j-1]; j--)
                {
                        swapInt(j,j-1,ary);
                }
        }
}

/*
*希尔排序
*/
void shellSort(int length,int* ary)
{
        for (int step = length / 2; step > 0; step /=2)
        {
                for (int i = 0;i < step - 1;i++)
                {
                        for (j = i; j >= 0 && ary[j] > ary[j + step]; j -= step)
                        {
                                swapInt(j,j + step,ary);
                        }
                }
        }
}

/**
*冒泡排序
*/
void bublleSort(int length,int* ary)
{
        for (int i = 0;i<length-1;i++)
        {
                for (int j = 0;j<length - i -1;j++)
                {
                        if (ary[j] > ary[j+1])
                        {
                                swapInt(j,j+1,ary);
                        }
                }
        }
}

/**
*快速排序
*/
void quickSort(int beginIndex,int endIndex,int* ary)
{
        if (beginIndex > endIndex)
                return;
        int frist = beginIndex;
        int last = endIndex;
        int markVal = ary[beginIndex];
        while (beginIndex < endIndex)
        {
                while(beginIndex < endIndex && ary[endIndex] > markInt)
                {
                        --endIndex;
                }
                ary[beginIndex] = ary[endIndex];
               
                while(beginIndex < endIndex && markVal <= ary[beginIndex])
                {
                        ++beginIndex;
                }
                ary[endIndex] = ary[beginIndex];
        }
        ary[beginIndex] = markVal;
        quickSort(frist,beginIndex-1,ary);
        quickSort(beginIndex + 1,last,ary);
}

/**
*选择排序
*/
void selectSort(int length,int* ary)
{
        for (int i = 0;i<length-1;i++)
        {
                int maxIndex = 0;
                for (int j = 1;j<length - i -1;j++)
                {
                        if (ary[j] > ary[maxIndex])
                        {
                                maxIndex = j;
                        }
                }
                swapInt(maxIndex,length - i -1,ary);
        }
}

/**
*堆排序
*/
void heapAdjust(int rootIndex ,int length,int* ary)
{
        int tempRootIndex = rootIndex;
        int lChildIndex = tempRootIndex * 2 + 1;
        int rChildIndex = lChildIndex + 1;
        int largestIndex = 0;
        while(lChildIndex < length)
        {
                rChildIndex = lChildIndex + 1;
                if (rChildIndex < length && ary[rChildIndex] > ary[lChildIndex])
                        largestIndex = rChildIndex;
                else
                        largestIndex = lChildIndex;
               
                if (ary[tempRootIndex] > ary[largestIndex])
                        break;
               
                swapInt(largestIndex,tempRootIndex,ary)
               
                tempRootIndex = largestIndex;
                lChildIndex = tempRootIndex * 2 + 1;
        }
}

void heapSort(int length,int* ary)
{
        //(i-1)/2求i的根
        for (int i = (length-2) / 2;i>=0;i--)
                heapAdjust(i,length,ary);
       
        for (int j = 0;j<length;j++)
        {
                swapInt(0,length - j - 1,ary);
                heapAdjust(0,length - j - 1,ary);
        }
}

/**
*计数排序
*/
void countSort(int length,int* ary,int maxNum)
{
        int* sortAry = new int[length];
        int* countAry = new int[maxNum];
        for (int i = 0;i<length;i++)
        {
                ++countAry[ary];
        }
        for (int i= 1;i<maxNum;i++)
        {
                countAry += countAry[i-1];
        }
        for(int i=length-1;i>=0;--i)
        {
                sortAry[--countAry[ary]] = ary;
        }
        for (int i = 0;i<length;i++)
        {
                ary = sortAry;
        }
        delete countAry;
        delete sortAry;
}

void maxBitFunc(int length,int* ary)
{
        int maxBit = 1;
        for (int i = 0;i <length;i++)
        {
                int tempBit = ary/10 + 1;
                if(maxBit < tempBit)
                {
                        maxBit = tempBit;
                }
        }
        return maxBit;
}

/**
*基数排序
*/
void radixSort(int length,int* ary)
{
        int maxBit = maxBitFunc(length,ary);
        int* sortAry = new int[length];
        int* countAry = new int[10];
        int radix = 1
        for (int i = 0;i<maxBit;i++)
        {
                for(int j = 0;j<10;j++)
                {
                        countAry[j] = 0;
                }
               
                for (int j = 0;j < length;j++)
                {
                        int k = (ary[j] / radix) % 10;
                        countAry[k]++;
                }
               
                for (int j = 1;j<10;j++)
                {
                        countAry[j]+= countAry[j-1];
                }
               
                for (int j = length - 1;j>=0;j++)
                {
                        int k = (ary[j] / radix) % 10;
                        sortAry[countAry[k]--] = ary[j];
                }
               
                for (int j = 0;j < length;j++)
                {
                        ary[j] = sortAry[j];
                }
        }
        delete countAry;
        delete sortAry;
}

/**
*归并排序
*/
void merge(int* ary,int* tempAry,int beginIndex,int midIndex,int endIndex)
{
        int frist1Index = beginIndex, frist2Index = midIndex + 1,tempIndex;
        while(frist1Index != midIndex && frist2Index != endIndex)
        {
                if (ary[frist1Index] > ary[frist2Index])
                {
                        tempAry[tempIndex++] = ary[frist2Index++];
                }
                else
                {
                        tempAry[tempIndex++] = ary[frist1Index++];
                }
        }
       
        while(frist1Index != midIndex)
        {
                tempAry[tempIndex++] = ary[frist1Index++];
        }
       
        while(frist2Index != endIndex)
        {
                tempAry[tempIndex++] = ary[frist2Index++];
        }
       
        for (int i = beginIndex;i<= endIndex;i++)
        {
                ary = tempAry;
        }
}

void mergeSort(int beginIndex,int endIndex,int* ary,int* tempAry)
{
        if (beginIndex < endIndex)
        {
                int midIndex = (beginIndex + endIndex) / 2;
                mergeSort(beginIndex,midIndex,ary,tempAry);
                mergeSort(midIndex+1,endIndex,ary,tempAry);
                merge(ary,tempAry,beginIndex,midIndex,endIndex);
        }
}




上一篇:数据结构表达式求值问题
下一篇:数据结构 修路问题
52_avatar_middle
在线会员 发表于 2016-11-21 20:05:41 | 显示全部楼层
这个很不错,比其他帖子的东西好很多。
75_avatar_middle
在线会员 发表于 2016-12-15 22:02:41 | 显示全部楼层
ccccccccccccccccccccccc
31_avatar_middle
在线会员 发表于 2017-2-6 08:44:09 | 显示全部楼层
这个还不错
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2019-3-20 01:50

Powered by Discuz! X3.4

© 2009-2019 cctry.com

快速回复 返回顶部 返回列表