C语言学习:关于数据的几种排序算法

数据结构的排序算法有很多种。
其中,快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法;
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

以下整理的5种排序算法

以下是几种排序算法的代码:

选择排序

基本思路:每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

void select_sort(int * a,int n)
{
    int i = 0;
    int j = 0;
    int temp = 0;
    for(i = 0;i < n;i++)
    {
        for(j = i + 1;j < n;j++)
        {
            if(a[i] > a[j])
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    return;
}
冒泡排序

基本思路:重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

void bul_sort(int * a,int n)
{
    int i,j,t;
    for(j = 1;j < n;j++)
    {
        for(i = 0;i < n-j;i++)
        {
            if(a[i] < a[i+1])
            {
                t = a[i];
                a[i] = a[i+1];
                a[i+1] = t;
            }
        }
    }
    return;
}
归并排序

基本思路:(假设序列共有n个元素)

  1. 将序列每相邻两个数字进行归并操作,形成n/2个序列,排序后每个序列包含两个元素;
  2. 将上述序列再次归并,形成n/4个序列,每个序列包含四个元素;
  3. 重复上一个步骤,直到所有元素排序完毕。
void merge_sort(int * a,int n)
{
    if(n > 1)
    {
        int * list1 = a;
        int list1_size = n/2;
        int * list2 = a + n/2;
        int list2_size = n - list1_size;

        merge_sort(list1,list1_size);
        merge_sort(list2,list2_size);

        merging(list1,list1_size,list2,list2_size);
    }
}
void merging(int * list1,int list1_size,int * list2,int list2_size)
{
    int temp[N];
    int i = 0,j = 0,k = 0,m;//i sui yin list1,j sui yin list2,k sui yin temp
    while(i < list1_size && j < list2_size)
    {
        if(list1[i] < list2[j])
        {
            temp[k] = list1[i];
            k++;
            i++;
        }
        else
        {
            temp[k] = list2[j];
            k++;
            j++;
        }
    }
    while(i < list1_size)
    {
            temp[k] = list1[i];
            k++;
            i++;
    }
    while(j < list2_size)
    {
            temp[k] = list2[j];
            k++;
            j++;
    }
    for(m = 0;m < (list1_size + list2_size);m++)
    {
        list1[m] = temp[m];
    }
    return;
}
快速排序

基本思路:
快速排序是找出一个元素作为基准,然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值,如此作为基准的元素调整到排序后的正确位置。

void quik_sort(int * a,int n)
{
    if(n < 2)
    {
        return;
    }
    int low = 0;
    int high = n - 1;
    int key = a[0];
    while(low < high)
    {
        while(low < high && key < a[high])
        {
            high--;
        }
        if(low < high)
        {
            a[low] = a[high];
            low++;
        }
        while(low < high && key > a[low])
        {
            low++;
        }
        if(low < high)
        {
            a[high] = a[low];
            high--;
        }
    }
    a[low] = key;
    quik_sort(a,low);
    quik_sort(a+low+1,n-low-1);
}
链接
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Ba la la la ~ 读者朋友们,你们好啊,又到了冷锋时间,话不多说,发车! 1.冒泡排序(Bub...
    王饱饱阅读 1,815评论 0 7
  • 该篇文章主要介绍了算法基础以及几种常见的排序算法:选择排序、插入排序、冒泡排序、快速排序、堆排序。 一、算法基础 ...
    ZhengYaWei阅读 1,269评论 0 12
  • 一、直接插入排序 直接插入排序(Insertion Sort)的基本思想是:每次将一个待排序的元素记录,按其关键字...
    kevin16929阅读 575评论 0 0
  • 17 后核时代 M和F离开后不久,Y和R也告别了。意外的是,他加入一家英语培训机构,帮老板打理一个培训点。至此,早...
    一般般笨的猫阅读 295评论 0 0
  • 一日无课。 早,九时,艳阳高照,欣然而起,自觉起之甚早而颇为得意。携盥而出,未佩眼镜。至水房,见有一人,未敢相认,...
    一树梅花小阅读 351评论 1 3