个人介绍及难题消除,同样这里的梳排序也是在冒泡排序上做了有的优化

  

私家介绍及难点一蹴即至

  那篇再看看四个卓越的排序,梳排序,为何取名称叫梳,也许各种梳都有谈得来的gap吧,大梳子gap大学一年级点,小梳子gap小一些。

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 ;
}

冒泡排序上大家的挑选是相近的七个数做比较,正是她们的gap为1,其实梳排序建议了不一样的见地,假如将这里的gap设置为一定的大大小小,

不带中间变量完结五个同样档案的次序不一样值变量间的沟通

  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不可能指向同一块地点空间!

频率反而必gap=1要高速的多。

SelectSort选择排序

首先,用第贰个数去和全部数实行比较,选出个中非常的小的数,放在第三个人,在用第贰个数去和全数数进行比较,最小的放在第几人,依第2轮回遍历!

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记下来,不用每回相比完举行调换,而是最后直接用记录的数组下标实行置换!

 上边我们看看具体考虑,梳排序有与上述同类一个1.3的比率值,每便相比较完后,都会用这些1.3去递减gap,直到gap=1时成为冒泡排序,这种

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;
    }

}

算法比冒泡排序的功效要火速的多,时间复杂度为O(N2/2p)
 这里的p为增量,是否跟希尔排序有一点点点神似。。。

快排

快排的亮点:是正如次数最少的排序!

    比方上面有一组数据: 早先化的gap=list.count/1.3,
然后用这些gap作为数组下标进行跨数字极大小,前面多少个大于后面一个则展开置换,

挖坑填补法

诸如数组:7,2,8,4,3,5。我们用temp标记7

  1. 我们将首先数7当规范值,此时一定于7是二个坑(用粗斜体标志),然后大家以前边依次找比正规值7小的数,
    第三个5就比7小,大家将5放到7的坑里。数组变成5,2,8,4,3,7,那是坑产生最后位数!
  2. 接下来大家在前方找四个比正规值大的数,第二个数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);
    }
}

每回排序完结后都除以1.3, 最终直接除到gap=1

区间(域)分割法

快排的一种,比挖坑填补法快!类似与挖坑填补法,是其优化提高版啊!
例如,数组: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交换,57,4,3,6。
  3. 将遍历指针指下一处,5,7,4,3,6,比标准值小,将4和第贰个数调换。5,47,3,6
    一举手一投足遍历指针,5,4,7,3,6
  4. 比标准值小,将3和第3个数调换。5,4,37,6,移动遍历指针。5,4,3,7,6
  5. 那时遍历甘休,判定++s与i是还是不是相等,若不等,5,4,3,76,数组[s]与数组[i]交换。
  6. 5,4,3,67,此时专门的学问值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);
    }
}

图片 1

快排区间分开优化

若我们挑选的标准值恰好是最小值或许最大值,那是快排产生互换的次数最多,如若大家在甄选下标的时候进行优化,
笔者们用随机数选拔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。
    一定于在提请的数组首个职位,计数加一,每趟碰着一样的值都加一。
  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]--;
        }
    }
}
 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Xml.Xsl;
 6 
 7 namespace ConsoleApplication1
 8 {
 9     class Program
10     {
11         static void Main(string[] args)
12         {
13             List<int> list = new List<int>() { 8, 1, 4, 2, 9, 5, 3 };
14 
15             Console.WriteLine("\n排序前 => {0}\n", string.Join(",", list));
16 
17             list = CombSort(list);
18 
19             Console.WriteLine("\n排序后 => {0}\n", string.Join(",", list));
20 
21             Console.Read();
22         }
23 
24         /// <summary>
25         /// 梳排序
26         /// </summary>
27         /// <param name="list"></param>
28         /// <returns></returns>
29         static List<int> CombSort(List<int> list)
30         {
31             //获取最佳排序尺寸: 比率为 1.3
32             var step = (int)Math.Floor(list.Count / 1.3);
33 
34             while (step >= 1)
35             {
36                 for (int i = 0; i < list.Count; i++)
37                 {
38                     //如果前者大于后者,则进行交换
39                     if (i + step < list.Count && list[i] > list[i + step])
40                     {
41                         var temp = list[i];
42 
43                         list[i] = list[i + step];
44 
45                         list[i + step] = temp;
46                     }
47 
48                     //如果越界,直接跳出
49                     if (i + step > list.Count)
50                         break;
51                 }
52 
53                 //在当前的step在除1.3
54                 step = (int)Math.Floor(step / 1.3);
55             }
56 
57             return list;
58         }
59     }
60 }

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;
            }
        }
    }
}

图片 2

Hill排序的优化

分组时,让各组一齐开展插入排序,都只实行三次,然后循环举行,代码看起来不难,不过实际上耗费时间基本一样!

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路)进行递归拆分,
拆分到每一种块里只剩贰个成分,然后和相邻成分举办相比较排序合併,在比较在统一。

 

流程

图片 3

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}

图片 4

Heap1

  1. 第一数组遵照二叉树的地势,我们只是遵照二叉树对应的本性来将数组假想成二叉树的样子(并未当真的转移数组的构造)。
  2. 我们依照图2的不二秘诀,从下往上从右往左的调动结点的岗位,使其依照大堆的特色!
  3. 图三是大家率先次调动好成大堆的样子。
  4. 图四大家将堆顶和数组最终三个因素对换。
  5. 下一场再一次依照前面包车型地铁步骤调解成大堆,最后我们二叉树的率先个结点正是最大的数,依次类推。二叉树链接

堆排序类型题

品类题小结:

  1. 在四个数组中寻找前4个最大的数?
    答:首先大家想到的是用小堆,大家创立五个独有七个结点的小堆(图在上边),将数组成分三回放入小堆,并调治成小堆,那是用数组第五因素和堆顶成分比较,若比堆顶成分大的话,则把堆顶成分放入小堆,并移走小堆的末尾二个成分(侧面最下边),循环完数组小堆里的数正是前4大的!
  2. 在50亿个数里寻觅前50大?
    答:如故用小堆,建肆拾叁个结点,将数据遵照内部存款和储蓄器体量分流,依次按流通过小堆,各个流里选出前50大的,最终在重组到一块,在选出前50的数?
  3. 在八个数据流中找到中位数?数据流:一向不间断提供数据,随时提供,不是贰个牢固的数组。
    确立三个大堆和小堆,将数据丢入大堆,並且调动大堆,把大堆堆顶扔小堆里,当来多少的时候,调治小堆,把小堆堆顶放大堆里,来数量时,放入大堆并调节大堆,把大堆堆顶放入小堆里。依次循环进度。此时,小堆堆顶是不小数里最小的,大堆堆顶是相当小数里最大的。若数据的个数为奇数时,小堆堆顶是里面位数。当数码的个数为偶数时,小堆堆顶和大堆堆顶的和除2是当中位数。

图片 5

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桶发轫倒回原数组(不给图了,读者能够自行画下,异常的粗略)。那时排序就完事了。
![](https://upload-images.jianshu.io/upload_images/3780843-7f92b8707d4abd61.jpg)

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拾二个数字,所以我们要11个桶。

  1. 依据数组的相继,依次入桶,所以大家那时候应该是链表的尾增加
    个位:
![](https://upload-images.jianshu.io/upload_images/3780843-db84dcbf2f340b70.jpg)

RadinSort-1
  1. 将桶内元素倒回数组,顺序不可能变,也正是10,11,221,1,111,3,23,124,14,25,215,35,306.这些顺序步向链表。
  2. 根据十位的数字举行分桶,从数组依次入桶。
    十位:
![](https://upload-images.jianshu.io/upload_images/3780843-78386c18963aef2c.jpg)

RadinSort-2
  1. 再将桶内成分倒入数组,同样顺序不得以变,也即是1,3,306,10,11,111,14,215,221,23,124,25,35.以此顺序。
  2. 依据百位,依次入桶。
    百位:
![](https://upload-images.jianshu.io/upload_images/3780843-a859196069ed2636.jpg)

RadinSort-3
  1. 在倒入数组中,此时大家的排序就完事了。

代码

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);
    }
}

相关文章