c语言各种排序算法的实现.doc

. . . .
在学习算法的过程中，排序算法是很基础的。下面我用C语言实现了5中基础的排序算法：插入排序、选择排序、冒泡排序、并归排序、快速排序。
1.>插入排序
插入排序很简单，在《算法导论》中的解释是这样的。插入排序的工作机理与很多人打牌时，整理手上的牌的做法差不多。开始的时候我们的左手是空的。接着我们从桌面上一一的摸牌，并将它放到左手的一个正确的位置上。为了找到这个正确的位置，要将它与左手的牌从右到左地进行比较，无论在什么
时候左手的牌都是排好序的。很简单吧,不过当初为了理解这个算法也花了一点时间，下面是C语言对插入排序的一个简单实现：
帮助
1
2
3
4
5
6
7
8
9
10
11
12
13
//插入排序 int insert_sort(int a[],int size)
{
    int i,j,temp;
    for(i = 1;i < size;i++){
        temp = a[i];
        for(j = i-1;j >=0 && temp < a[j];j--)
            a[j+1] = a[j];

        a[j+1] = temp;
    }
    return0;
}//end insert_sort
2>.选择排序
选择排序的工作原理是这样的，对数据进行遍历，找出最小的元素（升序）作为第一个元素，再在剩下的数中找出最小的作为第二个元素，一直循环下去，最后的你会发现这个数组中的数据已经排好序了。下面是C语言的选择排序的一个简单实现：
帮助
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//选择排序  int select_sort(int a[],int size)
{
    int i,j,temp;
    for(i = 0;i < size;i++){
        for(j = i+1;j < size;j++)
            if(a[i] > a[j]){
                //交换位置                 temp = a[i];
                a[i] = a[j];
                a[j] = temp; 
            }
    }
    return0;
}//end select_sort
3>.冒泡排序
冒泡排序是重复交换相邻的两个反序元素。它的工作工作机理我觉得跟选择排序差不多。因为在第一个遍历整个数组交换反序元素之后，数组的第一个元素
就已经是整个数组中最小的元素了。下面是C语言实现的一个冒泡排序。
帮助
1
2
3
4
5
6
7
8
9
10
11
12
//冒泡排序 int bubble_sort(int data[],int size)
{
    int i,j,temp;
    for(i = 0;i < size;i++)
        for(j = size - 1;j > i;j--)
            if(data[j] < data[j-1]){
                temp = data[j];
                data[j] = data[j-1];
                data[j-1] = temp;
            }
}//end bubble_sort
4>.并归排序
并归排序，你也可以叫它合并排序。它采用了递归的思想，将数据分成两个部分，将这两个部分排好序之后再进行合并，一直重复这个过程，得出最后的结
果。可能说的比较抽象，大家看下面的代码。
帮助
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//合并两个已经排好的结果  int merg_result(int data[],int start,int middle,int end)
{
    int s1,s2,
        i,i1,i2;
    s1 = middle-start+1;
    s2 = end - middle;

    i1 = i2 = 0;
    //两个临时的数组      int temp1[s1],temp2[s2];
    //复制数据前后两个段的数据进临时数组     for(i = 0;i < s1;i++)
        temp1[i] = data[start+i];
    for(i = 0;i < s2;i++)
        temp2[i] = data[middle+1+i]; 

    //开始合并     for(i = start;i < s1+s2+start;i++){
        if(temp1[i1] < temp2[i2]){
            if(i1 >= s1)
                break;//无法将两个临时数组的最后一个
元素设为无穷大 
            data[i] = temp1[i1++];
        }
        else{
            if(i2 >= s2)
                break;
            data[i] = temp2[i2++];
        }
    }  
    //添加两个循环，将最后的数据合并好     while(i1 < s1)
        data[i++] = temp1[i1++];
    while(i2 < s2)
        data[i++] = temp2[i2++];                              

}//end merg_result //并归排序  int merg_sort(int data[],int start,int end)
{
    int middle;
    if(start < end){
        middle = (start+end)/2;
        //分治           merg_sort(data,start,middle);
        merg_sort(data,middle+1,end);
        //合并结果         merg_result(data,start,middle,end);
    }
    return0;
}//end merg_sort
有两个函数，主例程将数组分成2个部分，然后递归调用自身，最后再调用合并函数合并最后的结果。更多关于合并排序的容在这里。
5>.快速排序
这是我觉得最神奇的一个。前面3个排序时间代价都是O(n2)，虽然并归排序的时间O(nlgn）。但是由于合并过程中需要的临时数组，使得它占用的栈空间相当大，在我的机子上（2G存）排序50万的整形数据程序就会崩溃，存不够了。而快速排序虽然也是递归的，但是它完全在本地工作，不需要申请额外的空间，所以很方便。下面是我用C语言写的一个快速排序的例程，
帮助
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//合并两个已经排好的结果  int partition(int data[],int start,int end)
{
    int key,
        i,j,temp;

    //选取最后一个元素作为主元素     key = data[end];

    i = start; 

    for(j = start;j < end;j++){
        if(data[j] <= key){
            //交换data[j]与data[i]             temp = data[i];
            data[i++] = data[j];
            data[j] = temp;
        }

    }
    //将主元素换到i位置     temp = data[i];
    data[i] = data[end];
    data[end] = temp; 
    //返回主元素的位置      //printf("%d ",i);     returni; 
}//end partition //并归排序  int quick_sort(int data[],int start,int end)
{
    int middle;
    if(start < end){
        middle = partition(data,start,end);
        quick_sort(data,start,middle-1);
        quick_sort(data,middle+1,end);
    }
    return0;
}//end quick_sort
这只是我理解的快速排序一个很简单的实现。更多有关快速排序的原理你可以看这里
上面的代码都是我在理解算法之后写出来的，当然可能有一些bug，如果你发现
了请联系我。：）
关于算法性能的分析，我实在不在行。在书上说的这几个算法性能上，前3个是O(n2）,后两个是O(nlgn)。说实话我对这些的理解不是很够。于是我自己写了一个测试程序在我的笔记本上跑了下。我的方式是随机生成数据，然后使用不同的排序算法进行测试，当然几百个数据几乎一瞬间就可以解出，所以我在测试的时候是对1000次（或者更多）排序的总时间进行统计。
通过统计结果，我发现插入排序在对于小量的数据，效果很好。但是在数据太大的时候就不能和并归排序和快速排序进行比较了。这个数据的间值在200左右。而快速排序不管是大数据还是小数据的效果都非常好，有些时候比插入排序还好。当然，这是我没有遇到传说中的坏数据，因为坏数据是有可能让快速排序的时间达到O(n2)的。
这个文件是我测试的结果，有一些我连续测了几次，结果都差不多。你可以看看。当然，你可能会看的眼花。
寒假过了这么久，在家看游戏设计方面的是容。参考书是《windows游戏编程大师技巧》。终于会读取bmp位图了，并且还按照书上做了一个小动画。哈哈，过几天再把整理的一个容发到博客上。快过年了，提前祝大家新年快乐！：
）

7 / 7