冒泡

  1. // 每次两两比对，交换，将大的送到右边，所以第i次比对到倒数第i个数即可
  2. def maopao(nums):
  3.     if len(nums) <= 1:
  4.         return nums
  5.     for i in range(len(nums)-1):// 一共需要n-1次遍历，每次找到一个，最后剩下一个最小的
  6.         for j in range(len(nums)-1-i)://每次遍历右侧已经有正确顺序的i+1个大数，且考虑到下面比对含有j+1所以j循环到len(nums)-1-i即可
  7.             if nums[j] > nums[j+1]:
  8.                 swap(nums,j,j+1)

选择排序

  1. //每次找到i右侧剩余里面最小的 跟目前的位置交换
  2. def xuanze(nums):
  3.     if len(nums) <= 1:
  4.         return nums
  5.     for i in range(len(nums)-1)://只需要遍历n-1次，剩下的是最大的
  6.         index = i
  7.         for j in range(i+1,len(nums)):
  8.             if nums[j] < nums[index]://保存最小的数的index
  9.                 index = j
  10.         swap(nums, i, index)

插入排序

  1. //跟打牌摸牌一样，每次将后面一个数依次交换到前面合适的位置
  2. def charu(nums):
  3.     if len(nums) <= 1:
  4.         return nums
  5.     for i in range(1,len(nums)):
  6.         index = i
  7.         for j in range(i):
  8.             if nums[index] < nums[i-1 - j]://直到碰到比自己小的
  9.                 swap(nums, index, i-1-j)
  10.                 index = i-1 - j
  11.             else:
  12.                 break

快排

  1. //为何先动j，是为了无论何时交换都保证移到左边的比K（选取的左端点，且目标从小到大）要小
  2. def kuaipai(nums,L,R):
  3.     if R == L :
  4.         return 0
  5.     i = L
  6.     j = R
  7.     K =nums[L]
  8.     while(i < j):
  9.         while(i < j and nums[j]>=K):
  10.             j -= 1
  11.         while(i < j and nums[i]<=K):
  12.             i += 1
  13.         if i == j :
  14.             nums[L] = nums[i]
  15.             nums[i] = K
  16.             kuaipai(nums, L, i)
  17.             kuaipai(nums, i+1, R)
  18.         else:
  19.             swap(nums, i, j)

并归排序

  1. //取一半数组，假设有序，然后合并数组
  2. def binggui(nums):
  3.     if len(nums) <= 1:
  4.         return nums
  5.     mid = int(len(nums)/2)
  6.     result = []
  7.     nums1 = binggui(nums[:mid])
  8.     nums2 = binggui(nums[mid:])
  9.     i = 0
  10.     j = 0
  11.     while(i < len(nums1) and  j < len(nums2)):
  12.         if nums1[i] <= nums2[j]:
  13.             result.append(nums1[i])
  14.             i+=1
  15.         elif nums1[i] > nums2[j]:
  16.             result.append(nums2[j])
  17.             j+=1
  18.     while(i<len(nums1)):
  19.         result.append(nums1[i])
  20.         i+=1
  21.     while(j<len(nums2)):
  22.         result.append(nums2[j])
  23.         j+=1
  24.     return result