C语言排序方法(冒泡,选择,插入,归并,快速)

目录
  • 1.冒泡排序
  • 2.选择排序
  • 3.插入排序
  • 4.归并排序
  • 5.快速排序
  • 总结

1.冒泡排序

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

算法步骤 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

执行过程:

# include <stdio.h>
# include <string.h>
int main(void)
{
    int arr[] = {5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};
    int len= sizeof(arr) / sizeof(arr[0]);;
    int i;  //比较的轮数
    int j;  //每轮比较的次数
    int temp;  //交换数据时用于存放中间数据
    for (i=0; i<len-1; ++i)  //比较n-1轮
    {
        for (j=0; j<len-1-i; ++j)  //每轮比较n-1-i次,
        {
            if (arr[j] < arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    printf("排序后:\n");
    for (i=0; i<len; ++i)
    {
        printf("%d\x20", arr[i]);
    }
    printf("\n");
    return 0;
}

2.选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

算法步骤 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
再从剩余未排序元素中继续
寻找最小(大)元素,然后放到已排序序列的末尾。

重复第二步,直到所有元素均排序完毕。

代码:

#include <stdio.h>
# include <string.h>
int main() {
        int arr[] = { 5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};
        int len = (int) sizeof(arr) / sizeof(*arr);
       int i, j, temp;
        for (i = 0; i < len - 1; i++)
                for (j = 0; j < len - 1 - i; j++)
                        if (arr[j] > arr[j + 1]) {
                                temp = arr[j];
                                arr[j] = arr[j + 1];
                                arr[j + 1] = temp;
                        }
        for (i = 0; i < len; i++)
                printf("%d ", arr[i]);
        return 0;
}

3.插入排序

插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 [2] 。

算法步骤 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

#include <stdio.h>
# include <string.h>
int main(){
     int arr[] = { 5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};
  int len = (int) sizeof(arr) / sizeof(*arr);
	int i,j,x;
    for( i= 1; i<len; i++){
        if(arr[i] < arr[i-1]){//若第 i 个元素大于 i-1 元素则直接插入;反之,需要找到适当的插入位置后在插入。
             j= i-1;
             x = arr[i];
            while(j>-1 && x < arr[j]){  //采用顺序查找方式找到插入的位置,在查找的同时,将数组中的元素进行后移操作,给插入元素腾出空间
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = x;      //插入到正确位置
        }
}
    for(j=0; j<len; j++){
        printf("%d ",arr[j]);
    }
    printf("\n");
    return 0;
}

4.归并排序

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:

自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);

自下而上的迭代;

算法步骤 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

设定两个指针,最初位置分别为两个已经排序序列的起始位置;

比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

重复步骤 3 直到某一指针达到序列尾;

将另一序列剩下的所有元素直接复制到合并序列尾。
#include <stdio.h>
#define MAXSIZE 10

// 递归的方式实现归并排序

// 实现归并,并把结果存放到list1

# include <string.h>
#include <stdio.h>
void merging(int *list1, int list1_size, int *list2, int list2_size) {
    int i,j,k, m;
    int temp[MAXSIZE];
    i = j = k = 0;
    while(i < list1_size && j < list2_size)
    {
        if(list1[i] < list2[j])
        {
            temp[k] = list1[i];
            k++;
            i++;
        }
        else
        {
            temp[k++] = list2[j++];
        }
    }
    while(i < list1_size)
    {
        temp[k++] = list1[i++];
    }
    while(j < list2_size)
    {
        temp[k++] = list2[j++];
    }
    for(m = 0;m < (list1_size + list2_size);m++)
    {
        list1[m] = temp[m];
    } }
void MergeSort(int k[], int n) {
    if(n > 1)
    {
        /*
        *list1是左半部分,list2是右半部分
        */
        int *list1 = k;
        int list1_size = n/2;
        int *list2 = k + list1_size;
        int list2_size = n - list1_size;
        MergeSort(list1, list1_size);
        MergeSort(list2, list2_size);
        // 把两个合在一起
        merging(list1, list1_size, list2, list2_size);
    }
}
int main() {
    int i, arr[] = { 5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};    int len = (int) sizeof(arr) / sizeof(*arr);
    MergeSort(arr, len);
    printf("排序后的结果是:");
    for(i = 0;i < len;i++)
    {
        printf("%d", a[i]);
    }
    printf("\n\n");
    return 0;
}

5.快速排序

原理:

   快速排序,给基准数据找其正确索引位置的过程.

   如下图所示,假设最开始的基准数据为数组第一个元素23,则首先用一个临时变量去存储基准数据,即tmp=23;然后分别从数组的两端扫描数组,设两个指示标志:low指向起始位置,high指向末尾.

   如果扫描到的值大于基准数据就让high减1,如果发现有元素比该基准数据的值小(如上图中18<=tmp),就将high位置的值赋值给low位置。

   如果扫描到的值小于基准数据就让low加1,如果发现有元素大于基准数据的值(如上图46=>tmp),就再将low位置的值赋值给high位置的值.

算法步骤 从数列中挑出一个元素,称为 “基准”(pivot);

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

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

#include "stdio.h"
typedef struct _Range {
    int start, end;    //开始指向分别指向两端
} Range;
Range new_Range(int s, int e) {
    Range r;
    r.start = s;     //开始指向需要排序数组的两端
    r.end = e;
    return r;   //返回一个结构体
}
void swap(int *x, int *y) {   //交换数据函数
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort(int arr[], const int len) {
    if (len <= 0)
        return;    //保证数据长度大于0
    Range r[len];
    int p = 0;
    r[p++] = new_Range(0, len - 1);
    while (p) {
        Range range = r[--p];
        if (range.start >= range.end)
            continue;
        int mid = arr[(range.start + range.end) / 2]; // 选取中间点作为基准点
        int left = range.start, right = range.end;
        do {
            while (arr[left] < mid) ++left;   // 检测基准点左侧是否符合要求
            while (arr[right] > mid) --right; //检测基准点右侧是否符合要求
            if (left <= right) {
                swap(&arr[left], &arr[right]);
                left++;
                right--;               // 移動指針以繼續
            }
        } while (left <= right);
        if (range.start < right) r[p++] = new_Range(range.start, right);
        if (range.end > left) r[p++] = new_Range(left, range.end);
    }
}
int main()
{
	int j;
	  int arr[] = { 5, 2, 3, -8, 34, 76, 32, 43, 0, -70, 35, 543, 6};
        int len = (int) sizeof(arr) / sizeof(*arr);
        quick_sort(arr,len);
            for(j=0; j<len; j++){
        printf("%d ",arr[j]);
    }
    printf("\n");
}

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • C语言排序算法之冒泡排序实现方法【改进版】

    本文实例讲述了C语言排序算法之冒泡排序实现方法.分享给大家供大家参考,具体如下: 冒泡排序和改进的冒泡排序 /*------------------------------------------------------------------------------------------- Bubble_sort.h 冒泡排序: 时间复杂度为O(N^2) 改进的冒泡排序: 时间复杂度仍为O(N^2) 一般的冒泡排序方法有可能会在已经排好序的情况下继续比较,改进的冒泡排序 设置了一个哨兵fla

  • C语言所有经典排序方法的实现代码

    运行结果正确 还是快速排序难一些. 完整代码 #include<stdio.h> #include <stdlib.h> #include <string.h> #include<malloc.h> void swap(int *a,int *b); void select_sort(int arr[],int n); void tra_arr(int arr[],int n); void insert_sort(int arr[],int n); void

  • C语言实现3个数从小到大排序/输出的方法示例

    前言 本文主要给大家介绍了一个功能,任意输入 3 个整数,编程实现对这 3 个整数由小到大进行排序.下面话不多少了,来一起看看详细的介绍吧 实现过程: (1)定义数据类型,本实例中 a.b.c.t 均为基本整型. (2) 使用输入函数获得任意 3 个值赋给 a.b.c. (3) 使用 if 语句进行条件判断,如果 a 大于 b,则借助于中间变量 t 互换 a 与 b 值, 依此类推比较 a 与 c.b 与 c,最终结果即为 a.b.c 的升序排列. (4) 使用输出函数将 a.b.c 的值依次输

  • 使用C语言实现12种排序方法

    1.冒泡排序 思路:比较相邻的两个数字,如果前一个数字大,那么就交换两个数字,直到有序. 时间复杂度O(n^2),稳定性:这是一种稳定的算法. 代码实现: void bubble_sort(int arr[],size_t len){ size_t i,j; for(i=0;i<len;i++){ bool hasSwap = false; //优化,判断数组是否已经有序,如果有序可以提前退出循环 for(j=1;j<len-i;j++){ //这里j<len-i是因为最后面的肯定都是最

  • C语言实现桶排序的方法示例

    本文实例讲述了C语言实现桶排序的方法.分享给大家供大家参考,具体如下: 一.定义 假定:输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数.将区间[0, 1)划分为n个大小相等的子区间(桶),每桶大小1/n:[0, 1/n), [1/n, 2/n), [2/n, 3/n),-,[k/n, (k+1)/n ),-将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组,指向桶(链表). 二.性能 对于N个待排数据,

  • C语言排序方法(冒泡,选择,插入,归并,快速)

    目录 1.冒泡排序 2.选择排序 3.插入排序 4.归并排序 5.快速排序 总结 1.冒泡排序 它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把他们交换过来.走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成. 算法步骤 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重

  • 详解Python排序算法的实现(冒泡,选择,插入,快速)

    目录 1. 前言 2. 冒泡排序算法 2.1 摆擂台法 2.2 相邻两个数字相比较 3. 选择排序算法 4. 插入排序 5. 快速排序 6. 总结 1. 前言 所谓排序,就是把一个数据群体按个体数据的特征按从大到小或从小到大的顺序存放. 排序在应用开发中很常见,如对商品按价格.人气.购买数量……显示. 初学编程者,刚开始接触的第一个稍微有点难理解的算法应该是排序算法中的冒泡算法. 我初学时,“脑思维”差点绕在 2 个循环结构的世界里出不来了.当时,老师要求我们死记冒泡的口诀,虽然有点搞笑,但是当

  • 图解Java经典算法冒泡选择插入希尔排序的原理与实现

    目录 一.冒泡排序 1.基本介绍 2.代码实现 二. 选择排序 1.基本介绍 2.代码实现 三.插入排序 1.基本介绍 2.代码实现 四.希尔排序 1.基本介绍 2.代码实现(交换排序) 3.代码实现(移位排序) 一.冒泡排序 1.基本介绍 冒泡排序是重复地走访要排序的元素,依次比较两个相邻的元素,如果它们的顺序与自己规定的不符合,则把两个元素的位置交换.走访元素重复地进行,直到没有相邻元素需要交换为止,完成整个排序过程. 算法原理 1.比较相邻元素,如果前一个元素大于后一个元素,则交换. 2.

  • 关于Python排序问题(冒泡/选择/插入)

    前言: 学过C语言肯定接触过排序问题,我们最常用的也就是冒泡排序.选择排序.插入排序……等等,同样在Python中也有排序问题,这里我也会讲解Python中冒泡排序.选择排序和插入排序的写法和思维,上正文! (这里我是以列表作为一个排序对象) 1.冒泡排序 冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.

  • Java轻松入门冒泡 选择 插入 希尔 归并排序算法

    今天我们主要看一些简单的排序 常见的时间复杂度 常数阶Ο(1) 对数阶Ο(log2n) 线性阶Ο(n) 线性对数阶Ο(nlog2n) 平方阶Ο(n²) 立方阶Ο(n³) K次方阶Ο(n^k) 指数阶Ο(2^n) 常见的时间复杂度对应图 Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n²)<Ο(n³)<…<Ο(2^n) <Ο(n!)<O(n^n) 冒泡排序(Quicksort) 算法描述: ①. 比较相邻的元素.如果第一个比第二个大,就交

  • C语言排序算法之选择排序(直接选择排序,堆排序)

    目录 前言 一.直接选择排序 1.1 算法思想 1.2 代码实现 1.3 直接选择排序的特征总结 二.堆排序 2.1 什么是堆? 2.2 判断是否是堆 2.3 向下调整算法 2.4 自底向上的建堆方式 2.5 代码实现 2.6 堆排序的特性总结 2.7 堆排序的特性总结 前言 本期为大家带来的是常见排序算法中的选择排序,主要有直接选择排序以及——堆排序(有点难理解),包您一看就会,快来试试吧~ 一.直接选择排序 1.1 算法思想 每一次从待排序的数据元素中选出最小(或最大的)的一个元素,存放在序

  • java中常用的排序方法

    复制代码 代码如下: package com.test; import java.util.Random; /** * 排序测试类 *  * 排序算法的分类如下: 1.插入排序(直接插入排序.折半插入排序.希尔排序): 2.交换排序(冒泡泡排序.快速排序): * 3.选择排序(直接选择排序.堆排序): 4.归并排序: 5.基数排序. *  * 关于排序方法的选择: (1)若n较小(如n≤50),可采用直接插入或直接选择排序. * 当记录规模较小时,直接插入排序较好:否则因为直接选择移动的记录数少

  • C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)

    目录 前言 选择排序 冒泡排序 插入排序 归并排序 希尔排序 快速排序 堆排序 计数排序 总结 前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏.但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效. 选择排序 选择排序几乎是最无脑的一种排序算法,通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位:再从数组中剩下的数里选出最大(小)的,放到第二位,依次类推. 算法步骤 设数组有n个元素,{ a 0 , a 1 , - , a n } 从数组第

  • 数据结构与算法 排序(冒泡,选择,插入)

    数据结构与算法 排序(冒泡,选择,插入) 1.冒泡排序 1.1算法 冒泡排序(buddle-sort)算法的运作如下:(从后往前) 比较相邻的元素.如果第一个比第二个大,就交换他们两个. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 针对所有的元素重复以上的步骤,除了最后一个. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 1.2 实现 // // main.c // BubbleSort // // Created

  • Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

    本文实例讲述了Go语言实现冒泡排序.选择排序.快速排序及插入排序的方法.分享给大家供大家参考.具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法.排序算法有许多种,这里介绍4中排序算法:冒泡排序,选择排序,快速排序和插入排序,以从小到大为例. 一.冒泡排序 冒泡排序的原理是,对给定的数组进行多次遍历,每次均比较相邻的两个数,如果前一个比后一个大,则交换这两个数.经过第一次遍历之后,最大的数就在最右侧了:第二次遍历之后,第二大的数就在右数第二个位置了:以此类推. 复制代码 代码如下:

随机推荐