排序算法

冒泡排序（bubble sort）

優(yōu)化后時間復(fù)雜度是O(n)

do
    swapped = false
    for i = 1 to indexOfLastUnsortedElement - 1
        if leftElement > rightEmement
            swap(leftElement,rightElement)
            swapped = true
while swapped

選擇排序（selection sort）

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）

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）

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）

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)

隨機快速排序在數(shù)據(jù)量大時優(yōu)于快速排序

計數(shù)排序（countion sort）

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

基數(shù)排序（radix sort）

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