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

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

1.冒泡排序

1.1算法

冒泡排序(buddle-sort)算法的运作如下:(从后往前)

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

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

1.2 实现

//
// main.c
// BubbleSort
//
// Created by Wuyixin on 2017/6/2.
// Copyright © 2017年 Coding365. All rights reserved.
// 

#include <stdio.h> 

void bubbleSort(int a[],int n){
  int i,j;
  for (i = 0; i < n - 1; i++) {
    for (j = 0; j < n - i; j++) {
      if (a[j] > a[j + 1]){
        int temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
      }
    }
  }
} 

int main(int argc, const char * argv[]) { 

  int a[] = {9,3,1,4,7,6,5,8,2};
  bubbleSort(a, 9);
  int i = 0;
  while (i < 9)
    printf("%d ",a[i++]); 

  return 0;
}

2.选择排序

2.1 算法

选择排序(selection-sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完

2.2实现

//
// main.c
// SelectionSort
//
// Created by Wuyixin on 2017/6/2.
// Copyright © 2017年 Coding365. All rights reserved.
// 

#include <stdio.h> 

void selectionSort(int a[],int n){
  int i,j,min,temp; 

  for (i = 0; i < n; i++) {
    min = i;
    for (j = i + 1; j < n; j++) {
      if (a[j] < a[min])
        min = j;
    }
    if (i != min){
      temp = a[i];
      a[i] = a[min];
      a[min] = temp;
    }
  }
} 

int main(int argc, const char * argv[]) {
  int a[] = {9,3,1,4,7,6,5,8,2};
  selectionSort(a, 9);
  int i = 0;
  while (i < 9)
    printf("%d ",a[i++]);
  return 0;
}

3.插入排序

3.1 算法

插入排序(insertion-sort)的基本思想是:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

3.2 实现

//
// main.c
// InsertionSort
//
// Created by Wuyixin on 2017/6/2.
// Copyright © 2017年 Coding365. All rights reserved.
// 

#include <stdio.h> 

void insertionSort(int a[],int n){
  int i,j,temp;
  for (i = 1; i < n ; i++) {
    temp = a[i];
    for (j = i; j > 0 && temp < a[j - 1]; j--) {
      a[j] = a[j - 1];
    }
    a[j] = temp;
  }
} 

int main(int argc, const char * argv[]) {
  int a[] = {9,3,1,4,7,6,5,8,2};
  insertionSort(a, 9);
  int i = 0;
  while (i < 9)
    printf("%d ",a[i++]);
  return 0;
}

以上就是对C语言数据结构与算法中排序的讲解,大家如有疑问可以留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

  • C++ 数据结构 堆排序的实现

    堆排序(heapsort)是一种比较快速的排序方式,它的时间复杂度为O(nlgn),并且堆排序具有空间原址性,任何时候只需要有限的空间来存储临时数据.我将用c++实现一个堆来简单分析一下. 堆排序的基本思想为: 1.升序排列,保持大堆:降序排列,保持小堆: 2.建立堆之后,将堆顶数据与堆中最后一个数据交换,堆大小减一,然后向下调整:直到堆中只剩下一个有效值: 下面我将简单分析一下: 第一步建立堆: 1.我用vector顺序表表示数组: 2.用仿函数实现大小堆随时切换,实现代码复用: 3.实现向下

  • C语言 数据结构堆排序顺序存储(升序)

    堆排序顺序存储(升序) 一: 完全二叉树的概念:前h-1层为满二叉树,最后一层连续缺失右结点! 二:首先堆是一棵全完二叉树: a:构建一个堆分为两步:⑴创建一棵完全二叉树      ⑵调整为一个堆 (标注:大根堆为升序,小根堆为降序) b:算法描述:①创建一棵完全二叉树 ②while(有双亲){ A:调整为大根堆: B:交换根和叶子结点: C:砍掉叶子结点: } c:时间复杂度为 O(nlogn)  ,空间复杂度为 O(1), 是不稳定排序! 代码实现: /*堆排序思想:[完全二叉树的定义:前

  • C语言中数据结构之链表归并排序实例代码

    C语言中数据结构之链表归并排序实例代码 问题 设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增排序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏. 源程序 #include <stdio.h> #include<stdlib.h> #define N1 6 /*链表La的长度*/ #define N2 6 /*链表Lb的

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • Java数据结构和算法之冒泡,选择和插入排序算法

    目录 1.冒泡排序 2.选择排序 3.插入排序 4.总结 1.冒泡排序 这个名词的由来很好理解,一般河水中的冒泡,水底刚冒出来的时候是比较小的,随着慢慢向水面浮起会逐渐增大,这物理规律我不作过多解释,大家只需要了解即可. 冒泡算法的运作规律如下: ①.比较相邻的元素.如果第一个比第二个大,就交换他们两个. ②.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数(也就是第一波冒泡完成). ③.针对所有的元素重复以上的步骤,除了最后一个. ④.持续每次对越

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

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

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

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

  • 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) 算法描述: ①. 比较相邻的元素.如果第一个比第二个大,就交

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

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

  • java数据结构与算法之简单选择排序详解

    本文实例讲述了java数据结构与算法之简单选择排序.分享给大家供大家参考,具体如下: 在前面的文章中已经讲述了交换类的排序算法,这节中开始说说选择类的排序算法了,首先来看一下选择排序的算法思想: 选择排序的基本算法思想: 每一趟在 n-i+1 (i=1,2,3,--,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录. 简单选择排序: 设所排序序列的记录个数为n.i取1,2,-,n-1,从所有n-i+1个记录(Ri,Ri+1,-,Rn)中找出排序码最小的记录,与第i个记录交换.执行n-

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

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

  • JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

    排序算法的介绍 排序也称排序算法 (Sort Algorithm),排序是将 一组数据 , 依指定的顺序 进行 排列的过程 . 排序的分类 1)  内部排序 : 指将需要处理的所有数据都加载 到 内部存储器(内存) 中进行排序. 2) 外部排序法: 数据量过大,无法全部加载到内 存中,需要借助 外部存储(文件等) 进行 排序. 常见的排序算法分类 算法的时间复杂度 度量一个程序(算法)执行时间的两种方法 1.事后统计的方法 这种方法可行, 但是有两个问题:一是要想对设计的算法的运行性能进行评测,

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

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

  • Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)

    本文实例汇总了Java各种排序算法.分享给大家供大家参考,具体如下: 1. 冒泡排序: public class SortTest { public static void main(String[] args) { int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345}; show(a); bubbleSort(a); show(a); } private static void bubbleSo

随机推荐