排序算法：
一种能将一串数据依照特定顺序进行排列的一种算法
常见排序算法效率的比较
排序算法的实现
1. 冒泡排序
思想
- 从索引为0的位置开始遍历，只比较相邻两个元素的大小，并且按照升序进行比较，这样遍历完成后，数组中的最大元素放在最后的位置。
- 第二次的遍历范围是(0到n-2)， 因为n-1的位置已经被最大元素占据
- 按照这个方法，每次遍历减少一个元素，两两比较升序排列，直到遍历到所以为1的位置终止
- 最优时间复杂度：O(n) （表示遍历一次发现没有任何可以交换的元素，排序结束。）
最坏时间复杂度：O(n2)
稳定性：稳定
代码
class Sorting(object):
def bubble_sort(self, nums):
n = len(nums)
for j in range(n-1, 0, -1): # 确定遍历的范围
for i in range(j): # 在特定的范围的遍历，比较元素大小
if nums[i] > nums[i+1]:
nums[i], nums[i+1] = nums[i+1], nums[i]
return nums
2. 选择排序
思想
- 找出数组中最小元素，放在数组的起始位置。然后从剩下的数组中再找出最小的数组，依次放在上一次排序好元素之后，直到所有元素排序完毕
- 最优时间复杂度：O(n2)
最坏时间复杂度：O(n2)
稳定性：不稳定（考虑升序每次选择最大的情况）
class Sorting(object):
def select_sort(self, nums):
n = len(nums)
for i in range(n-1):
min_index = i
for j in range(i+1, n):
if nums[min_index]>nums[j]:
min_index = j
if min_index != i:
nums[min_index], nums[i] = nums[i], nums[min_index]
return nums
3. 插入排序
思想
- 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
- 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
最坏时间复杂度：O(n2)
稳定性：稳定
class Sorting(object):
def insert_sort(self, nums):
n = len(nums)
for i in range(1, n):
for j in range(i, 0, -1):
if nums[j] < nums[j-1]:
nums[j], nums[j-1] = nums[j-1], nums[j]
else:
break
return nums
4. 快速排序
思想
- 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
- 最优时间复杂度：O(nlogn)
最坏时间复杂度：O(n2)
稳定性：不稳定
代码
class Sorting(object):
def quick_sort(self, nums, first, last):
if first >= last:
return
low = first
high = last
mid_value = nums[first]
while low < high:
while low < high and nums[high] >= mid_value:
high -=1
nums[high] = nums[low]
while low < high and nums[low] < mid_value:
low += 1
nums[low] = nums[high]
nums[low] = mid_value
self.quick_sort(nums, first, (low-1))
self.quick_sort(nums, (low+1), last)
return nums
5. 归并排序
思想
- 归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
代码
def merge_sort(self, nums):
n = len(nums)
if n <= 1:
return nums
mid = n // 2
left_li = self.merge_sort(nums[:mid])
right_li = self.merge_sort(nums[mid:])
left_point, right_point = 0, 0
result = []
while left_point < len(left_li) and right_point < len(right_li):
if left_li[left_point]<right_li[right_point]:
result.append(left_li[left_point])
left_point += 1
else:
result.append(right_li[right_point])
right_point += 1
result += left_li[left_point:]
result += right_li[right_point:]
return result
6.希尔排序
思想
- 是插入排序的一种
- 将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。
3.最优时间复杂度：根据步长序列的不同而不同
最坏时间复杂度：O(n2)
稳定想：不稳定
def shell_sort(nums):
n = len(nums)
gap= n // 2
while gap > 0:
for i in range(gap, n):
for j in range(i, 0, -gap):
if nums[j] < nums[j-1]:
nums[j], nums[j-1] = nums[j-1], nums[j]
else:
break
gap //= 2
搜索
二分查找
思想：
- 二分查找适用于有序数组
- 可以类比查字典，先找出数组中的中间元素，与target比较，如果等于target, 即找到，返回True; 如果比target大，说明target在mid_element的左边，这时我们要更改查找范围，将其缩小为[0: mid-1]; 如果比target小，说明target在mid_element的右边，缩小查找范围为[mid+1：]，然后重复上述进行循环，直到first>last，退出循环，返回false
- mid = first + (last - first) // 2是为了防止数值溢出
- 优点是比较次数少，查找速度快，平均性能好；
- 缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
- 时间复杂度：O(logn)
空间复杂度：O(1)
代码
非递归法
def binary_search(nums, target):
n = len(nums)
first = 0
last = n-1
while first <= last:
mid = first + (last - first) // 2
if nums[mid] > target:
last = mid-1
elif nums[mid] < target:
first = mid + 1
else:
return True
return False
递归法
def binary_search2(nums, target):
if len(nums) == 0:
return False
mid = len(nums) //2
if nums[mid] == target:
return True
else:
if target < nums[mid]:
return binary_search(nums[:mid], target)
else:
return binary_search(nums[mid+1:],target)