收藏本站 收藏本站
积木网首页 - 软件测试 - 常用手册 - 站长工具 - 技术社区
首页 > python > 正文

首页 - PHP - 数据库 - 操作系统 - 游戏开发 - JS - Android - MySql - Redis - MongoDB - Win8 - Shell编程 - DOS命令 - jQuery - CSS样式 - Python - Perl

Access - Oracle - DB2 - SQLServer - MsSql2008 - MsSql2005 - Sqlite - PostgreSQL - node.js - extjs - JavaScript vbs - Powershell - Ruby

Python排序算法实例代码

排序算法,下面算法均是使用Python实现:

插入排序

原理:循环一次就移动一次元素到数组中正确的位置,通常使用在长度较小的数组的情况以及作为其它复杂排序算法的一部分,比如mergesort或quicksort。时间复杂度为 O(n2) 。

# 1nd: 两两交换
def insertion_sort(arr):
 for i in range(1, len(arr)):
  j = i
  while j >= 0 and arr[j-1] > arr[j]:
   arr[j], arr[j-1] = arr[j-1], arr[j]
   j -= 1
 return arr
# 2nd: 交换,最后处理没交换的
def insertion_sort2(arr):
 for i in range(1, len(arr)):
  j = i-1
  key = arr[i]
  while j >= 0 and arr[j] > key:
   arr[j+1] = arr[j]
   j -= 1
  arr[j+1] = key
 return arr
# 3nd: 加速版本,利用已经排好了序的进行二分查找
def insertion_sort3(seq):
 for i in range(1, len(seq)):
  key = seq[i]
  # invariant: ``seq[:i]`` is sorted
  # find the least `low' such that ``seq[low]`` is not less then `key'.
  # Binary search in sorted sequence ``seq[low:up]``:
  low, up = 0, i
  while up > low:
   middle = (low + up) // 2
   if seq[middle] < key:
    low = middle + 1
   else:
    up = middle
  # insert key at position ``low``
  seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]
 return seq
# 4nd: 原理同上,使用bisect
import bisect
def insertion_sort4(seq):
 for i in range(1, len(seq)):
  bisect.insort(seq, seq.pop(i), 0, i) # 默认插在相同元素的左边
 return seq

选择排序

原理:每一趟都选择最小的值和当前下标的值进行交换,适用在大型的数组,时间复杂度为 O(n2)

# 1nd: for
def select_sort(seq):
 for i in range(0, len(seq)):
  mi = i
  for j in range(i, len(seq)):
   if seq[j] < seq[mi]:
    mi = j
  seq[mi], seq[i] = seq[i], seq[mi]
 return seq
# 2nd: min
def select_sort2(seq):
 for i, x in enumerate(seq):
  mi = min(range(i, len(seq)), key=seq.__getitem__)
  seq[i], seq[mi] = seq[mi], x
 return seq

冒泡排序

原理:比较数组中两两相邻的数,如果第一个大于第二个,就进行交换,重复地走访过要排序的数列,达到将最小的值移动到最上面的目的,适用于小型数组,时间复杂度为O(n2)

def bubble_sort(seq):
 for i in range(len(seq)):
  for j in range(len(seq)-1-i):
   if seq[j] > seq[j+1]:
    seq[j], seq[j+1] = seq[j+1], seq[j]
 return seq
def bubble_sort2(seq):
 for i in range(0, len(seq)):
  for j in range(i + 1, len(seq)):
   if seq[i] > seq[j]:
    seq[i], seq[j] = seq[j], seq[i]
 return seq

快速排序

原理:从数组中选择pivot,分成两个数组,一个是比pivot小,一个是比pivot大,最后将这两个数组和pivot进行合并,最好情况下时间复杂度为O(n log n),最差情况下时间复杂度为O(n2)

def quick_sort(seq):
 if len(seq) >= 1:
  pivot_idx = len(seq)//2
  small, large = [], []
  for i, val in enumerate(seq):
   if i != pivot_idx:
    if val <= seq[pivot_idx]:
     small.append(val)
    else:
     large.append(val)
  quick_sort(small)
  quick_sort(large)
  return small + [seq[pivot_idx]] + large
 else:
  return seq

归并排序

原理:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

# 1nd: 将两个有序数组合并到一个数组
def merge(left, right):
 i, j = 0, 0
 result = []
 while i < len(left) and j < len(right):
  if left[i] <= right[j]:
   result.append(left[i])
   i += 1
  else:
   result.append(right[j])
   j += 1
 result += left[i:]
 result += right[j:]
 return result
def merge_sort(lists):
 if len(lists) <= 1:
  return lists
 num = len(lists) / 2
 left = merge_sort(lists[:num])
 right = merge_sort(lists[num:])
 return merge(left, right)
# 2nd: use merge
from heapq import merge
def merge_sort2(m):
 if len(m) <= 1:
  return m
 middle = len(m) // 2
 left = m[:middle]
 right = m[middle:]
 left = merge_sort(left)
 right = merge_sort(right)
 return list(merge(left, right))

堆排序

原理:堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。平均时间复杂度为O(n logn)

# 1nd: normal
def swap(seq, i, j):
 seq[i], seq[j] = seq[j], seq[i]
# 调整堆
def heapify(seq, end, i):
 l = 2 * i + 1
 r = 2 * (i + 1)
 ma = i
 if l < end and seq[i] < seq[l]:
  ma = l
 if r < end and seq[ma] < seq[r]:
  ma = r
 if ma != i:
  swap(seq, i, ma)
  heapify(seq, end, ma)
def heap_sort(seq):
 end = len(seq)
 start = end // 2 - 1
 # 创建堆
 for i in range(start, -1, -1):
  heapify(seq, end, i)
 for i in range(end - 1, 0, -1):
  swap(seq, i, 0)
  heapify(seq, i, 0)
 return seq
# 2nd: use heapq
import heapq
def heap_sort2(seq):
 """ Implementation of heap sort """
 heapq.heapify(seq)
 return [heapq.heappop(seq) for _ in range(len(seq))]


希尔排序

原理:希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

def shell_sort(seq):
 count = len(seq)
 step = 2
 group = count // step
 while group > 0:
 for i in range(0, group):
 j = i + group
 while j < count:
 k = j - group
 key = seq[j]
 while k >= 0:
  if seq[k] > key:
  seq[k + group] = seq[k]
  seq[k] = key
  k -= group
 j += group
 group //= step
 return seq

区别

查看图片

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持积木网。

关于Python中空格字符串处理的技巧总结
前言大家应该都知道字符串处理,是任何语言最常用到的。其中就经常会碰到,对字符串中的空格处理,比如:去除前后空格,去除全部空格,或者以

Python 由字符串函数名得到对应的函数(实例讲解)
把函数作为参数的用法比较直观:deffunc(a,b):returna+bdeftest(f,a,b):printf(a,b)test(func,3,5)但有些情况下,‘要传递哪个函数'这个问题事先还不确定,例如函数

Python 处理数据的实例详解
Python处理数据的实例详解最近用python(3.2的版本)写了根据特定规则,处理数据的一个小程序,用到了一些python常用的基础知识,在此总结一下:1,pyth

本周排行

更新排行

强悍的草根IT技术社区,这里应该有您想要的! 友情链接:b2b电子商务
Copyright © 2010 Gimoo.Net. All Rights Rreserved  京ICP备05050695号