各种各样的排序(持续更新)

1.冒泡排序

 

void BubbleSort(int array[], int n)
{
    int i, j, k;
    for(i=0; i<n-1; i++)
        for(j=0; j<n-1-i; j++)
        {
            if(array[j]>array[j+1])
            {
                k=array[j];
                array[j]=array[j+1];
                array[j+1]=k;
            }
        }
}

思想很明确,就是遇到比自己小的就立刻交换,注意此时比较大的那个(之前在比它小的前面)被转移到了后一位,那么j++后指向的对象就是这个比较大的,如果不是那么 j++ 指向的就是比 j++ 操作前指向的个体大的那个数,从而实现“冒泡”。

 

 

2.选择排序(没用)

 

void selectSort(int array[], int n)
{
    int i, j ,min ,k;
    for( i=0; i<n-1; i++)
    {
        min=i; //每趟排序最小值先等于第一个数,遍历剩下的数
        for( j=i+1; j<n; j++) //从i下一个数开始检查
        {
            if(array[min]>array[j])
            {
                min=j;
            }
        }
        if(min!=i)
        {
            k=array[min];
            array[min]=array[i];
            array[i]=k;
        }
    }
}

每次都要遍历一次数组,找到最小的,如果不是原来的就进行交换。

 

 

3.插入排序

 

void insertSort(int array[], int n)
{
    int i,j,temp;
    for( i=1;i<n;i++)
    {
        if(array[i]<array[i-1])  //确定这个数是要进行排序的
        {
            temp=array[i];          //把它提取出来
            for( j=i;j-1>=0 && array[j-1]>temp ;j--)  //如果这个数比前面的要小,就把提取出来的数的位置给它
            {
                array[j]=array[j-1];     //原来的位置被覆盖,一次便利到最后总会出现两个相同的值
            }
            array[j]=temp;  //插入操作
        }
    }
}

 

 

 

4.归并排序

 

void merging(int *list1, int list1_size, int *list2,  int list2_size)  //归并过程
{
    int i=0, j=0, k=0, m=0;      //注意这里的i的作用域在整个函数中
    int temp[1000];

    while(i < list1_size && j < list2_size)     //在两个数组中轮流选择,谁小谁上
    {
        if(list1[i]<list2[j])   
        {
            temp[k++] = list1[i++];
        }
        else
        {
            temp[k++] = list2[j++];
        }
    }                                    //事实上经过这样的选择融合后必定有一个数组是被选完的
    
    //说白了假如 list1或2 数组中如果有剩下的,那么说明就是它剩余的是比前面的数组都大的,直接加入就可以了

    while(i<list1_size)         //此时i不再是零而是在上面经过选择进入 temp 数组(这个过程)后指向 list1 的末尾(如果i不等于末尾的话)
    {
        temp[k++] = list1[i++];  //把 list1 数组中剩余的数复制进去 temp 数组中
    }
    while(j<list2_size)         //此时j不再是零而是在上面经过选择进入 temp 数组(这个过程)后指向 list2 的末尾(如果j不等于末尾的话)
    {
        temp[k++] = list2[j++];  //把 list2 数组中剩余的数复制进去 temp 数组中
    }

    for(m=0; m < (list1_size+list2_size); m++)
    {
        list1[m]=temp[m];
    }
}
 
void mergeSort(int array[], int n)
{
    if(n>1)             //判断是否返回的标准
    {
        int *list1 = array;
        int list1_size = n/2;
        int *list2 = array + n/2;
        int list2_size = n-list1_size;

        mergeSort(list1, list1_size);  //持续递归直到list数组只剩下两个
        mergeSort(list2, list2_size);  //持续递归直到list数组只剩下两个

        merging(list1, list1_size, list2, list2_size);   //对list 1 或 2 数组进行融合
    }
}

 

 

 

5.快排

 

//接口调整
void adjust_quicksort(int k[],int n)  
{  
   quicksort(k,0,n-1);  
}  
void quicksort(int a[], int left, int right)  
{  
    int i,j,t,temp;  
    if(left>right)   //(递归过程先写结束条件)
       return;  

    temp=a[left]; //temp中存的就是基准数  
    i=left;  
    j=right;  
    while(i!=j)  
    {  
                   //顺序很重要,要先从右边开始找(最后交换基准时换过去的数要保证比基准小,因为基准                               
                   //选取数组第一个数,在小数堆中) 
                   while(a[j]>=temp && i<j)  
                            j--;  
                   //再找右边的  
                   while(a[i]<=temp && i<j)  
                            i++;  
                   //交换两个数在数组中的位置  
                   if(i<j)  
                   {  
                            t=a[i];  
                            a[i]=a[j];  
                            a[j]=t;  
                   }  
    }  
    //最终将基准数归位 (之前已经temp=a[left]过了,交换只需要再进行两步)
    a[left]=a[i];  
    a[i]=temp;  

    quicksort(left,i-1);//继续处理左边的,这里是一个递归的过程  
    quicksort(i+1,right);//继续处理右边的 ,这里是一个递归的过程  
}  

 

 

6.桶排序

这个很简单没什么好说的 🙂

int main()
{
    int a[11],i,j,t;
    for(i=0;i<=10;i++)
        a[i]=0;  //初始化为0

    for(i=1;i<=5;i++)  //循环读入5个数
    {
        scanf("%d",&t);  //把每一个数读到变量t中
        a[t]++;  //进行计数(核心行)
    }

    for(i=0;i<=10;i++)  //依次判断a[0]~a[10]
        for(j=1;j<=a[i];j++)  //出现了几次就打印几次
            printf("%d ",i);

    return 0;
}

 

 

 

7.堆排序

 

//注意数组第一个是不设值的,即int a[]={0,899,5,58,62,14,17};
void heapSort(int array[], int n)
{
    int i;
    for (i=n/2;i>0;i--)               //建立最大堆,i为从右到左第一个非子叶节点
    {
        HeapAdjust(array,i,n);    //从下向上,从右向左调整
    }
    for( i=n;i>1;i--)       //开始进行排序
    {
        swap(array, 1, i);      //交换最大的和最后一个子叶点,实际上就是把最大的(堆顶)放在最后
        HeapAdjust(array, 1, i-1);//再次调整最大堆,从上到下,从左向右调整,i-1是对被调整到最后的最大值进行出堆操作
    
}
void HeapAdjust(int array[], int s, int n )
{
    int i,temp;
    temp = array[s];        
                                //下面的注释大都在描述第一次调整时的过程:)
    for(i=2*s;i<=n;i*=2)        //i为从右到左选择的第一个非子叶点的节点,(当它在倒数第二层乘了二后变为子叶点)(通常在倒数第三层后才会进行循环)
    {
        if(i<n && array[i]<array[i+1]) //不会越界因为 i 要小于节点总数 n 才行,此步骤为两个子叶点进行比较(前提是如果有两个)
        {
            i++;                  //如果右大于左,则把i设为指向右节点
        }
        if(temp>=array[i])      //如果父节点比两个子节点中最大的那个都要大,那么退出循环,注意这里的父节点是指循环第一次所选定的父节点
        {                       //今后的比较都是用这个temp值来比较
            break;
        }
        array[s]=array[i];  //否则将父节点的内容变成两个子节点中最大的那个,注意这里的交换只是数组内容的顶替
        s=i;    //更新指向原父节点的指针s的值,将其值变成(某)两个子节点中最大的那个的编号(i)的值
                //在下一轮循环中要找的子节点的编号是由s提供的,实际上s可以理解为一种指针,s永远指向相对的父节点
                //事实上(也可以注意到)某两个个节点中的值相同并不重要因为如果一开始指定的“父节点”原值已经被记录在 temp 中
                //如果这个值比剩下的两个节点都要大,就把它塞进去
                //如果还要再调整,即没用进入break模块,那么就把此时s指向的节点(相对的父节点)的值换成那个最大子节点的值
                //同时再次更新s指针,如果到底了就退出循环
    }
    //此时s已经指向一个子叶节点或者相对的父节点,而此时这个点的值还是原来某两个子节点中最大的那个的值,因此需要更新
    array[s]=temp; 
    //可以发现交换过程中父节点总是和相差最大的子节点进行“交换”行为
}
void swap(int array[], int i, int j)
{
    int temp;

    temp=array[i];
    array[i]=array[j];
    array[j]=temp;
}

思考了很久,事实上堆排序利用的就是最大堆的特性:堆顶的最大值,每次对堆顶的数字进行出堆操作同时放到数组的最后面。而关键的我猛然发现这个数组里面的“键值”,就是x[2]里面的2,可以理解为一种属性(废话),而把这种属性抽象出来就是一种“指针”。可以利用这一点对值进行相关的修改(废话)。像在这个堆排序里面就是这样子,设置了两个“指针”,i和s,i由s生,s又可以变成i,i永远指向s的子节点。

总之很牛皮。

 

 

8.希尔排序:

先粘贴上去,下次再想

//在插入排序基础上修改得到希尔排序
void SheelSort( int array[], int n)
{
    int i,j,temp;
    int gap=n; //~~~~~~~~~~~~~~~~~~~~~
    do{
        gap=gap/3+1;  //~~~~~~~~~~~~~~~~~~
        for( i=gap;i<n;i++ )
        {
            if(array[i]<array[i-gap])
            {
                temp=array[i];
                for( j=i-gap;array[j]>temp;j-=gap)
                {
                    array[j+gap]=array[j];
                }
                array[j+gap]=temp;
            }
        }
    }while(gap>1);  //~~~~~~~~~~~~~~~~~~~~~~

}

 

Bellman-Ford及其队列优化

说白了这玩意可以处理负边权,和 Dijkstra 看起来一样但却有着微妙的不同..

未优化前

优化后

一些分析

可以看的出该算法是以把边扔进去试一试为主,Dijkstra 算法的找最小值那一步体现了它基于贪心,而Bellman-Ford 算法则是从边的点出发,企图通过给定边(u,v)来达到 v 点或者说看能不能缩短源点 s 到 v 的距离(一开始是 inf )。 第一轮把所有边扔进去试,松弛结束后 dis[ ] 数组更新,开始进行第二轮松弛,重新把所有边扔进去算(注意此时会存在冗杂的现象,因为一些点的值已成为确定值)。

事实上可以发现第一次松弛时 dis[ ] 数组只有与源点相邻的点才会更新,而后可以发现第 k 次松弛代表着用 k 条线路可以达到的最小值(即表现为对 dis[ ] 数组的更新)即使出现负边权,设这条蛋疼的边为 x(u,v),则迟早会对 v 进行真正的松弛,(其实第一次把边代进去会缩小 dis[ v ] 的值,就算 dis[ u ] 是 inf , 
dis[ v ] > x(u,v)+ dis[ u ] )我指的真正的松弛是当 dis[ u ] 不为 inf 时,dis[ v ] 再次被更新,然后。。看起来负权边对后续就没什么影响了。。(大概)

而当算了n-1轮后结束,则能给出最短路径。若还能再松弛,则说明出现负权回路。因为若进行了n轮说明了居然存在一条路在通过n个点时的权值比以往的还小,这就说明存在一条路它的值可能为 -100000 之类的,这时就要报错了,这也是Bellman-Ford 的特征:可以处理负权环路。

优化分析

Bellman-Ford算法在每一次实施松弛操作时,就会有一些顶点已经求得最短路径,此后这些顶点的最短路径的估计值就会一直保持不变,不再受后续松弛操作的影响,但是每次还要判断是否需要松弛,这里浪费了大量的时间.

思想:每次选取队首顶点u,对顶点u的所有出边进行松弛操作,例如有一条u->v的边,如果通过u->v的这条边使得源点到顶点v的最短路径变得更短,也即(dis[u] + e[u][v] < dis[v]),并且顶点v不在当前的队列(并用借助一个数组标记顶点是否已经在队列之中),则将顶点v放置队尾. 对顶点u的所有出边松弛完毕之后,就将顶点u出队,接下来不断从队列中取出新的队首顶点反复上面操作直到队列为空结束. 
队列优化的Bellman-Ford的关键之处: 只有那些在前一遍松弛中改变了最短路径估计值的点,才可能引起它们邻接点最短路径估计值发生改变. 因此用一个队列保存被成成功松弛的顶点,之后只对队列中的点进行处理,这就降低了算法的时间复杂度


来自CSDN的说明

说白了就是如果入队成功则代表这个点有资格作为中转站,如果松弛失败了则对它的后续操作是没有意义的,并且可以看到每次把边带进去时是代头指针指向的点的邻边,不会一开始就浪费资源去搞其他边。(大概是这个样子)

(逃

 

Floyd 和 Dijkstra 算法

弗洛伊德算法很简单,疯狂试试就出来了

这个狄克斯特拉就得慢慢找了…

这是Floyd


这是Dijkstra

分析一下这个Dijkstra

先说说这个 Dijkstra ,书上说的所谓“松弛”,其实就是某个点可以用来当中转站这个意思。先找最小的,再以这个最小的点作为中转站然后去扩展(或者说是去“努力”到达【因为可能并不能通过这个点去到达其他点】)其他的点。

这个算法是基于贪心算法而来的,就是说我一直选离我最近的点且保证松弛以后其他点不会离我更近。因此出现负边权就用不了了, 因为每次选取的是当前最短的边进行松弛,当边都是正权时,松弛后边权一定比当前最短边大,所以满足贪心的条件,有了负边后后续的松弛会出现比前边小的情况,不满足贪心的条件所以不能用 Dijkstra 计算带有负边的单源最短路。

总结

1.Floyd 空间复杂度为 N^2 时间复杂度为 N^3

2.Dijkstra 空间复杂度为 M 时间复杂度为 (M+N)logN

分类….