这些排序都是比较经典的排序算法:
- 冒泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 计数排序
- 桶排序
- 基数排序
那么如何使用python来实现这些排序呢?
冒泡排序
-
比较相邻的元素。如果第一个比第二个大,就交换它们两个;
-
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
-
针对所有的元素重复以上的步骤,除了最后一个。
重复以上步骤,直到排序完成。
def Bubble_Sort(array):
length = len(array)
for i in range(length):
for j in range(length-i-1):
if array[j] > array[j+1]: array[j+1], array[j] = array[j], array[j+1]
return array
选择排序
-
在未排序序列中找到最小元素,存放到排序序列的起始位置;
-
再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾。
重复以上步骤,直到排序完成。
def Select_Sort(array):
length = len(array)
for i in range(length-1):
idx_min = i
for j in range(i+1, length):
if array[j] < array[idx_min]:
idx_min = j
array[i], array[idx_min] = array[idx_min], array[i]
return array
插入排序
-
从第一个元素开始,该元素认为已经被排序;
-
取出下一个元素,在已经排序的元素序列中从后向前扫描;
-
如果该元素(已排序)大于新元素,将该元素移到下一位置;
-
重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
-
将新元素插入到该位置后。
重复步骤2~5,直到排序完成。
def Insert_Sort(array):
length = len(array)
for i in range(1, length):
pointer, cur = i - 1, array[i]
while pointer >= 0 and array[pointer] > cur:
array[pointer+1] = array[pointer]
pointer -= 1
array[pointer+1] = cur
return array
归并排序
-
把长度为n的输入序列分成两个长度为n/2的子序列;
-
对这两个子序列分别采用归并排序;
-
将两个排序好的子序列合并成一个最终的排序序列。
def Merge(array_1, array_2):
result = []
while array_1 and array_2:
if array_1[0] < array_2[0]:
result.append(array_1.pop(0))
else:
result.append(array_2.pop(0))
if array_1:
result += array_1
if array_2:
result += array_2
return result
def Merge_Sort(array):
if len(array) < 2: return array
pointer = len(array) // 2
left = array[:pointer]
right = array[pointer:]
return Merge(Merge_Sort(left), Merge_Sort(right))
快速排序
-
从数列中挑出一个元素,作为一个基准(pivot);
-
重新排序数列,将所有比基准值小的摆放在基准前面,所有比基准值大的摆在基准的后面(相等的可以分到任一边),于是该基准就处于数列的中间位置。
-
递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
def Quick_Sort(array, left, right):
if left >= right:
return array
pivot, i, j = array[left], left, right
while i < j:
while i < j and array[j] >= pivot:
j -= 1
array[i] = array[j]
while i < j and array[i] <= pivot:
i += 1
array[j] = array[i]
array[j] = pivot
Quick_Sort(array, left, i-1)
Quick_Sort(array, i+1, right)
return array
计数排序
-
找出待排序的数组中最大和最小的元素;
-
统计数组中值为i的元素出现的次数,存入数组C的第i项;
-
对所有的计数累加(从C中的第一个元素开始,每一项值和前一项相加);
-
反向填充目标数组——将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
def Count_Sort(array):
length = len(array)
max_value = max(array)
count = [0 for _ in range(max_value+1)]
output = [0 for _ in range(length)]
for i in range(length):
count[array[i]] += 1
for i in range(1, len(count)):
count[i] += count[i-1]
for i in range(length):
output[count[array[i]]-1] = array[i]
count[array[i]] -= 1
return output
桶排序
-
设置一个大小定量的数组A当作空桶;
-
遍历一组数据,并且把数据一个一个放到对应的桶里去(数i放入A(i));
-
遍历桶数组,对每个不是空的桶进行排序;
-
从不是空的桶里把排好序的数据拼接起来。
def Bucket_Sort(array):
max_value, min_value, length = max(array), min(array), len(array)
buckets = [0 for _ in range(min_value, max_value+1)]
for i in range(length):
buckets[array[i]-min_value] += 1
output = []
for i in range(len(buckets)):
if buckets[i] != 0:
output += [i+min_value] * buckets[i]
return output
基数排序
-
取得数组中的最大数,并取得其位数;
-
假设arr为原始数组,从最低位开始取每个位组成radix数组;
-
对radix进行计数排序。
def Radix_Sort(array):
max_value = max(array)
num_digits = len(str(max_value))
for i in range(num_digits):
buckets = [[] for k in range(10)]
for j in array:
buckets[int(j / (10 ** i)) % 10].append(j)
output = [m for bucket in buckets for m in bucket]
return output