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

个人介绍及问题解决

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);
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,670评论 5赞 460
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,928评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,926评论 0赞 320
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,238评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,112评论 4赞 356
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,138评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,545评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,232评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,496评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,596评论 2赞 310
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,369评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,226评论 3赞 313
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,600评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,906评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,185评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,516评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,721评论 2赞 335

推荐阅读更多精彩内容

  • 八大排序算法 (转载)
    概述：排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    每天刷两次牙阅读 3,723评论 0赞 15
  • （转）八大排序算法
    概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    蚁前阅读 5,149评论 0赞 52
  • 排序 29
    1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,225评论 0赞 2
  • 2017-11-11
    请您欣赏儿子花窖新到的品质盆景
    老窦阅读 230评论 0赞 0
  • [TB6] U1L2 Homework
    Book 6, Unit 1, Lesson 2 In this unit, the students will ...
    TimmySHENX阅读 206评论 0赞 2