文档章节

常见的排序算法

d
 db_brooke
发布于 2014/08/22 16:51
字数 979
阅读 30
收藏 1

常用的排序算法有以下几类:

    插入排序(直接插入排序,希尔排序),

    选择排序(简单选择排序,堆排序),

    交换排序(冒泡排序,快速排序),

    归并排序,

    基数排序。

排序方法选择得当与否直接影响程序执行的速度和辅助存储空间的占有量,进而影响整个软件的性能。下面对这些算法一一的介绍他们究竟是怎么排的。

        

插入排序:

         直接插入排序:插入到已经排好序的数列中的一个数据。举一个形象的例子:在一个排好队打饭的对列中,张三是后来了,直接插到了队列中李四的后边,因为张三和李四是哥们儿。


         希尔排序:将所有的数据分组,小组内进行排序,之后重新分组,组内数据增多,重新排序(每个步骤都使用直接插入排序)。举一个形象的例子:还是排队打饭,学校有好多班级,不能所有班级都一起打,先按班级(分组)排好队,最后所有的班级再组成一个大组,再一个一个的排着打饭。



选择排序:

         简单选择排序:每次对剩余的数据中选择最小的和剩余的这些数据中的第一个进行交换。举个例子:毕业了,大家都在照毕业照,大家站在那里参差不齐,照相师傅一看,这可不行啊,瞅了一眼一下看到了最高的,好了,你就站到第一个,接着瞅剩下最高的,站第二个……最后就成了一个由高到低的队列


         堆排序:堆分为大顶堆(父节点大于子节点)和小顶堆(父节点小于子节点),根节点是最大的节点(或者最小的节点),每次挑出根节点之后,将剩余的节点进行重新建堆。


交换排序:

         冒泡排序:从后到前(或者从前到后)相邻的两个两两进行比较,不满足要求就位置进行交换,一轮下来选择出一个最小(或最大)的放到了第一个位置上(或最后位置),之后不考虑选出的元素,对剩余的元素进行循环的排列。再举一个例子:我们在火车站买票有军人、记者、两会代表优先的原则,大家排队买票,这时来了一个两会代表买票,他从后往前问买票的人是否是军人、记者、两会代表,如果不是就和普通老百姓交换位置

         快速排序选出一个关键字,比他小的放到他的左边,大的放到右边,设置两个指针,同时与关键字进行比较。举个例子:期末考试到了,考试完了我们要把成绩排序,我们先选60为几个分数,大于等于60分的排到一边,小于60分的排到另一边,之后对小于60分的同学和大于60分的同学进行同样的排序。


归并排序:

归并排序 就是相邻两个元素组成一个组,组内进行排序,之后再将组内元素增加,循环比较


基数排序:

         基数排序 就是先对各位进行比较,进行排序,再对十位进行比较,进行排序……最后对最高位进行比较,进行排序。举个例子:每年在大学里我们都要进行评优,什么样的学生是最优的学生?各方面都要进行比较——成绩、人品、道德等

 

最后我们来总结一下各类排序算法的时间复杂度和空间复杂度,并进行对比:



本文转载自:http://blog.csdn.net/xudepeng0813/article/details/7591883

d
粉丝 0
博文 2
码字总数 534
作品 0
成都
私信 提问
数据结构之常见的排序算法c语言实现

常见的简单排序算法有冒泡排序、选择排序、插入排序、快排、堆排序、归并排序、希尔排序等,这些排序的理论在网上有很多,这就只给出常见的排序算法源码,上学时候写的,不足之处欢迎大家指正...

菏泽小朱
2016/12/11
0
0
常见排序算法实现(直接插入排序,冒泡排序,快速排序,简单选择排序)

常见的排序算法实现(直接插入排序,冒泡排序,快速排序,简单选择排序),还有几个下次写上。 #include "stdio.h" include "stdlib.h" include "malloc.h" include <iostream> using namesp......

种地瓜
2015/10/22
1K
0
排序算法-09-冒泡排序(Bubble Sort)

Basics Sorting - 基础排序算法 算法复习——排序 算法分析 时间复杂度-执行时间(比较和交换次数) 空间复杂度-所消耗的额外内存空间 使用小堆栈或表 使用链表或指针、数组索引来代表数据 排序...

Corwien
2016/06/17
73
0
1. Two Sum - LeetCode

LeetCode Problems Solutions question description: 问题描述 Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assu......

才华惊动党中央
2017/08/17
0
0
算法系列【希尔排序】篇

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 1. 平方阶 (O(n2)) 排序各类简单排序:直接插入...

湖南小影
2017/05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

查看线上日志常用命令

cat 命令(文本输出命令) 通常查找出错误日志 cat error.log | grep 'nick' , 这时候我们要输出当前这个日志的前后几行: 显示file文件里匹配nick那行以及上下5行 cat error.log | grep -C ...

xiaolyuh
36分钟前
5
0
六、Java设计模式之工厂方法

工厂方法定义: 定义一个创建对象的接口,但让实现这个接口的类来决定实例化哪个类,工厂方法让类的实例化推迟到子类中进行 类型:创建型 工厂方法-使用场景: 创建对象需要大量重复的代码 ...

东风破2019
43分钟前
5
0
win服务器管理遇到的一系列问题记录

有些小伙伴在使用iis7远程桌面管理工具的时候总是会遇到一系列的问题,下面就是为大家介绍一下服务器日常管理过程中出现的问题及我的解决办法和心得。希望能帮到大家。   拒绝服务器重新启...

1717197346
50分钟前
6
0
flutter 剪切板 复制粘贴

复制粘贴功能 import 'package:flutter/services.dart'; Clipboard.setData(ClipboardData(text:_text));Clipboard.getData;...

zdglf
52分钟前
4
0
如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题?

面试题 如何保证消息的可靠性传输?或者说,如何处理消息丢失的问题? 面试官心理分析 这个是肯定的,用 MQ 有个基本原则,就是数据不能多一条,也不能少一条,不能多,就是前面说的重复消费...

米兜
53分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部