冒泡排序,插入排序

冒泡排序

每两个相邻的元素进行比较,前者大于后者则交换元素位置,直到所有的相邻元素均无法交换位置步骤

步骤

  1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3.针对所有的元素重复以上的步骤,除了最后一个。
  4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

python代码:

lst = [43,56,53,33,1,23]
def mpsort(ln):
    lenth = len(ln)
    while lenth:
        for i in range(lenth - 1):
            if ln[i] > ln[i + 1]:
                ln[i], ln[i + 1] = ln[i + 1], ln[i]
        lenth -= 1
    return ln
print mpsort(lst)

冒泡排序是稳定的排序,时间复杂度最好的为O(n) 最差的情况为O(n^2)

直接插入排序

介绍:

插入排序的工作原理是,对于每个未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

步骤:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果被扫描的元素(已排序)大于新元素,将该元素后移一位
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

排序演示:

 python代码:

lst = [1, 2, 4, 3, 1, 10]
def insert_sort(ary):
    n = len(ary)
    for i in range(1,n):
        if ary[i] < ary[i-1]:
            temp = ary[i]
            index = i           #待插入的下标
            for j in range(i-1,-1,-1):  #从i-1 循环到 0 (包括0)
                if ary[j] > temp :
                    ary[j+1] = ary[j]
                    index = j   #记录待插入下标
                else :
                    break
            ary[index] = temp
    return ary

print insert_sort(lst)

原文地址:https://www.cnblogs.com/bianjing/p/10376450.html

时间: 02-14

冒泡排序,插入排序的相关文章

简单排序

冒泡排序 选择排序 插入排序 时间复杂度 O(n^2) 冒泡排序è基本不用  过于简单比较次数(见下) 与 交换次数(平均为比较次数的一半) 均正比于N^2 选择排序è快于冒泡 交换时间级别大于比较时间级别选择该排序 比较次数(见下) 正比于N^2 交换次数N 插入排序 VS表插入排序 效率比较 插入排序>(略快于)选择排序>冒泡排序 插入排序 表插入排序 原理 简单排序之一 利用有序链表插入效率的比较为O(N)的特点 比较次数MAX (N^2-N)/2 N 比较次数AVG (N^2-N)/4

数据排序(二)

归并排序 归并排序(MERGE SORT)是又一类不同的排序方法,归并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列,因此它又叫归并算法. 例如,有两个有序表,(7,10,13,15)和(4,8,19,20),归并后得到的有序表为(4,7,8,10,13,15,19,20) . 归并过程:比较a[i]和b[j]的大小,若a[i]<=b[j],则将第一个有序序列中的元素a[i]复制到r[k]中,并令i和k分别加1,分别指向后一个单元,否则将第二个有序序列的元素b[j]复制到r[

白话排序算法--快速排序

前言: 写到快速排序时,之前已经进行了冒泡.选择.插入排序,发现算法问题很多东西都是和实际问题相逆的,实际你可能会由外及里,由上及下,可是算法里面它有时就需要你由里往外去扩散,好比最里面的是小成果,然后一次次往外变化,成果也慢慢变大,最后直至达到最终成果为止.本篇快速排序方法因为调用了递归,你就可以逆着由里及外来思考问题. 写这篇文章光画图就花费了我2小时时间,越抽象就越不好形容和比喻,画的不好,希望各位不要吐槽. 快速排序:先快速排序将队列一分为二,然后对每个队列进行递归调用快速排序方法,直至

09-排序1 排序

给定N个(长整型范围内的)整数,要求输出从小到大排序后的结果. 本题旨在测试各种不同的排序算法在各种数据情况下的表现.各组测试数据特点如下: 数据1:只有1个元素: 数据2:11个不相同的整数,测试基本正确性: 数据3:103个随机整数: 数据4:104个随机整数: 数据5:105个随机整数: 数据6:105个顺序整数: 数据7:105个逆序整数: 数据8:105个基本有序的整数: 数据9:105个随机正整数,每个数字不超过1000. 输入格式: 输入第一行给出正整数N(≤10?^5??),随后

排序常用算法总结

排序算法:一种能将一串数据依照特定的排序方式进行排列的一种算法. 排序算法性能:取决于时间和空间复杂度,其次还得考虑稳定性,及其适应的场景. 稳定性:让原本有相等键值的记录维持相对次序.也就是若一个排序算法是稳定的,当有俩个相等键值的记录R和S,且原本的序列中R在S前,那么排序后的列表中R应该也在S之前. 以下来总结常用的排序算法,加深对排序的理解. 排序算法目录 冒泡排序 插入排序 希尔排序 选择排序 快速排序 归并排序 堆排序 计数排序 桶排序 基数排序 总结 冒泡排序 原理 俩俩比较相邻记

算法 排序lowB三人组 冒泡排序 选择排序 插入排序

参考博客:基于python的七种经典排序算法   [经典排序算法][集锦]     经典排序算法及python实现 首先明确,算法的实质 是 列表排序.具体就是操作的列表,将无序列表变成有序列表! 一.排序的基本概念和分类 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作.排序算法,就是如何使得记录按照要求排列的方法. 排序的稳定性: 经过某种排序后,如果两个记录序号同等,且两者在原无序记录中的先后秩序依然保持不变,则称所使用的排序方法是稳定的,反之是不稳定

基本排序算法(冒泡排序 选择排序 插入排序 快速排序 归并排序 基数排序 希尔排序)

冒泡排序 public static void bubbleSort(int[] arr){ int lgn = arr.length; for (int i = 0; i < lgn - 1; i++) { for (int j = 0; j < lgn - 1 - i; j++) { if(arr[j] > arr[j + 1]){ int temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; } } } } 选择排序 publ

Python排序-冒泡排序、选择排序、插入排序

''' 冒泡排序 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成. 这个算法的名字由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端 ''' data_set = [12,45,2,48,66,2,1,56,36,90,5,10,503] for i in range(len(data_set)): ##控制相邻比较的轮数 for j in range(len(data_set

python开发之路Day17-算法设计(冒泡排序、选择排序、插入排序、二叉树)

s12-20160514-day17 *:first-child { margin-top: 0 !important; } body>*:last-child { margin-bottom: 0 !important; } /* BLOCKS =============================================================================*/ p, blockquote, ul, ol, dl, table, pre { margin

Java学习 (七)、数组,查找算法,二分查找法,冒泡排序,选择排序,插入排序

一.常用数组查找算法 工作原理:它又称为顺序查找,在一列给定的值中进行搜索,从一端的开始逐一检查每个元素,知道找到所需元素的过程. 例1:查找指定的数在数组中出现的位置,找到返回下标,找不到返回-1 1 import java.util.Scanner; 2 public class LinearSearch{ 3 public static void main(String []argas) 4 { 5 int [] array={10,100,90,65,80,92}; 6 System.o