常見排序演示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:數(shù)組的首位進(jìn)行比較，小的放進(jìn)去馋贤，依次進(jìn)去
一般遇到Merge這種合并的方式，都會(huì)涉及到3的歸并排序，兩兩比較然后放到數(shù)組或者新開的buffer里面躲惰。比完之后周霉，總有一個(gè)數(shù)組或者一個(gè)區(qū)間沒有出完翰苫，那就繼續(xù)
Notice：在快排和歸并排序里面，都有l(wèi)eft, right温技，其中對(duì)于快排，left = start, right = end,從兩邊開始往里走扭粱。對(duì)于歸并排序而言舵鳞，left = start, right = mid + 1。分別從區(qū)間的頭部開始琢蛤。而且對(duì)于不同數(shù)組而言蜓堕，使用"<" ，對(duì)于不同區(qū)間而言博其，使用"<="
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:這道題非常好的聯(lián)系歸并排序和快排的題目套才，下面分別用這兩種方法解題
@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是指
#區(qū)間永遠(yuǎn)都是<=
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)
