思想:将数组中的所有元素依次跟前面已经排好的元素相比较,如果选择的元素比已排序的元素小,这两个位置的数值进行交换,直到全部元素都比较过。
- #直接插入排序
- def insert_sort(L):
- #遍历数组中的所有元素,其中0号索引元素默认已排序,因此从1开始
- for x in range(1,len(L)):
- #将该元素与已排序好的前序数组依次比较,如果该元素小,则交换
- #range(x-1,-1,-1):从x-1倒序循环到0
- for i in range(x-1,-1,-1):
- #判断:如果符合条件则交换
- if L[i] > L[i+1]:
- temp = L[i+1]
- L[i+1] = L[i]
- L[i] = temp
(2)希尔排序
思想:将待排序数组按照步长gap进行分组,然后将每组的元素利用直接插入排序的方法进行排序;每次将gap折半减小,循环上述操作;当gap=1时,利用直接插入,完成排序。
- #希尔排序
- def insert_shell(L):
- #初始化gap值,此处利用序列长度的一般为其赋值
- gap = (int)(len(L)/2)
- #第一层循环:依次改变gap值对列表进行分组
- while (gap >= 1):
- #下面:利用直接插入排序的思想对分组数据进行排序
- #range(gap,len(L)):从gap开始
- for x in range(gap,len(L)):
- #range(x-gap,-1,-gap):从x-gap开始与选定元素开始倒序比较,每个比较元素之间间隔gap
- for i in range(x-gap,-1,-gap):
- #如果该组当中两个元素满足交换条件,则进行交换
- if L[i] > L[i+gap]:
- temp = L[i+gap]
- L[i+gap] = L[i]
- L[i] =temp
- #while循环条件折半
- gap = (int)(gap/2)
如代码所示:需要比较的元素的个数是L,第一次排序比较时,步长取L/2。
(3)简单选择排序
思想:比较+交换(和直接插入排序不同,直接插入排序,是将小的元素插在大的元素前面)
- 从待排序序列中,找到关键字最小的元素;
- 如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换;
- 从余下的 N - 1 个元素中,找出关键字最小的元素,重复(1)、(2)步,直到排序结束。
因此我们可以发现,简单选择排序也是通过两层循环实现。
第一层循环:依次遍历序列当中的每一个元素
第二层循环:将遍历得到的当前元素依次与余下的元素进行比较,符合最小元素的条件,则交换。
- 简单选择排序
- def select_sort(L):
- #依次遍历序列中的每一个元素
- for x in range(0,len(L)):
- #将当前位置的元素定义此轮循环当中的最小值
- minimum = L[x]
- #将该元素与剩下的元素依次比较寻找最小元素
- for i in range(x+1,len(L)):
- if L[i] < minimum:
- temp = L[i];
- L[i] = minimum;
- minimum = temp
- #将比较后得到的真正的最小值赋值给当前位置
- L[x] = minimum
(4)堆排序
(5)冒泡排序
思想:将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素
- 将序列当中的左右元素,依次比较,保证右边的元素始终大于左边的元素;
( 第一轮结束后,序列最后一个元素一定是当前序列的最大值;)- 对序列当中剩下的n-1个元素再次执行步骤1。
- 对于长度为n的序列,一共需要执行n-1轮比较
(利用while循环可以减少执行次数)
- #冒泡排序
- def bubble_sort(L):
- length = len(L)
- #序列长度为length,需要执行length-1轮交换
- for x in range(1,length):
- #对于每一轮交换,都将序列当中的左右元素进行比较
- #每轮交换当中,由于序列最后的元素一定是最大的,因此每轮循环到序列未排序的位置即可
- for i in range(0,length-x):
- if L[i] > L[i+1]:
- temp = L[i]
- L[i] = L[i+1]
- L[i+1] = temp
(6)快速排序
(7)归并排序
(8)基数排序
好机会