排序算法简介及其C实现

排序算法(Sorting Algorithm)是计算机算法的一个组成部分。排序算法是将一个序列按照大小顺序重新排列。排序是古老但依然富有挑战的问题。Donald Knuth的经典之作《计算机程序设计艺术》(The Art of Computer Programming)的第三卷就专门用于讨论排序和查找。从无序到有序，从统计物理的角度看，就是减小了系统的熵值，增加了系统的有序度。有序这一特征是关于系统的非常有用的先验知识。因此，排序算法可以作为其他快速算法的基础，比如二分法就是基于有序序列的查找算法。直到今天，排序算法依然是计算机科学积极探索的一个方向。

我在这里列出一些最常见的排序方法，并使用C语言实

现。序列表示为一个数组a，数组有n个元素。a[i]为数组中的一个元素，i为元素在数组中的位置(下标)。根据C的规定，数组下标从0开始。假设数组从左向右排列，下标为0的元素位于数组的最左边。

序列将最终排列成从小到大的顺序。下面函数中的参数ac是数组中元素的数目，也就是n。

(C语言的数组名都转成指针，传递给函数，所以需要传递数组中元素的数目ac给函数，详细见"Expert C Programming: Deep C Secrets"一书)

起始数列 （unsorted）

有序数列 (sorted)

下面的链接中，有相关算法的动画图例，强烈推荐同时阅读。

http://www.sorting-algorithms.com/

时间： 2024-02-28 15:34:22

排序算法简介及其C实现的相关文章

[AS功能代码教程10] 数据结构排序算法

一.概论 对于数据的处理工作,排序是其最基本的运算之一.在当今的计算机系统中,花费在排序上的时间占系统CPU运行时间的很大比重.有资料表明,在一些商用计算机上,在排序上的CPU时间达到20%至60%.为了提高计算机的工作效率,人们提出了各种各样的排序方法和算法.这些算法有力地发展.并充分地展示了算法设计的某些重要原则和高超技巧.因此,对于计算专业人员来说掌握排序算法是十分重要的. 二.排序算法简介 本次课程中我们将介绍六种排序方法:插入排序,选择排序,冒泡排序,希尔排序,快速排序及二路归并. <

各种排序算法汇总

目录 简介 交换排序 冒泡排序 快速排序 插入排序 直接插入排序 希尔排序 选择排序 简单选择排序 堆排序 归并排序 基数排序 总结 简介 排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列.分内部排序和外部排序.若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序.反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序.内部排序的过程是一个逐步扩大记录的有序序列长度的过程

各种排序算法汇总（转）

  目录 简介 交换排序 冒泡排序 快速排序 插入排序 直接插入排序 希尔排序 选择排序 简单选择排序 堆排序 归并排序 基数排序 总结 简介 排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列.分内部排序和外部排序.若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序.反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序.内部排序的过程是一个逐步扩大记录的有序序列长度的

排序算法（Java）——那些年面试常见的排序算法

前言 排序就是将一组对象按照某种逻辑顺序重新排列的过程.比如信用卡账单中的交易是按照日期排序的--这种排序很可能使用了某种排序算法.在计算时代早期,大家普遍认为30%的计算周期都用在了排序上,今天这个比例可能降低了,大概是因为现在的排序算法更加高效.现在这个时代数据可以说是无处不在,而整理数据的第一步往往就是进行排序.所有的计算机系统都实现了各种排序算法以供系统和用户使用. 即使你只是使用标准库中的排序函数,学习排序算法仍然有很大的实际意义: - 排序算法往往是我们解决其他问题的第一步 - 排序

十大经典排序算法的JS版

前言 读者自行尝试可以想看源码戳这(https://github.com/damonare/Sorts),博主在github建了个库,读者可以Clone下来本地尝试.此博文配合源码体验更棒哦 这世界上总存在着那么一些看似相似但有完全不同的东西,比如雷锋和雷峰塔,小平和小平头,玛丽和马里奥,Java和javascript-.当年javascript为了抱Java大腿恬不知耻的让自己变成了Java的干儿子,哦,不是应该是跪舔,毕竟都跟了Java的姓了.可如今,javascript来了个咸鱼翻身,几乎

使用Java实现希尔排序算法的简单示例_java

简介希尔排序(缩小增量法) 属于插入类排序,由Shell提出,希尔排序对直接插入排序进行了简单的改进:它通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项排过一趟序之后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去,进行这些排序时的数据项之间的间隔被称为增量,习惯上用字母h来表示这个增量. 常用的h序列由Knuth提出,该序列从1开始,通过如下公式产生: h = 3 * h +1 反过来程序需要反向计算h序列,应该使用 h=(h-

排序算法之PHP版快速排序、冒泡排序_php实例

一.快速排序 1.简介快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要Ο(n log n)次比较.在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见.事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来.快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists).2.步骤从数列中挑出一个元素,称为 "基准&quo

JavaScript中九种常用排序算法_javascript技巧

笔试面试经常涉及各种算法,本文简要介绍常用的一些算法,并用JavaScript实现. 一.插入排序  1)算法简介 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间. 2)算法描述和实现 一般来说,插入排序都

PHP 四种基本排序算法的代码实现(1)

许多人都说算法是程序的核心,算法的好坏决定了程序的质量.作为一个初级phper,虽然很少接触到算法方面的东西.但是对于基本的排序算法还是应该掌握的,它是程序开发的必备工具.这里介绍冒泡排序,插入排序,选择排序,快速排序四种基本算法,分析一下算法的思路. 前提:分别用冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中的值按照从小到大的顺序进行排序. $arr(1,43,54,62,21,66,32,78,36,76,39); 1. 冒泡排序 思路分析:在要排序的一组数中,对当前还未排好的序