高薪算法+计算机职称考试数据结构和算法程序书海

C/C++十大排序大总结（完结）

2016-11-22  本文已影响2953人  Juinjonn

个人介绍及问题解决

BubbleSort（冒泡排序）

定义：在同一个数组中，从数组第一个数开始，相邻两个数进行比较，按照小左大右或者大右小左的顺序，依次循环遍历，进行排序！

void BubbleSort(int *arr,int Length)
{
    int i = 0;
    int j = 1;
    int sys = 0;
    for (i = 0; i < Length-1; i++)
    {
        for (j = 0; j < Length-i-1; j++)
        {
            if (arr[j]>arr[j+1])
            {
                arr[j] = arr[j]^arr[j+1];
                arr[j+1] = arr[j]^arr[j+1];
                arr[j] = arr[j]^arr[j+1];
            }

        }
        sys++;
    }

    return ;
}

改进版冒泡排序

在原有的基础上，我们添加了标记！记录了最后一次交换的位置！
如5，1，4，6，3，2，7，8，9。最后一次交换的位置在2处，并且设定我们每次循环的到2，不对7，8，9
进行比较，节省我们运算的效率！

冒泡排序是对全部已经排好序列排序最快的

void BetterBubbleSort(int *arr,int Length)
{
    int i = 0;
    int j = 1;
    int pmark;
    int sys = 0;
    for (; i < Length-1; i++)
    {
        pmark = 0;
        for (j = 0; j < Length-i-1; j++)
        {
            if (arr[j]>arr[j+1])
            {
                arr[j] = arr[j]^arr[j+1];
                arr[j+1] = arr[j]^arr[j+1];
                arr[j] = arr[j]^arr[j+1];
                pmark = j+1;
            }

        }

        i == Length - pmark - 1;
        sys++;
    }

    return ;
}

不带中间变量实现两个相同类型不同值变量间的互换

  1. 加减法
int a = 5;
int b = 3;
a = a+b;
b = a-b;
a = a-b;
  1. 异或^
int a = 5;
int b = 3;
a = a^b;
b = a^b;
a = a^b;

ps:若对于*a，*b值进行交换，*a，*b不能指向同一块地址空间！

SelectSort选择排序

首先，用第一个数去和所有数进行比较，选出其中最小的数，放在第一位，在用第二个数去和全部数进行比较，最小的放在第二位，依次循环遍历！

void SelectSort(int *Arr,int nLength)
{
    int i = 0;
    int j = 1;
    int min = 0;
    for (i = 0; i < nLength; i++)
    {
        for (j = i; j < nLength-1; j++)
        {
            if (Arr[i] > Arr[j])
            {
                Arr[j] = Arr[j]^Arr[i];
                Arr[i] = Arr[j]^Arr[i];
                Arr[j] = Arr[j]^Arr[i];
            }
        }
    }
}

代码优化：把每次都交换的位置，换成比较完之后，有一个int记下来，不用每次比较完进行交换，而是最后直接用记录的数组下标进行交换！

InsertSort插入排序

把当前数组分成两部分，第一部分有序，第二部分无序，将无序数组依次插入有序数组里去！
例如数组：10，20，3，8，55.用一个temp保存无序数组第一个

适合场景：每个元素距离其最终位置不远时，我们选择插入排序。

  1. 首先把10当成有序数组的最后一位，20当成无序数组的第一位，20和10比较，20比10大不移动。
  2. 之后用无序数组向后移动一位，变成3，3和20比较，比20小，把3放10和20中间，在用3和10比，比10小，放10前面。
  3. 此时有序最后一位仍是20，用8再去和前面几位有序数组进行比较，一次循环遍历！
void InsertSort(int arr[],int nLength)
{
    int j;//有序数组的最后位置
    int i;//无序数组的第一个
    int temp;

    if(arr == NULL || nLength <=0)return;

    for(i = 1;i<nLength;i++)
    {
        j = i-1;
        temp = arr[i]; //保存无序数组的第一个

        //进行比较
        while(temp < arr[j] && j >=0)
        {
            //将前一个元素向后移动 
            arr[j+1] = arr[j];
            j--;
        }

        //将元素放入其对应位置
        arr[j+1] = temp;
    }

}

快排

快排的优点：是比较次数最少的排序！

挖坑填补法

例如数组：7，2，8，4，3，5。我们用temp标记7

  1. 我们将第一数7当标准值，此时相当于7是一个坑（用粗斜体标记），然后我们从后面依次找比标准值7小的数，
    第一个5就比7小，我们将5放到7的坑里。数组变成5，2，8，4，3，7，这是坑变成最后位数！
  2. 然后我们在前面找一个比标准值大的数，第3个数8比标准值大，这是我们将8填到数7的坑里！这是数组变成了：
    5，2，7，4，3，8，我们对已经操作的数，不再进行考虑比较！
  3. 这时我们在从前面开始找一个数比标准值小的数3，填坑。数组变成了：2，3，4，7，8，此时前面和后面的数，
    皆比标准值小和大！
  4. 标准值前面的数我们看做一个区域，标准值后面的数我们看成一个区域。依次递归循环此区域。
//挖坑填补法 
int Sort(int arr[],int nLow,int nHigh)
{
    int temp ;
    temp = arr[nLow]; //保存标准值

    while(nLow < nHigh)
    {
        //从后向前找比标准值小的
        while( nLow < nHigh)
        {
            if(arr[nHigh] > temp)
            {
                nHigh--;
            }

            //小的放前面
            else
            {
                arr[nLow] = arr[nHigh];
                nLow++;
                break;
            }
        }

        //从前往后找比标准值大的
        while(  nLow < nHigh)
        {
            if(arr[nLow] < temp)
            {
            nLow++;
            }
            //大的放后面
            else
            {
                arr[nHigh] = arr[nLow];
                nHigh--;
                break;
            }
        }
    }

    //填坑
    arr[nLow] = temp;
    return nLow;
}
void QuickSort(int arr[],int nLow,int nHigh)
{
    int nIndex;
    if(arr == NULL )return;
    if(nLow < nHigh)
    {
        //找到标准值位置
        nIndex = Sort(arr,nLow,nHigh);

        //根据标准值将当前数组分割成两部分
        Sort(arr,nLow,nIndex-1);
        Sort(arr,nIndex+1,nHigh);
    }
}

区间（域）分割法

快排的一种，比挖坑填补法快！类似与挖坑填补法，是其优化升级版吧！
例如，数组：7，5，4，3，6

  1. 我们选最后一个数6作为标准值，有两个标记，一个是循环标记I，一个是区域标记s。s= i - 1
    s用黄体标记，i用粗斜体标记！s，7，5，4，3，6
  2. 用数6去和第一个数7比较，比标准值大，7,5,4，3，6，则将遍历元素移动到下一处，比标准值6小，
    则将数5和7交换，5，7，4，3，6。
  3. 将遍历指针指下一处，5，7，4，3，6，比标准值小，将4和第二个数交换。5，4，7，3，6
    移动遍历指针，5，4，7，3，6
  4. 比标准值小，将3和第三个数交换。5，4，3，7，6，移动遍历指针。5，4，3，7，6
  5. 这时遍历结束，判断++s与i是否相等，若不等，5，4，3，7，6，数组[s]与数组[i]交换。
  6. 5，4，3，6，7，此时标准值6前小后大，递归遍历！
//区间分割法
int Sort(int arr[],int nLow,int nHigh)
{
    int nSmall;//小区间的右边界
    nSmall = nLow-1;
    for(nLow;nLow < nHigh;nLow++)
    {
        //和标准值进行比较
        if(arr[nLow] < arr[nHigh])
        {
            //扩张小区间
            if(++nSmall != nLow)
            {
                arr[nSmall] = arr[nSmall] ^ arr[nLow];
                arr[nLow] = arr[nSmall] ^ arr[nLow];
                arr[nSmall] = arr[nSmall] ^ arr[nLow];
            }
        }
    }

    //标准值放入对应位置
    if(++nSmall != nHigh)
    {
        arr[nSmall] = arr[nHigh] ^ arr[nSmall];
        arr[nHigh] = arr[nHigh] ^ arr[nSmall];
        arr[nSmall] = arr[nHigh] ^ arr[nSmall];
    }

    return nSmall;
}

void QuickSort(int arr[],int nLow,int nHigh)
{
    int nIndex;
    if(arr == NULL )return;
    if(nLow < nHigh)
    {
        //找到标准值位置
        nIndex = Sort(arr,nLow,nHigh);

        //根据标准值将当前数组分割成两部分
        QuickSort(arr,nLow,nIndex-1);
        QuickSort(arr,nIndex+1,nHigh);
    }
}

快排区间分割优化

若我们选择的标准值恰好是最小值或者最大值，这是快排发生交换的次数最多，如果我们在选择下标的时候进行优化，
我们用随机数选择3个下标，之后选其中位数，会最大限度的减少极值下标的可能！

//找中间值下标
int GetIndex(int arr[],int nLow,int nHigh)
{
    int a,b,c;
    srand(time(NULL));

    //随机出三个在下标范围之内的下标
    a = rand()%(nHigh-nLow+1) + nLow;
    b = rand()%(nHigh-nLow+1) + nLow;
    c = rand()%(nHigh-nLow+1) + nLow;

    //找到三个的中间值
    if(arr[a] > arr[b])
    {
        if(arr[b] > arr[c])
            return b;
        else
        {
            if(arr[a] < arr[c])
                return a;
            else
                return c;
        }       
    }
    else
    {
        if(arr[a] > arr[c])
            return a;
        else
        {
            if(arr[b] < arr[c])
                return b;
            else
                return c;
        }
    }
}

//区间分割法
int Sort(int arr[],int nLow,int nHigh)
{
    int nSmall;//小区间的右边界
    int nIndex;
    nSmall = nLow-1;

    //降低标准值是最大最小值得概率
    nIndex = GetIndex(arr,nLow,nHigh);
    if(nIndex != nHigh)
    {
        arr[nIndex] = arr[nIndex] ^ arr[nHigh];
        arr[nHigh] = arr[nIndex] ^ arr[nHigh];
        arr[nIndex] = arr[nIndex] ^ arr[nHigh];
    }

    for(nLow;nLow < nHigh;nLow++)
    {
        //和标准值进行比较
        if(arr[nLow] < arr[nHigh])
        {
            //扩张小区间
            if(++nSmall != nLow)
            {
                arr[nSmall] = arr[nSmall] ^ arr[nLow];
                arr[nLow] = arr[nSmall] ^ arr[nLow];
                arr[nSmall] = arr[nSmall] ^ arr[nLow];
            }
        }
    }

    //标准值放入对应位置
    if(++nSmall != nHigh)
    {
        arr[nSmall] = arr[nHigh] ^ arr[nSmall];
        arr[nHigh] = arr[nHigh] ^ arr[nSmall];
        arr[nSmall] = arr[nHigh] ^ arr[nSmall];
    }

    return nSmall;
}

void QuickSort(int arr[],int nLow,int nHigh)
{
    int nIndex;
    if(arr == NULL )return;
    if(nLow < nHigh)
    {
        //找到标准值位置
        nIndex = Sort(arr,nLow,nHigh);

        //根据标准值将当前数组分割成两部分
        QuickSort(arr,nLow,nIndex-1);
        QuickSort(arr,nIndex+1,nHigh);
    }
}

快排终极优化

如果数量过少时，直接采用插入排序！

CountSort计数排序

基于非比较排序
适用场景：数据分配非常密集的时候！
例如数组：2，1，3，1，2，2，3，4

  1. 首先在数组中找到最大值和最小值。
  2. 然后申请一个max-min+1的数组空间。
  3. 遍历数组，如第一个数2，就在申请的数组空间下标为2-最小值的位置+1。
    相当于在申请的数组第2个位置，计数加一，每次遇到相同的值都加一。
  4. 相当于在申请的数组空间对应下标对应着参数数组中的值，记录其出现的次数。
  5. 遍历申请的数组空间，对应着下标将值依次存入参数数组。
void CountSort(int arr[],int nLength)
{
    int *pCount = NULL;
    int i;
    int j;
    int nMin,nMax;

    if(arr == NULL || nLength <=0)return;

    //找最大值和最小值
    nMax = arr[0];
    nMin = arr[0];
    for(i = 1;i<nLength;i++)
    {
        if(arr[i] > nMax)
        {
            nMax = arr[i];
        }
        if(arr[i] < nMin)
        {
            nMin = arr[i];
        }
    }
    //开辟计数数组
    pCount = (int *)malloc(sizeof(int ) * (nMax-nMin+1));
    memset(pCount,0,sizeof(int ) * (nMax-nMin+1));
    //计数
    for(i = 0;i<nLength;i++)
    {
        pCount[arr[i]-nMin]++;
    }
    //放回原数组
    j = 0;
    for(i = 0;i< nMax-nMin+1;i++)
    {
        while(pCount[i] != 0)
        {
            arr[j] = i+nMin;
            j++;
            pCount[i]--;
        }
    }
}

ShellSort希尔排序

插入排序的优化，按步长进行分组，然后在组内进行插入排序，然后在二分法步长，重复此过程。（ps:不一定要二分步长）

使用场景：数据少的时候！

例如：35，5，9，12，21，8，7，4，13，25，21，14，长度，n

  1. 第一次：$ gap=\displaystyle\frac{n}{2}=6 $，也就是说差6为一组，35和7一组，5和4，9和13，12和25，21和21，8和14。
    每组内进行插入排序，所以35和7互换位置，5和3互换位置。数组：7，4，9，12，21，8，33，5，13，25，21，14
  2. 第二次：$ gap=\displaystyle\frac{gap}{2}=3 $，差3为一组，7，12，33，25一组，4，21，5，21一组，9，8，13，14一组。每组内进行插入排序，25和33换，31和5换。数组：7，4，8，12，5，9，25，21，13，33，21，14
  3. 第三次：$ gap=\displaystyle\frac{gap}{2}=1 $向下取整。所以直接对整个数组进行一次插入排序。
  4. 总结：每次进行组内的插入排序，都是为了让元素距其最终位置更近一步！
void ShellSort(int arr[],int nLength)
{
    int gap;
    int i; //小组
    int j;//插入排序
    int k;
    int temp;//保存无序数组的第一个

    if(arr == NULL || nLength <=0)return;

    //定步长
    for(gap = nLength/2 ; gap >0 ; gap/=2)
    {
        //按照步长分组
        for(i = 0;i<gap;i++)
        {
            //各组内部插入排序
            for(j = i+gap;j<nLength;j+=gap)
            {
                k = j - gap; //有序数组的最后一个
                temp = arr[j]; //无序数组的第一个

                while(arr[k] > temp && k >=i)
                {
                    arr[k +gap] = arr[k];
                    k-=gap;
                }
                arr[k+gap] = temp;
            }
        }
    }
}

希尔排序的优化

分组时，让各组一起进行插入排序，都只进行一次，然后循环进行，代码看起来简洁，但是实际耗时基本相同！

void ShellSort2(int arr[],int nLength)
{
    int gap;
    int i; //小组
    int j;//插入排序
    int k;
    int temp;//保存无序数组的第一个

    if(arr == NULL || nLength <=0)return;

    //定步长
    for(gap = nLength/2 ; gap >0 ; gap/=2)
    {
        for(i = gap;i<nLength;i++)
        {
            //各组内部插入排序
                k = i - gap; //有序数组的最后一个
                temp = arr[i]; //无序数组的第一个

                while(arr[k] > temp && k >=0)
                {
                    arr[k +gap] = arr[k];
                    k-=gap;
                }
                arr[k+gap] = temp;
        }
    }
}

MergeSort归并排序

先拆分再合并。有2路，3路，5路等，这里用2路作为举例说明。先将数组按照二分法（2路）进行递归拆分，
拆分到每个块里只剩一个元素，然后和相邻元素进行比较排序合并，在比较在合并。

流程

Alt text 
void Merge(int arr[],int nLow,int nHigh)
{
    int nBegin1;
    int nEnd1;
    int nBegin2;
    int nEnd2;
    int *pTemp = NULL;
    int i;

    nBegin1 = nLow;
    nEnd1 = (nLow+nHigh)/2;
    nBegin2 = nEnd1+1;
    nEnd2 = nHigh;

    pTemp = (int *)malloc(sizeof(int ) *(nHigh-nLow+1));

    //合并
    i = 0;
    while(nBegin1 <=nEnd1 && nBegin2 <= nEnd2)
    {
        if(arr[nBegin1] < arr[nBegin2])
        {
            pTemp[i] = arr[nBegin1];
            nBegin1++;
        }
        else
        {
            pTemp[i] = arr[nBegin2];
            nBegin2++;  
        }
        i++;
    }

    //将有剩余的数组元素放入临时数组
    while(nBegin1 <= nEnd1)
    {
        pTemp[i] = arr[nBegin1];
        i++;
        nBegin1++;
    }

    while(nBegin2 <= nEnd2)
    {
        pTemp[i] = arr[nBegin2];
        i++;
        nBegin2++;
    }

    //将临时数组元素放回原数组
    for(i = 0;i < nHigh-nLow +1;i++ )
    {
        arr[i+nLow] = pTemp[i];
    }

    //释放
    free(pTemp);
    pTemp = NULL;

}

void MergeSort(int arr[],int nLow,int nHigh)
{
    int nMid;
    if(arr == NULL )return;

    //两路归并
    nMid = (nLow + nHigh)/2;

    if(nLow < nHigh)
    {
        //先拆分 
        MergeSort(arr,nLow,nMid);
        MergeSort(arr,nMid+1,nHigh);

        //合并
        Merge(arr,nLow,nHigh);
    }
}

HeapSort堆排序

堆排序是顺序储存，分为大根堆（大堆）和小根堆（小堆）。
大堆：父亲结点一定是三个结点最大的！
小堆：父亲结点一定是三个结点最小的！
并且左右儿子结点并没有什么大小顺序关系，我们只是把这个顺序存储的结构看作是二叉树的结构，
我们仅仅是看作二叉树的形式，实际上也是在数组进行操作，并且根据完全二叉树性质(第5条)来进行排序，对此我们要先掌握二叉树的基本知识。

适用场景：在n个元素里找前几个最大的或最小的，我们用堆，并且找大的用小堆，找小的用大堆。

例如：一个数组｛10，2，7，4，6，12，11，9，8｝


Heap1
  1. 首先数组按照二叉树的形势，我们只是按照二叉树对应的性质来将数组假想成二叉树的样子（并没有真正的改变数组的结构）。
  2. 我们按照图2的方式，从下往上从右往左的调整结点的位置，使其遵循大堆的特点！
  3. 图三是我们第一次调整好成大堆的样子。
  4. 图四我们将堆顶和数组最后一个元素对换。
  5. 然后重新按照前面的步骤调整成大堆，最后我们二叉树的第一个结点就是最大的数，依次类推。二叉树链接

堆排序类型题

类型题小结：

  1. 在一个数组中找出前4个最大的数？
    答：首先我们想到的是用小堆，我们建立一个只有四个结点的小堆(图在下面)，将数组元素一次放入小堆，并调整成小堆，这是用数组第五元素和堆顶元素比较，若比堆顶元素大的话，则把堆顶元素放入小堆，并移走小堆的最后一个元素（左边最下面），循环完数组小堆里的数就是前4大的！
  2. 在50亿个数里找出前50大？
    答：还是用小堆，建50个结点，将数据根据内存容量分流，依次按流通过小堆，每个流里选出前50大的，最后在整合到一起，在选出前50的数？
  3. 在一个数据流中找到中位数？数据流：一直不间断提供数据，随时提供，不是一个固定的数组。
    建立一个大堆和小堆，将数据丢入大堆，并且调整大堆，把大堆堆顶扔小堆里，当来数据的时候，调整小堆，把小堆堆顶放大堆里，来数据时，放入大堆并调整大堆，把大堆堆顶放入小堆里。依次循环过程。此时，小堆堆顶是较大数里最小的，大堆堆顶是比较小数里最大的。若数据的个数为奇数时，小堆堆顶是其中位数。当数据的个数为偶数时，小堆堆顶和大堆堆顶的和除2是其中位数。
Heap2

堆排序代码

#define nLeft nRootID*2+1
#define nRight nRootID*2+2

void Adjust2(int arr[],int nLength,int nRootID)
{
    int nMax;

    //在有孩子的情况下  假设左孩子是大的    
    for(nMax = nLeft;nLeft < nLength;nMax = nLeft /*下一次继续假设左孩子是最大的8*/)
    {
        //两个孩子
        if(nRight < nLength)
        {
            //右孩子大  
            if(arr[nMax] < arr[nRight])
            {
                nMax = nRight;
            }
        }

        //大的  和父亲比较  大  则交换
        if(arr[nMax] > arr[nRootID])
        {
            arr[nMax] = arr[nRootID] ^ arr[nMax];
            arr[nRootID] = arr[nRootID] ^ arr[nMax];
            arr[nMax] = arr[nRootID] ^ arr[nMax];

            nRootID = nMax;
        }
        else
        {
            break;
        }
    }
}

void HeapSort(int arr[],int nLength)
{
    int i;
    if(arr == NULL || nLength <=0)return;
    //建初始堆
    for(i = nLength/2-1;i>=0;i--)
    {
        Adjust2(arr,nLength,i);
    }
    //排序
    for(i = nLength-1;i>0;i--)
    {
        //最大值放后面
        arr[i] = arr[i] ^ arr[0];
        arr[0] = arr[i] ^ arr[0];
        arr[i] = arr[i] ^ arr[0];

        //调整根节点
        Adjust2(arr,i,0);
    }
}

BucketSort（桶排序）

基于哈希查找，用桶原理进行排序。

哈希查找可以去我的博客,也可以看我的另一篇查找的算法。推荐去博客，因为可以看latex数学公式。

桶排序更多时候是用来给小数排序的。

  1. 这里就以整数举例说明，例如数组｛19，27，55，31，47，50，16，21，22，25｝，我们按照每隔十位为一个桶。
  2. 1020，2030，3040，4050，50~60，共分为5个桶。
  3. 将数字按照其范围放入桶内。

  4. 之后在每个桶内进行排序，排好序之后依次从1桶开始倒回原数组（不给图了，读者可以自行画下，很简单）。这时排序就完成了。


    BucketSort

由于是链表的头添加，所以数字是到过来的顺序！

桶排序代码

typedef struct node
{
    int nValue;
    struct node *pNext;
}MyBucket;

void FindMaxMin(int arr[],int nLength,int *nMin,int* nMax)
{
    int i;
    *nMin = arr[0];
    *nMax = arr[0];
    for(i = 1;i<nLength;i++)
    {
        if(arr[i] < *nMin)
        {
            *nMin = arr[i];
        }
        if(arr[i] > *nMax)
        {
            *nMax = arr[i];
        }
    }
}

void BucketSort(int arr[],int nLength)
{
    int nMax;
    int nMin;
    int i;
    MyBucket **pBucket = NULL;
    int nMinIndex;
    int nMaxIndex;
    int nIndex;
    MyBucket *pTemp = NULL;
    MyBucket *pMark = NULL;
    int temp;

    if(arr == NULL || nLength <=0)return;

    //找到最大值 最小值
    FindMaxMin(arr,nLength,&nMin,&nMax);

    nMinIndex = nMin/10;
    nMaxIndex = nMax/10;

    //桶的确定
    pBucket = (MyBucket **)malloc(sizeof(MyBucket*) *(nMaxIndex-nMinIndex+1));
    memset(pBucket,0,sizeof(MyBucket*) *(nMaxIndex-nMinIndex+1));

    //各元素入桶
    for(i = 0;i<nLength;i++)
    {
        nIndex = arr[i]/10 - nMinIndex;
        pTemp = (MyBucket*)malloc(sizeof(MyBucket) );
        pTemp->nValue = arr[i];

        pTemp->pNext = pBucket[nIndex];
        pBucket[nIndex] = pTemp;
    }

    //各桶内排序
    for(i = 0;i<nMaxIndex-nMinIndex +1;i++)
    {
        //冒泡排序
        pMark = pBucket[i];
        
        while(pMark )
        {
            pTemp = pBucket[i];
            while(pTemp->pNext )
            {
                if(pTemp->nValue > pTemp->pNext->nValue)
                {
                    temp = pTemp->nValue;
                    pTemp->nValue = pTemp->pNext->nValue;
                    pTemp->pNext->nValue = temp;
                }
                pTemp = pTemp->pNext;
            }
            pMark = pMark->pNext;
        }
    }

    //倒回原数组
    i = 0;
    for(temp = 0;temp <nMaxIndex-nMinIndex +1;temp++ )
    {
        //遍历各个桶
        pMark = pBucket[temp];
        while(pMark)
        {
            arr[i] = pMark->nValue;
            i++;
            pMark = pMark->pNext;
        }
    }

    //释放空间
    for(temp = 0;temp <nMaxIndex-nMinIndex +1;temp++)
    {
        //释放每个桶
        pMark = pBucket[temp];
        while(pMark)
        {
            pTemp = pMark;
            pMark = pMark->pNext;
            free(pTemp);
            pTemp = NULL;
        }
    }

    free(pBucket);
    pBucket = NULL;
}

RadinSort(LSD)基数排序

基数排序分两种一种是LSD，一种是MSD，这个就说LSD,因为MSD类似LSD而且使用的不是很频繁，如想了解，看完LSD会事半功倍。LSD也是基于桶原理，而且是从位数开始排序的。

哈希查找可以去我的博客,也可以看我的另一篇查找的算法。推荐去博客，因为可以看latex数学公式。

例如数组：｛124，11，25，3，221，215，306，35，23，14，10，1，111｝
从低位开始算起，也就是个位开始的。因为十进制最后也就是0~9十个数字，所以我们要十个桶。

  1. 按照数组的顺序，依次入桶，所以我们这时应该是链表的尾添加
    个位：


    RadinSort-1
  2. 将桶内元素倒回数组，顺序不可以变，也就是10，11，221，1，111，3，23，124，14，25，215，35，306.这个顺序进入链表。

  3. 按照十位的数字进行分桶，从数组依次入桶。
    十位：


    RadinSort-2
  4. 再将桶内元素倒入数组，同样顺序不可以变，也就是1，3，306，10，11，111，14，215，221，23，124，25，35.这个顺序。

  5. 按照百位，依次入桶。
    百位：


    RadinSort-3
  6. 在倒入数组中，此时我们的排序就完成了。

代码

typedef struct node
{
    int nValue;
    struct node *pNext;
}MyRadix;

int FindMax(int arr[],int nLength)
{
    int i;
    int nMax = arr[0];
    for(i = 1;i<nLength;i++)
    {
        if(arr[i] > nMax)
        {
            nMax = arr[i];
        }
    }
    return nMax;
}

int GetLoopTimes(int nMax)
{
    int i = 0;
    while(nMax)
    {
        nMax/=10;
        i++;
    }
    return i;
}

void Sort(int arr[],int nLength,int i)
{
    int nBase = 1;
    MyRadix **pRadix = NULL;
    int j;
    int k;
    MyRadix *pTemp = NULL;
    int nIndex;
    MyRadix *pMark = NULL;

    //申请桶
    pRadix = (MyRadix **)malloc(sizeof(MyRadix*) * 10);
    memset(pRadix,0,sizeof(MyRadix*) * 10);

    //求被除基数
    while(i > 1)
    {
        nBase *= 10;
        i--;
    }

    //数字入桶
    for(j = 0;j <nLength; j++)
    {
        nIndex = arr[j]/nBase%10;

        pTemp = (MyRadix*)malloc(sizeof(MyRadix));
        pTemp->nValue = arr[j];
        pTemp->pNext = NULL;

        //尾添加
        if(pRadix[nIndex] == NULL)
        {
            pRadix[nIndex] = pTemp;
        }
        else
        {
            pMark = pRadix[nIndex];
            while(pMark->pNext)
            {
                pMark = pMark->pNext;
            }

            pMark->pNext = pTemp;
        }
    }

    //放回原数组
    j = 0;
    for(k = 0;k<10;k++)
    {
        pMark = pRadix[k];
        while(pMark)
        {
            arr[j] = pMark->nValue;
            j++;
            pMark = pMark->pNext;
        }
    }

    //空间释放
    for(k = 0;k<10;k++)
    {
        pMark = pRadix[k];
        while(pMark)
        {
            pTemp = pMark;
            pMark = pMark->pNext;
            free(pTemp);
            pTemp = NULL;
        }
    }

    free(pRadix);
    pRadix = NULL;
}

void RadixSort(int arr[],int nLength)
{
    int i;
    int nMax;
    int nLoopTimes;
    if(arr == NULL || nLength <=0)return;

    //找最大值
    nMax = FindMax(arr,nLength);

    //获得循环次数
    nLoopTimes = GetLoopTimes(nMax);

    //数组元素按照各位依次入桶
    for(i = 1;i<=nLoopTimes;i++)
    {
        //个 十 百 位处理
        Sort(arr,nLength,i);
    }
}
上一篇下一篇

猜你喜欢

热点阅读