常见排序演示http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
1.Bubble sort
solution:两两交换
class Solution:
def bubble_sort(self, A):
len_a = len(A)
if len_a < 2:
return
for i in range(len_a):
for j in range(len_a - 1 -i):
if A[j] > A[j + 1]:
A[j], A[j + 1] = A[j + 1], A[j]
2.Quick Sort
solution:从上到下分治
class Solution:
def quick_sort(self, A, start, end):
if stat >= end:
return
left, right = start, end
#pivot is value not index
pivot = A[(start + end) / 2]
#every time you compare left & right, it should be left <= right
while left <= right:
while left <= right and A[left] < pivot:
left += 1
while left <= right and A[right] > pivot:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
self.quick_sort(self, A, start, right)
self.quick_sort(self, A, left, end)
3.Merge Sort
solution:从下到上分治
class Solution:
# @param {int[]} A an integer array
# @return nothing
def merge_sort(self, start, end, A, temp):
if start >= end:
return
mid = (start + end) / 2
self.merge_sort(start, mid , A, temp)
self.merge_sort(mid + 1, end, A, temp)
self.merge(start, mid, end, A, temp)
def merge(self, start, mid, end, A, temp):
left, right = start, mid + 1
index = start
while left <= mid and right <= end:
if A[left] < A[right]:
temp[index] = A[left]
left += 1
else:
temp[index] = A[right];
right += 1
index += 1
while left <= mid:
temp[index] = A[left]
left += 1
index += 1
while right <= end:
temp[index] = A[right]
right += 1
index += 1
for index in range(start, end + 1):
A[index] = temp[index]
4.[Merge Two Sorted Arrays]https://leetcode.com/problems/merge-sorted-array/description/
solution:数组的首位进行比较,小的放进去,依次进去
一般遇到Merge这种合并的方式,都会涉及到3的归并排序,两两比较然后放到数组或者新开的buffer里面。比完之后,总有一个数组或者一个区间没有出完,那就继续
Notice:在快排和归并排序里面,都有left, right,其中对于快排,left = start, right = end,从两边开始往里走。对于归并排序而言,left = start, right = mid + 1。分别从区间的头部开始。而且对于不同数组而言,使用"<" ,对于不同区间而言,使用"<="
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
result = []
left, right = 0, 0
while left < m and right < n:
if nums1[left] < nums2[right]:
result.append(nums1[left])
left += 1
else:
result.append(nums2[right])
right += 1
while left < m:
result.append(nums1[left])
left += 1
while right < n:
result.append(nums2[right])
right += 1
for i in range(m + n):
nums1[i] = result[i]
5.[Sort Integers II] http://www.lintcode.com/en/problem/sort-integers-ii/#
solution:这道题非常好的联系归并排序和快排的题目,下面分别用这两种方法解题
@mergeSort
class Solution:
"""
@param A: an integer array
@return: nothing
"""
def sortIntegers2(self, A):
# write your code here
len_a = len(A)
temp = [0 for _ in range(len_a)]
self.mergeSort(A, 0, len_a - 1, temp)
def mergeSort(self, A, start, end, temp):
if start >= end:
return
mid = (start + end) / 2
self.mergeSort(A, start, mid, temp)
self.mergeSort(A, mid + 1, end, temp)
self.merge(A, start, end ,temp)
def merge(self, A, start, end, temp):
mid = (start + end) / 2
left, right = start, mid + 1
index = start
while left <= mid and right <= end:
if A[left] < A[right]:
temp[index] = A[left]
left += 1
index += 1
else:
temp[index] = A[right]
right += 1
index += 1
while left <= mid:
temp[index] = A[left]
left += 1
index += 1
while right <= end:
temp[index] = A[right]
right += 1
index += 1
for index in range(start, end + 1):
A[index] = temp[index]
@quickSort
class Solution:
"""
@param A: an integer array
@return: nothing
"""
def sortIntegers2(self, A):
# write your code here
self.quickSort(A, 0, len(A) - 1)
def quickSort(self, A, start, end):
if start >= end:
return
left, right = start, end
pivot = A[(start + end) / 2]
#这里pivot是指
#区间永远都是<=
while left <= right:
while left <= right and A[left] < pivot:
left += 1
while left <= right and A[right] > pivot:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
self.quickSort(A, start, right)
self.quickSort(A, left, end)