注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

笑遍世界@网易博客

明天还会在路上……

 
 
 

日志

 
 
关于我

Stay hungry, stay foolish. 工作用脑,生活用心! 走过山重水复,必然迎来柳暗花明! 受苦的人没有悲观的权利,远征的人没有流泪的资格。 Live each day as if we should die tomorrow.

网易考拉推荐
 
 

常用排序算法(C语言版)  

2010-11-01 23:54:34|  分类: 编程技术 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       本文中的代码是根据网上的C++代码,经过简单的修改而得到的C代码,可以直接编译运行(本人采用gcc编译运行的)。将代码贴在这里留个纪念吧,这些东东是经常都用得上的。 (下次再把这些常见的排序算法的效率和优劣势都总结分析一下吧)
       包括:冒泡排序、选择排序、插入排序、快速排序、计数排序、归并排序、堆排序、希尔排序等。

非常感谢原帖作者,原帖见:
http://topic.csdn.net/u/20100327/16/9983a96e-3a26-489f-8590-a51dd4c4476d.html
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>

#define SIZE 100
#define MAX 1000

//交换数据
void Swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

// 冒泡排序
void BubbleSort(int *arr, int size)
{
    int i, j;
    for(i=0;i<size-1;i++)
        for(j=size-1;j>i;j--)
            if(arr[j] < arr[j-1])
                Swap(&arr[j], &arr[j-1]);
}

//选择排序
void SelectionSort(int *arr, int size)
{
    int i, j, min;
    //找出从a[i]到a[size-1]的最小元素的位置
    for(i=0;i<size-1;i++)
    {
        min = i;
        for(j=i+1;j<size;j++)
            if(arr[min] > arr[j])
                min = j;
        //将a[i]与a[min]的数据交换
        Swap(&arr[i], &arr[min]);
    }
}

//插入排序
void InsertSort(int *arr, int size)
{
    int fOut, loc, temp;
    for(fOut=1;fOut<size;fOut++)
        if(arr[fOut] < arr[fOut-1])
        {
            temp = arr[fOut];
            loc = fOut;
            do
            {
                arr[loc] = arr[loc-1];
                loc--;
            }while(loc>0 && arr[loc-1]>temp);
            arr[loc] = temp;
        }
}

//快速排序
int Partition(int *arr, int first, int last)
{
    int i, small, x;
    //为了减少最差情况的出现频率而作的一种优化
    Swap(&arr[first], &arr[(first+last)/2]);
    x = arr[first];
    small = first;
    for(i=first+1;i<=last;i++)
        if(arr[i] < x)
        {
            small++;
            Swap(&arr[small], &arr[i]);
        }
        Swap(&arr[first], &arr[small]);
        return small;
}

void RecQuick(int *arr, int first, int last)
{
    int pivotLoc;
    if(first < last)
    {
        pivotLoc = Partition(arr, first, last);
        RecQuick(arr, first, pivotLoc-1);
        RecQuick(arr, pivotLoc+1, last);
    }
}

void QuickSort(int *arr, int size)
{
    RecQuick(arr, 0, size-1);
}

//计数排 序
void CountSort(int *arr, int size)
{
    int temp[MAX] = {0};
    int i, j;
    for(i=0;i<size;i++)
        temp[arr[i]]++;
    j = 0;
    for(i=0;i<MAX;i++)
    {
        while(0 != temp[i])
        {
            arr[j] = i;
            temp[i]--;
            j++;
        }
    }
}

//归并排序
void Merge(int *arr, int start, int mid, int end)
{
    int temp1[SIZE], temp2[SIZE];
    int n1, n2;
    int i, j, k;
    n1 = mid - start + 1;
    n2 = end - mid;
    //拷贝前半部分数组
    for(i=0;i<n1;i++)
        temp1[i] = arr[start + i];
    //拷贝后半部分数组
    for(i=0;i<n2;i++)
        temp2[i] = arr[mid + i + 1];
    //把后面的元素设置的很大
    temp1[n1] = temp2[n2] = INT_MAX;
    i = j = 0;
    // 逐个扫描两部分数组然后放到相应的位置去
    for(k=start;k<=end;k++)
    {
        if(temp1[i] <= temp2[j])
        {
            arr[k] = temp1[i];
            i++;
        }
        else
        {
            arr[k] = temp2[j];
            j++;
        }
    }
}

void RecMerge(int *arr, int start, int end)
{
    int i;
    if(start < end)
    {
        i = (start + end) / 2;
        RecMerge(arr, start, i);
        RecMerge(arr, i+1, end);
        Merge(arr, start, i, end);
    }
}

void MergeSort(int *arr, int size)
{
    RecMerge(arr, 0, size-1);
}

//堆排序
void Heapify(int *arr, int low, int high)
{
    int large;
    int temp = arr[low];
    large = 2 * low + 1;
    while(large <= high)
    {
        if(large<high && arr[large]<arr[large+1])
            large = large + 1;
        if(temp > arr[large])
            break;
        else
        {
            arr[low] = arr[large];
            low = large;
            large = 2 * low + 1;
        }
    }
    arr[low] = temp;
}

void BuildHeap(int *arr, int size)
{
    int i;
    for(i=size/2-1;i>=0;i--)
        Heapify(arr, i, size-1);
}

void HeapSort(int *arr, int size)
{
    int i;        //lastOfOrder
    BuildHeap(arr, size);
    for(i=size-1;i>=0;i--)
    {
        Swap(&arr[0], &arr[i]);
        Heapify(arr, 0, i-1);
    }
}

//希尔排序
void ShellSort(int *arr, int size)
{
    int i, j, k, temp;
    //i为增量
    for(i=size/2;i>0;i/=2)
    {
        for(j=i;j<size;j+=i)
        {
            temp = arr[j];
            k = j;
            while(k-i>=0 && temp<arr[k-i])
            {
                arr[k] = arr[k-i];
                k -= i;
            }
            arr[k] = temp;
        }
    }
}

//输出数组里的数据
void Print(int *arr, int size)
{
    int i;
    for(i=0;i<size;i++)
    {
        printf("%6d ", arr[i]);
        if(0 == (i+1) % 10)
            printf("\n");
    }
    printf("\n");
}

//主函数
//先随机选择100个整型数据放入数组中,并输出
//然后将其从小到 大排序,并输出
int main()
{
    int arr[SIZE], i;
    printf("The array is:\n");
    srand((unsigned)time(0));
    for(i=0;i<SIZE;i++)
        arr[i] = rand() % MAX;
    Print(arr, SIZE);

    //请选择其中一个排序算法,以运行该程序
    BubbleSort(arr, SIZE);
//     SelectionSort(arr, SIZE);
//     CountSort(arr, SIZE);
//     InsertSort(arr, SIZE);
//     SelectionSort(arr, SIZE);
//     QuickSort(arr, SIZE);
//     MergeSort(arr, SIZE);
//     HeapSort(arr, SIZE);
//     ShellSort(arr, SIZE);

    printf("After sorting, the array is:\n");
    Print(arr, SIZE);
    return 0;
}
  评论这张
 
阅读(588)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017