五大排序算法的python实现

本文用Python实现了插入排序、冒泡排序、选择排序、快速排序、归并排序

1、插入排序

时间复杂度为O(n^2)
算法适用于少量数据的排序，稳定的排序方法
插入排序的基本操作思想：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据

1 def insert_sort(nums):
2     for i in range(len(nums)):
3         while i > 0 and nums[i] < nums[i-1]:
4             nums[i], nums[i-1] = nums[i-1], nums[i]
5             i -= 1
6     return nums

2、冒泡排序

时间复杂度为O(n^2)
利用两层循环，第一层循环为数组遍历次数，第二层循环将数组num[len(num)-i]中最大的数字移至数组的尾部

1 def bubble_sort(nums):
2     for i in range(len(nums)-1):
3         for j in range(len(nums)-i-1):
4             if nums[j] > nums[j+1]:
5                 nums[j], nums[j+1] = nums[j+1], nums[j]
6     return nums

3、选择排序

时间复杂度为O(n^2)
第1趟，在待排序记录n1 ~ n[n]中选出最小的记录，将它与n1交换；
第2趟，在待排序记录n2 ~ n[n]中选出最小的记录，将它与n2交换；
以此类推，第i趟在待排序记录n[i] ~ n[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

1 def select_sort(nums):
2     for i in range(len(nums)-1):
3         for j in range(i+1, len(nums)):
4             if nums[i] > nums[j]:
5                 nums[i], nums[j] = nums[j], nums[i]
6     return nums

4、快速排序

时间复杂度为O(n*log(n))
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

 1 def quick_sort(nums, left, right):
 2     if left < right:
 3         p = parttion(nums, left, right)
 4         quick_sort(nums, left, p-1)
 5         quick_sort(nums, p+1, right)
 6     return nums
 7 def parttion(nums, left, right):
 8     key = nums[left]
 9     low = left
10     high = right
11     while low < high:
12         while low < high and nums[high] >= key:
13             high -= 1
14         nums[low] = nums[high]
15         while low < high and nums[low] <= key:
16             low += 1
17         nums[high] = nums[low]
18     nums[low] = key
19     return low

5、归并排序

时间复杂度为O(n*log(n))
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并过程：

比较left[begin1]和right[begin2]的大小，若left[begin1]≤right[begin2]，则将第一个有序表中的元素left[begin1]添加到temp数组中，并令begin1自增1；否则将第二个有序表中的元素right[begin2]添加到temp数组中，并令begin2自增1
如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素添加到temp中

 1 def merge_sort(nums):
 2     middle = len(nums)/2
 3     if len(nums) <= 1:
 4         return nums
 5     _left = merge_sort(nums[:middle])
 6     _right = merge_sort(nums[middle:])
 7     return merge(_left, _right)
 8 def merge(left, right):
 9     temp = []
10     begin1 = begin2 = 0
11     while begin1 < len(left) and begin2 < len(right):
12         if left[begin1] < right[begin2]:
13             temp.append(left[begin1])
14             begin1 += 1
15         else:
16             temp.append(right[begin2])
17             begin2 += 1
18         if begin1 == len(left) and begin2 < len(right):
19             for num in right[begin2:]:
20                 temp.append(num)
21         elif begin2 == len(right) and begin1 < len(left):
22             for num in left[begin1:]:
23                 temp.append(num)
24     return temp