365体育官网一样那里的梳排序也是在冒泡排序上做了一部分优化,个人介绍及问题化解

  

个体介绍及问题解决

  那篇再看看一个经典的排序,梳排序,为啥取名为梳,可能每个梳都有投机的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采用排序

首先,用第三个数去和所有数举办比较,选出其中很小的数,放在首位,在用第四个数去和全路数进行比较,最小的位于首位,依次循环遍历!

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为增量,是还是不是跟希尔(希尔(Hill))排序有点点神似。。。

快排

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

    比如上面有一组数据: 开头化的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. 下一场咱们在前头找一个比标准值大的数,第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);
    }
}

每便排序落成后都除以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和第多个数调换。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);
    }
}

365体育官网 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。
    一定于在申请的数组第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]--;
        }
    }
}
 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希尔(希尔(Hill))排序

插入排序的优化,按涨幅举行分组,然后在组内举办插入排序,然后在二分法步长,重复此进程。(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;
            }
        }
    }
}

365体育官网 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路)举办递归拆分,
拆分到每个块里只剩一个因素,然后和隔壁元素举办相比排序合并,在比较在联合。

 

流程

365体育官网 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}

365体育官网 4

Heap1

  1. 先是数组根据二叉树的山势,大家只是依据二叉树对应的性能来将数组假想成二叉树的楷模(并不曾真正的变更数组的构造)。
  2. 大家根据图2的不二法门,从下往上从右往左的调动结点的岗位,使其根据大堆的特色!
  3. 图三是我们率先次调整好成大堆的榜样。
  4. 图四我们将堆顶和数组最后一个要素对换。
  5. 接下来再度根据前边的步骤调整成大堆,最终大家二叉树的首先个结点就是最大的数,依次类推。二叉树链接

堆排序类型题

类型题小结:

  1. 在一个数组中找出前4个最大的数?
    答:首先大家想到的是用小堆,大家树立一个唯有多少个结点的小堆(图在上边),将数组元素三遍放入小堆,并调整成小堆,那是用数组第五元素和堆顶元素比较,若比堆顶元素大的话,则把堆顶元素放入小堆,并移走小堆的最终一个要素(左侧最上边),循环完数组小堆里的数就是前4大的!
  2. 在50亿个数里找出前50大?
    答:照旧用小堆,建50个结点,将数据按照内存容量分流,依次按流通过小堆,每个流里选出前50大的,最终在整合到一块儿,在选出前50的数?
  3. 在一个数码流中找到中位数?数据流:平素不间断提供数据,随时提供,不是一个恒定的数组。
    建立一个大堆和小堆,将数据丢入大堆,并且调动大堆,把大堆堆顶扔小堆里,当来多少的时候,调整小堆,把小堆堆顶放大堆里,来数量时,放入大堆并调动大堆,把大堆堆顶放入小堆里。依次轮回进程。此时,小堆堆顶是较大数里最小的,大堆堆顶是比较小数里最大的。若数据的个数为奇数时,小堆堆顶是其中位数。当数码的个数为偶数时,小堆堆顶和大堆堆顶的和除2是里面位数。

365体育官网 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十个数字,所以大家要十个桶。

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

相关文章