深入C中常用的三种排序方法总结以及探讨分析

排序是程序设计中非常重要的内容，它的功能是将一组无序的的数据，排列成有序的数据序列，经过排列后的数据，要么是从大到小排列，要么是从小到大排列。一般也只有这两种情况。

例如我们统计班级学生的成绩，那么一般是按照学号来进行统计，原来成绩是无序排列的，这样的话非常不适合于我们对成绩的查询，那么一般我们进行成绩查询之前，先进行排序，如按照高分到低分的排序，这样可以很快地查出本班的最高分和最低分，和成绩比较靠前或靠后的学生。
排序有很多种方法，常用的有三种：冒泡排序、选择排序、插入排序等，下面我们就对这三种方法做一下分析和比较，以便大家能够更好的理解和应用。

一、冒泡排序

    1、冒泡排序的基本思想：对于n个数进行排序（现假定是从大到小排序，以下均按此进行），将相邻两个数依次比较，将大数调在前头：也就是说第一个数和第二个数比较，大数放前，小数放后，第二个和第三个进行比较，大数放前、小数放后，然后依次类推。。。经过第一轮比较以后，我们找到一个最小数在最下面（沉底）。然后进行下一轮比较，最后一个数就不用再参加比较了，所以本轮就可以少比较一次。
很显然，需要用双重循环来设计这个问题，外层循环控制进行的轮数，内层循环控制每轮比较的次数，那么到底需要多少轮、每轮需要多少次，我们通过一个实例看一下：

2、排序过程举例：












































外循环

1轮

2轮

3轮

4轮

内循环

5个数比较4次

4个数比较3次

3个数比较2次

2个数比较1次

7

5

8

6

9

1次

2次

3次

4次

1次

2次

3次

1 次

2次

1次

7

5

8

6

9

7

8

5

6

9

7

8

6

5

9

7

8

6

9

5

8

7

6

9

5

8

7

6

9

5

8

7

9

6

5

8

7

9

6

5

8

9

7

6

5

9

8

7

6

5

最小的数5沉底，其余4个数继续比较

次小数6沉底，其余3个数

7沉底，其余2个数比较

最后两个数一次比较



那么通过这个排序过程，我们了解了怎样去进行排序，那么到底谁是气泡呢，我们可以从中找出答案，那么从大到小进行排序，较大的一些数就是气泡。随着排序的进行，气泡逐步上升。

从这个排序过种中，还可以看出，5个数实际经过4轮就可以了，实践证明，n个数最多需要n-1轮排序就可以了。

3、冒泡排序的程序如下：


代码如下:

for(i=0;i<10;i++)
for(j=0;j<10-i;j++)
     if(a[j]<a[j+1])
   {t=a[j];a[j]=a[j+1];a[j+1]=t;}

在此程序段的上面加上输入部分和在程序段加上排序后的输出。
程序的改进：

4、算法的改进：

从上面的排序的过程可以看出，如果一个已经排好序的一组数或者经过很少的轮数就可以排完这些数，但是循环还是要继续进行，这样设计出的程序浪费了大量的时间，所以对一这个算法我们可以重新设计。
 经过修改后的程如下：


代码如下:

for(i=0;i<10&&!swap;i++)
{
swap=1;
for(j=0;j<10-I;j++)
     if(a[j]<a[j+1])
       {t=a[j];a[j]=a[j+1];a[j+1]=t;swap=0;}
}

二、选择排序

1、排序的基本思想：先从第一个数开始起，用第一个数和其它的数进行比较，如果比第一个数大就交换位置，否则不进行交换，这样经过第一轮比较我们就能够找出最大值放在第一位置，然后从第二个位置起再找次大数，这样依次下去，就可以进行整个数的排序，实践证明，n个数最多需要n-1轮排序就可以了。
        2、排序过程举例：











































外循环

1轮

2轮

3轮

4轮

内循环

5个数比较4次

4个数比较3次

3个数比较2次

2个数比较1次

7

5

8

6

9

1次

2次

3次

4次

1次

2次

3次

1 次

2次

1次

7

5

8

6

9

8

5

7

6

9

8

5

7

6

9

9

5

7

6

8

9

7

5

6

8

9

7

5

6

8

9

8

5

6

7

9

8

6

5

7

9

8

7

6

5

9

8

7

6

5

最大的数9找到，其余4个数找次大数

次大数8找到，其余3个数找

7找到，其余2个数找

最后两个数一次比较


选择排序较冒泡容易理解，程序编写也要相对容易一些。


代码如下:

for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
     if(a[i]<a[j])
   {t=a[i];a[i]=a[j];a[j]=t;}

对于选择排序，我们也可以看到一个问题，如第一轮排序中，我们要找的是9才是最大值，所以其它的交换完全没有必要进行，其它各轮都存在这样的情况，所以我们可以想办法取消这种情况，也就是说我们真正找到的最大值的位置后再进行交换。


代码如下:

for(i=0;i<10;i++)
{ p=i;
for(j=i+1;j<10;j++)
     if(a[p]<a[j])
       p=j;
    if(p!=i)
{t=a[i];a[i]=a[j];a[j]=t;}
}

这样算法经过改进以后就较好地解决了这个问题。

三、插入排序

1、插入排序基本思想：（假定从大到小排序）依次从后面拿一个数和前面已经排好序的数进行比较，比较的过程是从已经排好序的数中最后一个数开始比较，如果比这个数，继续往前面比较，直到找到比它大的数，然后就放在它的后面，如果一直没有找到，肯定这个数已经比较到了第一个数，那就放到第一个数的前面。
那么一般情况下，对于采用插入排序法去排序的一组数，可以先选 取第一个数做为已经排好序的一组数。然后把第二个放到正确位置
2、程序的编写如下：


代码如下:

for(i=1;i<10;i++)//i从0开始或者1开始都可以。其它不变。
for(j=i;j>0;j--)
     if(a[j]<a[j-1])
   {t=a[j];a[j]=a[j-1];a[j-1]=t;}

对于这个程序也有需要修该的地方，以上程序的排序实际上也是基于交换思想进行排序，也可以进行真正意义上的排序，即：先把待排序的数取出来，然后找出应该插入的位置，找到后，将待插入位置后的数据统统后移，原待排数据已经取出放于临时变量中。然后把这个数据插入到正确的空余位置就可以了。

那么对于基于交换的插入排序，没有找到位置之前，也进行了交换，所以我们也可以进行程序的改进。那么此程序的改进，肯定不能进行减少交换次数，因为我们知道如果到找到位置再进行交换，那么肯定已经找乱了原来的排序结果，所以只能是找位置，腾位置、放元素这几道手续。


代码如下:

main()
{
int i,j,t,a[]={12,11,2,3,6,67,89,0,1,3};
   for(i=1;i<10;i++)
   {t=a[i];
j=i-1;
while(j>=0&&t>a[i])
     {a[j+1]=a[j];
      j--;
}
    a[j+1]=t;  
 for(i=0;i<10;i++)
   printf("%d ",a[i]);
   printf("/n");
}

以上是对几种排序方法进行了探讨，关于排序问题，是程序设计中的一项非常重要的内容，所以在《数据结构与算法》中作为一项重要的内容做了深入的讲解，我们这在这里只做简单的探讨，以备C语言的初学者或正在学习C语言编程的爱好者使用。

赞 (0)

相关推荐

  • C++ 先对数组排序,在进行折半查找

    第一步:输入15个整数 第二步:对这15个数进行排序 第三部:输入一个数,在后在排好序的数中进行折半查找,判断该数的位置 实现代码如下: 方法一: 选择排序法+循环折半查找法 复制代码 代码如下: #include<iostream>using namespace std;int main(){ int a[15]; int n,i; void array_sort(int a[], int n); int zeban(int a[], int start ,int end,int n); c

  • C++实现基数排序的方法详解

    基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数.基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献.它是这样实现的: 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序.这样从最低位排序一直到最高位排序完成

  • C++ 冒泡排序数据结构、算法及改进算法

    程序代码如下: 复制代码 代码如下: // BubbleSort.cpp : 定义控制台应用程序的入口点.//#include "stdafx.h"#include <cmath>#include <iostream>using namespace std;#define  MAXNUM 20template<typename T>void Swap(T& a, T& b){    int t = a;    a = b;    b

  • C++ 关于STL中sort()对struct排序的方法

    C++ 关于STL中sort()对struct排序的方法

    前言 一直没有系统去看过c++,因为懂得一些c的基本语法,在实际编程中用到c++,只能用到哪些看哪些,发现这样虽然能够完成大部分工作,但是有时候效率实在太低,比如说这节要讲的Std::sort()函数的使用,调了半天才调通.开通c/c++序列博客是记录在使用c++中一些难题,避免以后重犯错,当然以后会尽量挤出时间来较系统学习下c++. 开发环境:QtCreator2.5.1+OpenCV2.4.3 实验基础 首先来看看std中的快速排序算法sort的使用方法: template <class R

  • C++实现数组的排序/插入重新排序/以及逆置操作详解

    C++实现数组的排序/插入重新排序/以及逆置操作详解

    插入新的数字重新排序分析:将新的数字与已经排序好的数组中的数字一一比较,直到找到插入点,然后将插入点以后的数字都向后移动一个单位(a[i+1]=a[i]),然后将数据插入即可. 代码: 复制代码 代码如下: #include<iostream>using namespace std;int main(){ int a[12];//定义用于存储数字的数组  int n;//输入的新的数字  int i=0,j=0,k=0;//排序用到的变量  cout<<"please i

  • C#归并排序的实现方法(递归,非递归,自然归并)

    C#归并排序的实现方法(递归,非递归,自然归并)

    //Main: 复制代码 代码如下: using System;using System.Collections.Generic;using System.Linq;using System.Text; namespace Merge{    class Program    {        static void Main(string[] args)        {            while (true)            {                Console.W

  • C语言使用stdlib.h库函数的二分查找和快速排序的实现代码

    快速排序: 复制代码 代码如下: #include <stdlib.h>#include <stdio.h>#include <string.h> #define LENGTH(x) sizeof(x)/sizeof(x[0]) /**输出数组元素*\param arr:指向数组的指针*\param len:数组元素的个数*/void print(char (*arr)[10],int len){    int i;    for (i=0;i<len;i++) 

  • 利用C++的基本算法实现十个数排序

    冒泡排序法原理:它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成. 冒泡排序算法的运作如下:1.比较相邻的元素.如果第一个比第二个大,就交换他们两个. 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 3.针对所有的元素重复以上的步骤,除了最后一个. 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 示例代码:

  • 用c语言实现冒泡排序,选择排序,快速排序

    代码如下所示: 复制代码 代码如下: /* * 冒泡排序 */void BubbleSort(int arr[], int n){ int temp; for (int i = 0; i < n - 1; i++) {  for (int j = i + 1; j < n; j++)  {   if (arr[i] > arr[j])   {    temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;   }  } }}/* * 选择排

  • 深入C中常用的三种排序方法总结以及探讨分析

    排序是程序设计中非常重要的内容,它的功能是将一组无序的的数据,排列成有序的数据序列,经过排列后的数据,要么是从大到小排列,要么是从小到大排列.一般也只有这两种情况. 例如我们统计班级学生的成绩,那么一般是按照学号来进行统计,原来成绩是无序排列的,这样的话非常不适合于我们对成绩的查询,那么一般我们进行成绩查询之前,先进行排序,如按照高分到低分的排序,这样可以很快地查出本班的最高分和最低分,和成绩比较靠前或靠后的学生.排序有很多种方法,常用的有三种:冒泡排序.选择排序.插入排序等,下面我们就对这三种

  • PHP中数组的三种排序方法分享

    一.冒泡排序法 说明:找到最大的数,排列到最后面,然后继续找 例: 复制代码 代码如下: $arr = array(3,5,-1,0,2); for($i=0;$i<count($arr)-1;$i++){ for($j=0;$j<count($arr)-1-$i;$j++){ if($arr[$j]>$arr[$j+1]){ $temp = $arr[$j]; $arr[$j]=$arr[$j+1]; $arr[$j+1]=$temp; } } } 理解: 3,5,-1,0,2 //从

  • PHP中常用的三种设计模式详解【单例模式、工厂模式、观察者模式】

    本文实例讲述了PHP中常用的三种设计模式.分享给大家供大家参考,具体如下: PHP中常用的三种设计模式:单例模式.工厂模式.观察者模式 1.单例模式 为何要使用PHP单例模式? 多数人都是从单例模式的字面上的意思来理解它的用途, 认为这是对系统资源的节省, 可以避免重复实例化, 是一种"计划生育". 而PHP每次执行完页面都是会从内存中清理掉所有的资源. 因而PHP中的单例实际每次运行都是需要重新实例化的, 这样就失去了单例重复实例化的意义了. 单单从这个方面来说, PHP的单例的确有

  • python中常用的九种预处理方法分享

    python中常用的九种预处理方法分享

    本文总结的是我们大家在python中常见的数据预处理方法,以下通过sklearn的preprocessing模块来介绍; 1. 标准化(Standardization or Mean Removal and Variance Scaling) 变换后各维特征有0均值,单位方差.也叫z-score规范化(零均值规范化).计算方式是将特征值减去均值,除以标准差. sklearn.preprocessing.scale(X) 一般会把train和test集放在一起做标准化,或者在train集上做标准化

  • C语言结构体数组常用的三种赋值方法(包含字符串)

    C语言结构体数组常用的三种赋值方法(包含字符串)

    目录 一.按照成员变量进行赋值(麻烦,好理解,字符串赋值需要strcpy) 二.对数组整体进行赋值.(一次性需要把所有的都添加进去,不需要strcpy) (1) 在声明数组的时候,进行赋值 (2)对有规律的数据赋值,比如学生结构体的学号是有规律的. 三.使用输入进行赋值 总结 一.按照成员变量进行赋值(麻烦,好理解,字符串赋值需要strcpy) 这里使用了一个Init函数,为了在进一步说明传参的使用.实际上赋值按照需要放在主函数就行. (使用strcpy函数需要添加头文件string.h) #i

  • JavaScript中常用的几种字符串方法汇总（新手必看）

    JavaScript中常用的几种字符串方法汇总（新手必看）

    JavaScript常用的几种字符串方法 字符串是一种只读数据,只能查 常用的几种字符串方法: 1.charAt:根据指定的下标获取到对应的字符; 2.charCodeAt:根据指定的下标获取到字符对应的阿斯克码:(底部有ASCII对照表) ps:通过阿斯克码获取到字符: 3.substring:截取字符串: 4.substr:截取字符串: 5.slice:截取字符串: 6.indexOf:查找字符/子字符串在大字符串中第一次出现的位置,找到了返回下标,找不到返回-1: 7.lastIndexO

  • Android中图片圆角三种实现方法

    目录 方法一 方法二 方法三 Android 开发中,经常需要对图片进行二次处理,比如添加圆角效果 或 显示圆形图片: 方法一 通过第三方框架 Glide 设置圆角效果: 写法1: RequestOptions options = new RequestOptions().error(R.drawable.img_load_failure).bitmapTransform(new RoundedCorners(30));//图片圆角为30 Glide.with(this).load(URL) /

  • Java中常用的6种排序算法详细分解

    排序算法很多地方都会用到,近期又重新看了一遍算法,并自己简单地实现了一遍,特此记录下来,为以后复习留点材料. 废话不多说,下面逐一看看经典的排序算法: 1. 选择排序 选择排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i-n-1] 中找出其中的最小值,然后将找到的最小值与 i 指向的值进行交换.因为每一趟确定元素的过程中都会有一个选择最大值的子流程,所以人们形象地称之为选择排序.举个实例来看看: 初始: [38, 17, 16, 16, 7, 31, 39,

  • java中ArrayList的两种排序方法实例

    java中ArrayList的两种排序方法实例

    目录 前言 1.ArrayList使用排序的初衷 2.对一个ArrayList中的数组进行排序. 3.多个ArrayList中的元素进行排序 总结 前言 由于其功能性和灵活性,ArrayList是 Java 集合框架中使用最为普遍的集合类之一.ArrayList 是一种 List 实现,它的内部用一个动态数组来存储元素,因此 ArrayList 能够在添加和移除元素的时候进行动态的扩展和缩减.你可能已经使用过 ArrayList,因此我将略过基础部分.如果你对 ArrayList 还不熟悉,你可

  • C#在foreach遍历删除集合中元素的三种实现方法

    C#在foreach遍历删除集合中元素的三种实现方法

    前言 在foreach中删除元素时,每一次删除都会导致集合的大小和元素索引值发生变化,从而导致在foreach中删除元素时会抛出异常. 集合已修改:可能无法执行枚举操作. 方法一:采用for循环,并且从尾到头遍历 如果从头到尾正序遍历删除的话,有些符合删除条件的元素会成为漏网之鱼: 正序删除举例: List<string> tempList = new List<string>() { "a","b","b","

随机推荐