大茶园丁 发布的文章

Merge Sort 归并排序C语言实现

#Merge Sort-归并排序

此贴由戴维营教育学员翻译,鄙人整理,特意为戴维营教育零基础学员课外学习之用.

归并排序是基于分而治之的方法,它把这个要进行排序的列表,平分成两半,变成两个未排序的列表。再对这两个无序列表进行同样的排序,合并,最终得到一个排好序的列表。这两个无序列表是通过不断地调用归并排序算法进行排序;我们最终得到一个大小为1的已经排好序的列表。这两个大小为1的列表,然后又合并。

##算法:

这是一种分而治之的算法。工作原理如下 -

  • 1,把我们输入的需要排序的列表从中间分成两半,称为左半部分和右半部分。
    例如:假设输入是-10 32 45 -78 91 1 0 -16,则左部分是-10 32 45 -78,右部分将是91 1 0 6。
  • 2,把这左右两部分分别单独排序。需要注意的是,这里的排序并不意味着使用其他一些方法来排序。而是我们递归地使用一样的函数。
  • 3,然后合并这两个排好序的列表。

输入元素的总个数:number_of_elements, 然后输入这么多个元素保存到数组array[number_of_elements]里面。接下来调用函数 MergeSort() 对这个数组进行排序。
MergeSort()函数对数组[left,right]范围内的元素排序,即从索引left到索引right之的所有元素。
Merge() 函数的作用是合并两个已排好序的部分。排好序的部分是从[left,mid][mid+1,right]。合并后输出这个排好序的数组。

MergeSort() 函数:

它把数组,以及该数组的最左边和最右边的索引作为它的参数。数组的中间元素通过公式(left + right)/2计算得出。检查是否(left<right)因为只有(left<right)时我们才需要排序,而当left=right时表示它已经排好序了。排序左半部分通过调用MergeSort(array,left,mid),排序右半部分通过调用MergeSort(array,mid + 1, right),最后调用Merge() 函数把这两个数组合并到一起。

最后复制回已排序的数组到原数组。

##特性:

  • 最好的情况 - 当数组已经排序时, 时间复杂度为O(nlogn)
  • 最坏的情况 - 当数组是按相反的顺序时, 时间复杂度为O(nlogn)
  • 一般情况下 - 时间复杂度为O(nlogn)
  • 额外的空间是必需的,所以数组归并排序空间复杂度是O(n) ,链表归并排序的空间复杂度是O(logn).

##归并排序C语言实现


#include <stdio.h>
/*This is called Forward declaration of function */
void Merge(int * , int , int , int );
/* Logic: This is divide and conquer algorithm. This works as follows.
         (1) Divide the input which we have to sort into two parts in the middle. Call it the left part and right part.
             Example: Say the input is  -10 32 45 -78 91 1 0 -16 then the left part will be -10 32 45 -78 and the right part will be  91 1 0 6.
         (2) Sort Each of them seperately. Note that here sort does not mean to sort it using some other method. We already wrote fucntion to sort it. Use the same.
         (3) Then merge the two sorted parts.
*/

/*This function Sorts the array in the range [left,right].That is from index left to index right inclusive
 */
 
void MergeSort(int *array, int left, int right)
{
        int mid = (left+right)/2;
        /* We have to sort only when left<right because when left=right it is anyhow sorted*/
        if(left<right)
        {
                /* Sort the left part */
                MergeSort(array,left,mid);
                /* Sort the right part */
                MergeSort(array,mid+1,right);
                /* Merge the two sorted parts */
                Merge(array,left,mid,right);
        }
}


/* Merge functions merges the two sorted parts. Sorted parts will be from [left, mid] and [mid+1, right].
 */
void Merge(int *array, int left, int mid, int right)
{
        /*We need a Temporary array to store the new sorted part*/
        int tempArray[right-left+1];
        int pos=0,lpos = left,rpos = mid + 1;
        while(lpos <= mid && rpos <= right)
        {
                if(array[lpos] < array[rpos])
                {
                        tempArray[pos++] = array[lpos++];
                }
                else
                {
                        tempArray[pos++] = array[rpos++];
                }
        }
        while(lpos <= mid)  tempArray[pos++] = array[lpos++];
        while(rpos <= right)tempArray[pos++] = array[rpos++];
        int iter;
        /* Copy back the sorted array to the original array */
        for(iter = 0;iter < pos; iter++)
        {
                array[iter+left] = tempArray[iter];
        }
        return;
}


int main(void)
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        MergeSort(array,0,number_of_elements-1); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;
}

Quick Sort 快速排序C语言实现

#Quick Sort-快速排序

此贴由戴维营教育学员翻译,鄙人整理,特意为戴维营教育零基础学员课外学习之用.

快速排序像归并排序一样是一个分而治之的算法,但它不想归并排序那样,它不需要额外的空间,在待排序的集合内就地排序。

这个分割步骤就是选择一个基准点把数组分割,小于或等于基准点的元素全排到左边去,大于或等于基准点的元素全部排到基准点右边去。再依次对左右两边的元素递归地进行快速排序。

##算法
该算法的关键在于分区.

  • 从数列中挑出一个元素,称为 "基准"(pivot),
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

基准选择与分区:

快速排序图示:

##特性

  • 最佳性能:当分区产生两个区域的大小是n/2时(n是列表中的元素的总数),时间复杂度为O(nlgn).
  • 最差性能:当分区产生一个区域的大小是n - 1时(n是列表中的元素的总数),另一个区域大小为1,时间复杂度为O(n2).
  • 平均情况:时间复杂度O(n(lgn))
  • 在最坏的情况下,使用O(lg(n))额外的空间, 这是一个不稳定的算法。

##快速排序-C语言代码

#include <stdio.h>
/* Logic:
This is divide and conquer algorithm like Merge Sort.
Unlike Merge Sort this does not require extra space.So it sorts in place.
Here dividing step is chose a pivot and parition the array such that all elements less than or equal to pivot are to the left of it andd all the elements which are greater than or equal to the pivot are to the right of it.
Recursivley sort the left and right parts.
*/

void QuickSort(int *array, int from, int to)
{
        if(from>=to)return;
        int pivot = array[from]; /*Pivot I am chosing is the starting element */
        /*Here i and j are such that in the array all elemnts a[from+1...i] are less than pivot, all elements a[i+1...j] are greater than pivot and the elements a[j+1...to] are which we have not seen which is like shown below.
          ________________________i_________________j___________
          |pivot|....<=pivot......|....>=pivot......|.........|
          If the new element we encounter than >=pivot the above variant is still satisfied.
          If it is less than pivot we swap a[j] with a[i+1].
         */
        int i = from, j, temp;
        for(j = from + 1;j <= to;j++)
        {
                if(array[j] < pivot) 
                {
                        i = i + 1;
                        temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                }
        }
        /* Finally The picture is like shown below
          _______________________i____________________
          |pivot|....<=pivot......|....>=pivot......|
        */
        temp = array[i];
        array[i] = array[from];
        array[from] = temp;
        /* So we the array is now 
          ____________________i______________________
          |...<=pivot......|pivot|....>=pivot......|
        */
        /*Recursively sort the two sub arrays */
        QuickSort(array,from,i-1);
        QuickSort(array,i+1,to);
}
int main()
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        QuickSort(array,0,number_of_elements-1); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;
}

Insertion Sort插入排序C语言实现

#Insertion Sort-插入排序

此贴由戴维营教育学员翻译,鄙人整理,特意为戴维营教育零基础学员课外学习之用.

##介绍
插入排序使用线性搜索来查找未排序的列表中第一个元素,其在已经排好序的那部分列表的插入位置。是一个基本排序算法,多用于排序较小的数据集或插入一个新元素到前面已排序好的列表中。

##算法:

插入排序从第1个元素开始,可以认为这个元素已经排序,然后把后面的元素依次插入前面有序列表中。

  • 1,假设如果数组排序到i位置,我们可以对数组进行排序,直到从第(i+1)个元素到数组最后一个元素正确插入到当前元素的前面。

  • 2,第i+1个元素的插入位置必须在遍历第个元素到第i个元素之间找到。

  • 3,任何数组排序到第个位置(单个元素总是排序),这样就知道如何扩大,怎么对整个数组排序。

##特性:

  • 最佳性能的情况——当数组已经排序:O(n), 总的比较次数:N-1,总的交换次数:N-1

  • 最差性能的情况——当数组排序以相反的顺序: O(n2), n-1次比较和交换的遍历。

  • 平均性能情况: O(n2)

  • 排序过程中的比较次数和交换次数严重依赖于数据的输入.

  • 它排序过程中不需要任何额外的空间,因此空间复杂度是 O(1)

##插入排序-C语言代码

#include <stdio.h>
/* Logic :
Suppose if the array is sorted till index i then we can sort the arry till i+1 by inserting i+1 th element in the correct position from 0 to i+1.
The position at which (i+1)th element has to be inserted has to be found by iterating from 0 to i.
As any array is sorted till 0th postion(Single element is always sorted) and we know how to expand, we can sort the whole array.
 */
void InsertionSort(int *array , int number_of_elements)
{
        int iter,jter;
        for(iter=1;iter<number_of_elements;iter++)
        {
                int current_element = array[iter];
                jter = iter-1;
                while(jter>=0 && array[jter] > current_element)
                {
                        array[jter+1] = array[jter];
                        jter--;
                }
                array[jter+1] = current_element;
        }
}

int main(void)
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements];
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        InsertionSort(array,number_of_elements);
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;
}

Bubble Sort冒泡排序C语言实现

#Bubble Sort

此贴特意为戴维营教育零基础学员课外学习之用.

这是一种排序算法,他就是相邻的两个元素两两比较,如果顺序不对就互相交换位置,比较一直往后重复,直到不需要交换为止,也就是已经排好序. 那个比较小的元素"像气泡一样往上冒泡"到最顶端,因此而得名冒泡排序.

###算法

从待排列表的第一个元素开始,一直比较和交换相邻的两个元素直到列表被排好序

  • 比较相邻的两个元素,并检查他们是否是正确的序号(第二个应该比第一个要大).
  • 如果他们的顺序不正确,那么交换他们的位置,使其第二个比第一个大.

让一个整型变量int iter;来表示循环的次数,那么iter的取值范围就是从1到n-1这样一个整型区间,n是待排序列表的元素的个数.
判断

  1. 如果在循环变量iter的位置,第二个元素的值小于第一个元素的值(iter-1位置),那么就交换他们的位置.
  2. 否则,比较的位置移动到下一个元素的地方:iter+1的位置.
    这样,待排序列表的有效大小就会在每次遍历中把最大的元素移动到有序子列表里最终的位置后减少一. 一直重复上面2个步骤知道列表被全部排好序,不需要任何元素交换. 如:有效大小缩减至1.

###特性

  1. 最佳性能:当列表是有序的,那么我们只需遍历一下.因此时间复杂度是 O(n).
  2. 最差性能:当列表是倒序的,那么我们需要遍历N次,每次要N次比较和交换,因此时间复杂度是 O(n2)
  3. 平均性能:时间复杂度是: O(n2)
  4. 这个不需要任意额外的临时变量空间,因此空间复杂度是 O(1)

###冒泡排序-C语言代码

#include <stdio.h>

/*
Logic steps : Do the following thing until the list is sorted
(i) Compare two adjacent elements and check if they are in correct order(that is second one has to be greater than the first).
(ii) Swap them if they are not in correct order.
 */

void BubbleSort(int *array,int number_of_elements)
{
        int iter, temp, swapped;
        do
        {
                swapped = 0; /* If no element is swapped array is sorted */
                /* In the following loop compare every pair of adjacent elements and check if they are in correct order */
                for(iter = 1; iter < number_of_elements; iter++)
                {
                        if(array[iter-1] > array[iter])
                        {
                                temp = array[iter-1];
                                array[iter-1] = array[iter];
                                array[iter] = temp;
                                swapped = 1;
                        }
                }

        }while(swapped);
}
int main(void)
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        BubbleSort(array,number_of_elements); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;

}

Mac OS X中编译WRTNode固件

#1.Disk Image Creation
Mac OS X系统默认的磁盘文件系统是非大小写敏感的,而Openwrt编译环境需要大小写敏感支持,故我们创建一个磁盘映像文件来新建大小写敏感的文件系统.

下面开始用MacOSX系统中自带的命令hdiutil来创建一个新磁盘镜像并挂载到系统中.

Hackintosh:~ Diveinedu$ cd $HOME
Hackintosh:~ Diveinedu$ hdiutil create -size 20g -fs "Case-sensitive HFS+" -volname OpenWrt OpenWrt.dmg
Hackintosh:~ Diveinedu$ hdiutil attach OpenWrt.dmg

上面命令会在我们的主目录下创建一个大小为20G的镜像文件,并格式化为Case-sensitive HFS+的文件系统,卷标名为OpenWrt,然后挂载到系统中.挂载后我们看样子Finder界面的左侧边栏看到他.
我们需要在终端命令行下进入我们刚刚创建好的文件系统对应的目录下去:

Hackintosh:~ Diveinedu$ cd /Volumes/OpenWrt

#2.Packages Installation
下一步我们需要安装搭建OpenWrt编译环境所需的一些软件包,主要是两个部分:

  • XCode IDE: Apple的一个集成开发环境SDK,包含一些核心的库文件和编译器
  • Homebrew: OS X 不可或缺的套件管理器,MacOSX平台的软件包管理系统(类似于Debian/Ubuntu系统里的apt-get),用来下载和安装一些开源项目软件,比如在Unix/Linux/BSD世界里广泛存在而Apple的MacOSX没有自带的软件.http://brew.sh/index_zh-cn.html

XCode的安装:

  • 打开 Mac App Store 应用商店
  • 在右上角的搜索框搜索 "Xcode"
  • 选择 Xcode,然后点击安装
  • 输入你的Apple ID账号和密码,就会开始下载安装.
  • 最后还需要一步,运行下面命令确保命令行开发工具已经安装:
Hackintosh:OpenWrt Diveinedu$ xcode-select --install

如果有弹出窗口,就选择安装他,他会自带去Apple的更新服务器上下载安装的.

Homebrew的安装:

  • 获取 Homebrew, 打开Homebrew的官网中文页面: http://brew.sh/index_zh-cn.html
  • 打开终端窗口, 粘贴以下脚本,脚本会解释它的作用,然后在您的确认下执行安装。
Hackintosh:OpenWrt Diveinedu$ ruby -e "$(curl -fsSL https://raw.github.com/Homebrew/homebrew/go/install)"

基础依赖软件包安装:

  • brew 命令安装:
Hackintosh:OpenWrt Diveinedu$ brew install asciidoc docbook gdbm libxml2 pbzip2 autoconf e2fsprogs gettext libxslt pkg-config bash-completion fastjar gnu-getopt libyaml readline binutils findutils gnu-tar lzlib sqlite bison flex gputils openssl wget coreutils gawk intltool ossp-uuid xz

#3.Checkout the OpenWrt Source
我们可以从OpenWrt的官方网站上的源码仓库里检出代码,用SVN或者Git版本管理工具都可以,我这里推荐使用Git,选择自己需要的源码版本然后用下面的命令检出代码:

  • trunk (main development tree)

Main repository

git clone git://git.openwrt.org/openwrt.git

  • 14.07 branch (Barrier Breaker)

Main repository

git clone git://git.openwrt.org/14.07/openwrt.git

我选择检出14.07分支版本,在之前准备好的文件系统的挂载目录下依次执行如下命令:

Hackintosh:OpenWrt Diveinedu$ git clone git://git.openwrt.org/14.07/openwrt.git
Hackintosh:OpenWrt Diveinedu$ cd openwrt
Hackintosh:openwrt Diveinedu$ ./scripts/feeds update
Hackintosh:openwrt Diveinedu$ ./scripts/feeds install -a

上述命令成功执行完成后,我们就已经准备好了OpenWrt的源码并部署了所有的软件包以供我们后面的编译配置步骤去选择了.

#4. Configure and Build OpenWrt For MT7620

A. 到这里,我们就可以开始为我们的路由器板子进行配置了,比如我现在为我的MT7620N板子进行编译的配置,在命令行执行如下命令:

Hackintosh:openwrt Diveinedu$ make menuconfig

这条命令会在终端显示一个基于ncurses的文本图形菜单,我们在菜单里作如下选择:

Target System (Ralink RT288x/RT3xxx) --->

Subtarget (MT7620n based boards) --->

其他具体的配置项这里就从略...

比如MT7620的WiFi驱动啊, USB存储驱动啊, USB的3G Modem驱动等等,

根据实际需求添加配置.此处只做配置编译过程的演示.

配置好这些合适的编译配置项目后,退出菜单保存设置.


B.此时此刻,万事具备只欠东风,东风就是最后一条编译命令:

Hackintosh:openwrt Diveinedu$ make V=s

由于是第一次编译,这一条命令的时间足够让我们睡一个午觉,如果不想睡觉,那就喝几杯咖啡吧.
如果网络条件好,那么首次编译过程中所需要下载的软件包应该不会遇到什么错误.因为我这次就非常的顺利,不过我是用的VPN番茄了的.

编译完成之后,我们可以在输出目录下查看我们的结果,那就是各种MT7620N方案的路由器板子的固件:

Hackintosh:openwrt Diveinedu$ ls -lh bin/ramips/
total 62344
-rw-r--r--  1 Diveinedu  staff   812B  9  8 20:45 md5sums
-rw-r--r--  1 Diveinedu  staff   3.5M  9  8 20:45 openwrt-ramips-mt7620n-mlw221-squashfs-sysupgrade.bin
-rw-r--r--  1 Diveinedu  staff   2.5M  9  8 20:45 openwrt-ramips-mt7620n-root.squashfs
-rw-r--r--  1 Diveinedu  staff   3.5M  9  8 20:45 openwrt-ramips-mt7620n-rt-n14u-squashfs-sysupgrade.bin
-rw-r--r--  1 Diveinedu  staff   1.0M  9  8 20:45 openwrt-ramips-mt7620n-uImage.bin
-rwxr-xr-x  1 Diveinedu  staff   2.9M  9  8 20:45 openwrt-ramips-mt7620n-vmlinux.bin
-rwxr-xr-x  1 Diveinedu  staff   3.0M  9  8 20:45 openwrt-ramips-mt7620n-vmlinux.elf
-rw-r--r--  1 Diveinedu  staff   3.5M  9  8 20:45 openwrt-ramips-mt7620n-wmr-300-squashfs-sysupgrade.bin
-rw-r--r--  1 Diveinedu  staff   3.5M  9  8 20:45 openwrt-ramips-mt7620n-wr8305rt-squashfs-sysupgrade.bin
-rw-r--r--  1 Diveinedu  staff   3.5M  9  8 20:45 openwrt-ramips-mt7620n-wrtnode-squashfs-sysupgrade.bin
-rw-r--r--  1 Diveinedu  staff   3.5M  9  8 20:45 openwrt-ramips-mt7620n-zbt-wa05-squashfs-sysupgrade.bin
drwxr-xr-x  4 Diveinedu  staff   136B  9  8 20:20 packages
Hackintosh:openwrt Diveinedu$

选择我们板子对应的固件,比如我们罗老湿的 WRTNode ,那就选择bin/ramips/openwrt-ramips-mt7620n-wrtnode-squashfs-sysupgrade.bin, 然后scp上传到路由器里或者通过TTL+TFTP的方式进行刷机测试.
如果是采用TTL+TFTP的方式,那我们还需要安装一个minicom工具.同样,在命令行运行命令:

Hackintosh:openwrt Diveinedu$ brew install minicom

安装完成之后运行minicom,设置正确的设备文件和正确的波特率:

Hackintosh:openwrt Diveinedu$ minicom -s

公司笔记本使用USB转串口的适配器在MacOSX里的设备文件的话,一般是/dev/tty.USBxxx这样的文件,像我现在家里所使用的台式机黑苹果的画,主板上的串口对应的设备文件是/dev/tty.serial1.具体看芯片的驱动是怎么样命名.

到此,在Mac OS X 10.9.4系统中进行OpenWrt智能路由器,嵌入式Linux开发环境搭建和编译的步骤就介绍完成.