算法记录

发表于

排序算法

冒泡排序（bubble sort）

优化后时间复杂度是O(n)

1
2
3
4
5
6
7
do
	swapped = false
	for i = 1 to indexOfLastUnsortedElement - 1
		if leftElement > rightEmement
			swap(leftElement,rightElement)
			swapped = true
while swapped

选择排序（selection sort）

1
2
3
4
5
6
repeat (numOfElements -1) times
	set the forst unsorted element as the minimum
	for each of the unsorted elemenys
		if element < currentMinimum
			set element as new minimum
	swap minimum with first unsort position

插入排序（insertion sort）

1
2
3
4
5
6
7
mark first element as sorted
for each unsorted element X
	'extract' the element X
	for j =  lastSortedIndex down to 0
		if current element j > X
			move sorted element to the right by 1
		break loop and insort X here

归并排序（merge sort）

1
2
3
4
5
6
7
split each element into partitions of size 1
recursively merge adjancent partitions
  for i = leftPartStartIndex to rightPartLastIndex inclusive
    if leftPartHeadValue <= rightPartHeadValue
      copy leftPartHeadValue
    else: copy rightPartHeadValue
copy elements back to original array

快速排序（quick sort）

1
2
3
4
5
6
7
for each (unsorted) partition
set first element as pivot
  storeIndex = pivotIndex + 1
  for i = pivotIndex + 1 to rightmostIndex
    if element[i] < element[pivot]
      swap(i, storeIndex); storeIndex++
  swap(pivot, storeIndex - 1)

随机快速排序在数据量大时优于快速排序

计数排序（countion sort）

1
2
3
4
5
6
7
create key (counting) array
for each element in list
  increase the respective counter by 1
for each counter, starting from smallest key
  while counter is non-zero
    restore element to list
    decrease counter by 1

基数排序（radix sort）

1
2
3
4
5
6
7
create 10 buckets (queues) for each digit (0 to 9)
for each digit placing
  for each element in list
    move element into respective bucket
  for each bucket, starting from smallest digit
    while bucket is non-empty
      restore element to list