python实现常见八种内排序算法

2019-11-08 01:32:08

字体：大中小

来源：转载

供稿：网友

#!/usr/bin/python# -*- coding: UTF-8 -*-# python 实现八大内排序算法, 利用list对象的方法改变了部分过程input_list = [3, 5, 9, 8, 7, 7, 6, 2, 4, 5]# 直接插入排序def insert_sort(alist): for x in xrange(len(alist)): for y in xrange(x): if alist[x] < alist[y]: # 原本对于有序区大于它的元素需要逐个后移，我使用insert和del方法简化操作 alist.insert(y, alist[x]) del alist[x+1] return alist# 希尔排序 d = n/2 , d2 = d1/2 , 调用前面的直接插入排序算法def shell_sort(alist): # 获取相同间隔内的元素组成列表 def get_group(blist, index_list): return [blist[index] for index in index_list] # 将直接插入的结果映射回原列表 def map_result(blist, result_iter, index_list): for a in index_list: blist[a] = result_iter.next() return blist n = len(alist) gap = n/2 while gap > 0: for x in xrange(gap): result_list = insert_sort(get_group(alist, range(x, n, gap))) alist = map_result(alist, result_list.__iter__(), range(x, n, gap)) gap /= 2 return alist# 冒泡排序def bubble_sort(alist): n = len(alist) for x in xrange(n): for y in range(x + 1, n)[::-1]: if alist[y] < alist[y-1]: alist[y], alist[y-1] = alist[y-1], alist[y] return alist# 快速排序def quick_sort(alist, i, j): start, end = i, j if start < end: base = alist[start] while start != end: while end > start and alist[end] >= base: end -= 1 alist[start] = alist[end] while end > start and alist[start] <= base: start += 1 alist[end] = alist[start] alist[start] = base quick_sort(alist, i, start - 1) quick_sort(alist, start + 1, j) return alist# 选择排序def select_sort(alist): count = 0 n = len(alist) while count < n: index = alist[count:].index(min(alist[count:])) + count alist[count], alist[index] = alist[index], alist[count] count += 1 return alist# 堆排序, 小根堆# 调整堆的算法def sift(alist, low, high): i, j = low, 2 * low root = alist[i] while j <= high: if j < high and alist[j] > alist[j+1]: j += 1 if root > alist[j]: alist[i], i, j = alist[j], j, 2 * j else: break alist[i] = root# 堆排序的算法def heap_sort(alist): n = len(alist) result = [] # 在0的位置插入一个元素，让下标从1开始 alist.insert(0, -1) for x in range(1, n / 2 + 1)[::-1]: sift(alist, x, n) for y in range(2, n + 1)[::-1]: result.append(alist[1]) alist[1], alist[y] = alist[y], alist[1] sift(alist, 1, y - 1) result.append(alist[1]) return result# 归并排序这个算法参考自http://python.jobbole.com/82270/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 resultdef merge_sort(alist): if len(alist) < 2: return alist num = len(alist) / 2 left = merge_sort(alist[:num]) right = merge_sort(alist[num:]) return merge(left, right)# 基数排序，不想写了# merge_sort(input_list[:])# heap_sort(input_list[:])# select_sort(input_list[:])# quick_sort(input_list[:], 0, len(input_list[:])-1)# bubble_sort(input_list[:])# PRint shell_sort(input_list[:])# insert_sort(input_list[:])

网上大部分都有，但有一些地方我按照python特点做了些变化。

其中有一个让我很疑惑的地方，希尔排序的定义是：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序。

我看过很多的博客，甚至包括我本科的数据结构教材，一概都是在算法中先分组，然后两两交换，但按照希尔排序的定义， 难道不是应该先分组，然后使用直接插入排序？，网上和教材中使用的代码普遍是“希尔冒泡法”，我不知道是我理解问题，还是大家的以讹传讹。

我贴出教材中的代码，有兴趣的朋友可以对照我上面的代码，看看有什么不同，

void ShellSort(int R[], int n){ int i,j,gap; int tmp; gap = n / 2; while(gap > 0) { for(i = gap;i < n;i++) { tmp = R[i]; j = j - gap; while(j >= 0 && tmp < R[j]) { R[j + gap] = R[j]; j = j - gap; } R[j + gap] = tmp; } gap = gap / 2; }}

上一篇：运行Python程序的2种方式

下一篇：python读取图像时遇到的奇怪问题