龙空技术网

Python|排序列表(选择排序和插入排序)

小智雅汇 1467

前言:

目前姐妹们对“python二重循环生成10乘10矩阵”大约比较看重,大家都想要知道一些“python二重循环生成10乘10矩阵”的相关知识。那么小编也在网上搜集了一些关于“python二重循环生成10乘10矩阵””的相关知识,希望我们能喜欢,小伙伴们快快来了解一下吧!

在列表list模块中,已有排序操作方法的实现:

lst = [2,9,5,4,8,1,6]

lst.sort()

print(lst) # output:[1, 2, 4, 5, 6, 8, 9]

如果要自定义实现这一方法呢?

排序一个序列,通常会用到双重(嵌套)循环(双重循环在二维列表、矩阵、行列式中使用比较普通)。

使用双重循环处理一个序列的排序,通常内循环搞定一个元素的位置,外循环搞定一个序列的全部。

排序的方法有很多种,效率及代码难易方面各有千秋。

1 选择排序

先用一个简单的实例用手动的方式模拟一下实际的操作过程,然后用代码实现一般化。

如数列lst = [2,9,5,4,8,1,6],选择排序操作(升序)如下:

可以描述为:

for i in range(len(lst)-1):

.....select the smallest element in lst[i : len(lst)]

....swap the smallest with lst[i], if necessary

# lst[i] is in its correct position

# the next iteration applies to lst[i+1 : len(lst)]

代码:

output:

[2, 9, 5, 4, 8, 1, 6]

[1, 9, 5, 4, 8, 2, 6]

[1, 2, 5, 4, 8, 9, 6]

[1, 2, 4, 5, 8, 9, 6]

[1, 2, 4, 5, 8, 9, 6]

[1, 2, 4, 5, 6, 9, 8]

[1, 2, 4, 5, 6, 8, 9]

2 插入排序

如数列lst = [2,9,5,4,8,1,6],插入排序(升序)操作如下:

一般思路描述:

for i in range(1,len(lst)):

....insert lst[i] into a sorted sublist lst[0 : i] so that

lst[0…i+1] is sorted.

代码:

output:

[2, 9, 5, 4, 8, 1, 6]

[2, 9]

[2, 5, 9]

[2, 4, 5, 9]

[2, 4, 5, 8, 9]

[1, 2, 4, 5, 8, 9]

[1, 2, 4, 5, 6, 8, 9]

附代码1

# The function for sorting elements in ascending order

def selectionSort(lst):

....for i in range(len(lst) - 1):

........# Find the minimum in the lst[i : len(lst)]

........currentMin, currentMinIndex = lst[i], i

........for j in range(i + 1, len(lst)):

............if currentMin > lst[j]:

................currentMin, currentMinIndex = lst[j], j

........# Swap lst[i] with lst[currentMinIndex] if necessary

........if currentMinIndex != i:

............lst[currentMinIndex], lst[i] = lst[i], currentMin

........print(lst)

lst = [2,9,5,4,8,1,6]

print(lst)

selectionSort(lst)

附代码2

# The function for sorting elements in ascending order

def insertionSort(lst):

....for i in range(1, len(lst)):

........# insert lst[i] into a sorted sublist lst[0..i-1] so that

........# lst[0..i] is sorted.

........currentElement = lst[i]

........k = i - 1

........while k >= 0 and lst[k] > currentElement:

............lst[k + 1] = lst[k]

............k -= 1

........# Insert the current element into lst[k + 1]

........lst[k + 1] = currentElement

........print(lst)

lst = [2,9,5,4,8,1,6]

print(lst)

insertionSort(lst)

-End-

标签: #python二重循环生成10乘10矩阵