文档章节

排序算法-09-冒泡排序(Bubble Sort)

Corwien
 Corwien
发布于 2016/06/17 15:02
字数 570
阅读 70
收藏 1

##Basics Sorting - 基础排序算法 算法复习——排序

###算法分析

  1. 时间复杂度-执行时间(比较和交换次数)
  2. 空间复杂度-所消耗的额外内存空间
  • 使用小堆栈或表
  • 使用链表或指针、数组索引来代表数据
  • 排序数据的副本

对具有重键的数据(同一组数按不同键多次排序)进行排序时,需要考虑排序方法的稳定性,在非稳定性排序算法中需要稳定性时可考虑加入小索引。

稳定性:如果排序后文件中拥有相同键的项的相对位置不变,这种排序方式是稳定的。

常见的排序算法根据是否需要比较可以分为如下几类:

  • Comparison Sorting
    1.Bubble Sort
    2.Selection Sort
    3.Insertion Sort
    4.Shell Sort
    5.Merge Sort
    6.Quck Sort
    7.Heap Sort
  • Bucket Sort
  • Counting Sort
  • Radix Sort

从稳定性角度考虑可分为如下两类: -稳定 -非稳定

有关排序法的文章

##Bubble Sort - 冒泡排序 核心:冒泡,持续比较相邻元素,大的挪到后面,因此大的会逐步往后挪,故称之为冒泡。

此处输入图片的描述

示例
python 冒泡:

#!/usr/bin/env python

def bubbleSort(alist):
    for i in xrange(len(alist)):
        print(alist)
        for j in xrange(1, len(alist) - i):
            if alist[j - 1] > alist[j]:
                alist[j - 1], alist[j] = alist[j], alist[j - 1]

    return alist

unsorted_list = [6, 5, 3, 1, 8, 7, 2, 4]
print(bubbleSort(unsorted_list))

php冒泡:


<?php

// 冒泡排序法
function bubbleSort($alist)
{
   for ($i = 0; $i< count($alist); $i ++)
{
    for($j = 1; $j < count($alist) - $i; $j++)
  {
     if($alist[$j-1] > $alist[$j])
   {
       $tmp = $alist[$j - 1];
       $alist[$j -1] = $alist[$j] ;
       $alist[$j] = $tmp;
   }

  }

}

return $alist;

}

 $unsorted_list = array(6, 5, 3, 1, 8, 7, 2, 4);
 print_r(bubbleSort($unsorted_list));

复杂度分析

平均情况与最坏情况均为 $$O(n^2)$$, 使用了 temp 作为临时交换变量,空间复杂度为 $$O(1)$$.

© 著作权归作者所有

Corwien
粉丝 27
博文 149
码字总数 115164
作品 0
广州
程序员
私信 提问
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光
2012/03/09
2.3K
1
常用的排序算法(一)

Date: 2016-02-14 排序算法的学习 冒泡排序 时间复杂度:当顺序为正序的时候,为最好状态时间复杂度为O(N),平均时间复杂的为O(N^2) 因为没有创建新的存储结构所以空间复杂度为O(1) 冒泡排序是...

eatnothing
2016/02/14
183
0
python冒泡排序

冒泡排序是最基本的排序算法,原理即元素两两比较。 一次将最大或者最小放到一端,那么实现过程是这样的 def bubble_sort(ls): ls_len = len(ls) for i in range(ls_len-1): for j in range...

农村程序员
2016/05/16
43
0
Java冒泡排序

一、冒泡排序 冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需...

晚天吹凉风
2017/03/01
11
0
Python算法(一) 数组冒泡排序(难度等级:easy)

冒泡排序(Bubble Sort)是一种典型的交换排序算法,通过交换数据元素的位置进行排序。 算法原理:从无序序列头部开始,进行两两比较,根据大小交换位置,直到最后将最大(小)的数据元素交换...

高杆python
2017/09/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

抽象同步队列AQS——AbstractQueuedSynchronizer锁详解

AQS——锁的底层支持 谈到并发,不得不谈ReentrantLock;而谈到ReentrantLock,不得不谈AbstractQueuedSynchronizer(AQS)! 类如其名,抽象的队列式的同步器,AQS定义了一套多线程访问共享资...

须臾之余
今天
3
0
springboot配置百度UEditor 富文本详解

富文本简介 UEditor是由百度web前端研发部开发所见即所得富文本web编辑器,具有轻量,可定制,注重用户体验等特点,开源基于MIT协议,允许自由使用和修改代码... 准备工作 ueditor需要单独文...

wotrd
昨天
4
0
mysql 5.7之my.cnf配置大全

[client]port = 3306socket = /tmp/mysql.sock[mysqld]###############################基础设置######################################Mysql服务的唯一编号 每个mysql服务...

Online_Reus
昨天
3
0
MAVEN打包时引入外部链接的包

1.项目引入了ORACLE的jar包,MAVEN配置如下 2.打jar包的时候需要指定下main入口函数mainClass <dependency> <groupId>com.oracle</groupId> <artifactId>ojdbc6</artifactId> ......

Cobbage
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部