Quick sort
  • java
public class QuickSort {
    public static int partition(int[] alist, int first, int last) {
        int pirot = alist[first];

        int left_mark = first + 1;
        int right_mark = last;

        boolean done = false;

        while(!done) {
            while (left_mark <= right_mark && alist[left_mark] <= pirot) {
                left_mark ++;
            }
            while (right_mark >= left_mark && alist[right_mark] >= pirot) {
                right_mark --;
            }

            if (left_mark > right_mark) {
                done = true;
            } else {
                int temp = alist[right_mark];
                alist[right_mark] = alist[left_mark];
                alist[left_mark] = temp;
            }
        }

        alist[first] = alist[right_mark];
        alist[right_mark] = pirot;
        return right_mark;
    }

    public static void quick_sort_helper(int[] alist, int first, int last) {
        if (first >= last) {
            return;
        }

        int pirot_point = partition(alist, first, last);

        quick_sort_helper(alist, first, pirot_point -1);
        quick_sort_helper(alist, pirot_point + 1, last);
    }

    public static void quick_sort(int[] alist) {
        quick_sort_helper(alist, 0, alist.length - 1);
    }

    public static void main(String args[]) {
        int[] alist = {5, 1, 2, 7, 5, 8, 1, 9};
        quick_sort(alist);
        for (int i = 0; i < alist.length; i ++) {
            System.out.println(alist[i]);
        }
    }
}
  • python
# -*- coding:utf-8 -*-

def quick_sort(alist):
    quick_sort_helper(alist, 0, len(alist) - 1)

def quick_sort_helper(alist, first, last):

    if first < last:

        pirot_point = partition(alist, first, last)

        quick_sort_helper(alist, first, pirot_point - 1)
        quick_sort_helper(alist, pirot_point + 1, last)

def partition(alist, first, last):
    pirot = alist[first]

    left_mark = first + 1
    right_mark = last

    done = False

    while not done:
        while left_mark <= right_mark and alist[left_mark] <= pirot :
            left_mark += 1
        while right_mark >= left_mark and alist[right_mark] >= pirot :
            right_mark -= 1

        if left_mark > right_mark:
            done = True
        else:
            temp = alist[left_mark]
            alist[left_mark] = alist[right_mark]
            alist[right_mark] = temp

    alist[first] = alist[right_mark]
    alist[right_mark] = pirot

    return right_mark
    

if __name__ == "__main__":
    alist = [5, 1, 6, 2, 8, 9 ,3, 10]
    quick_sort(alist)
    print(alist)
  • ruby
def quick_sort(alist)
  quick_sort_helper(alist, 0, alist.length - 1)
end

def quick_sort_helper(alist, first, last)
  if first < last
    pirot_point = partition(alist, first, last)

    quick_sort_helper(alist, first, pirot_point - 1)
    quick_sort_helper(alist, pirot_point + 1, last)
  end
end

def partition(alist, first, last)
  pirot = alist[first]

  left_mark = first + 1
  right_mark = last

  done = false
  while not done
    while left_mark <= right_mark && alist[left_mark] <= pirot
      left_mark += 1
    end

    while right_mark >= left_mark && alist[right_mark] >= pirot
      right_mark -= 1
    end

    if (left_mark > right_mark)
      done = true
    else
      temp = alist[right_mark]
      alist[right_mark] = alist[left_mark]
      alist[left_mark] = temp
    end
  end

  alist[first] = alist[right_mark]
  alist[right_mark] = pirot
  return right_mark
end

alist = [5,1,6,7,2,3,9]
quick_sort(alist)
print alist
Heap sort
Heap
  • A heap can be classified further as either a "max heap" or a "min heap". In a max heap, the keys of parent nodes are always greater than or equal to those of the children and the highest key is in the root node.
  • 堆是一个完全二叉树(所有节点尽可能的在上边和左边),然后对于最大堆来说父节点总是大于子节点,同理于最小堆
  • priority queue , Dijkstra's algorithm (堆的应用)
  • Worst-case performance O(n\log n), Best-case performance O(n\log n)[1], Average performance O(n\log n)
  • python 实现
# -*- coding:utf-8 -*-

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def max_heapify(alist, i, heap_size):
    l = left(i)
    r = right(i)

    if l < heap_size and alist[l] > alist[i]:
        largest = l
    else:
        largest = i

    if r < heap_size and alist[r] > alist[largest]:
        largest = r

    if largest != i:
        temp = alist[i]
        alist[i] = alist[largest]
        alist[largest] = temp

        max_heapify(alist, largest, heap_size)

def build_max_heap(alist):
    heap_size = len(alist)
    for i in range(heap_size / 2 - 1, -1, -1):
        max_heapify(alist, i, heap_size)

def heap_sort(alist):
    build_max_heap(alist)
    
    heap_size = len(alist)
    for i in range(heap_size -1, 0, -1):
        heap_size -= 1

        max_heapify(alist, 0, heap_size)

        temp = alist[0]
        alist[0] =  alist[i]
        alist[i] = temp

def main():
    alist = [1, 5, 7, 3, 9 ,2, 34, 12, 12, 10]
    heap_sort(alist)
    print(alist)

if __name__ == "__main__":
    main()
  • ruby 实现
def left(i)
     return 2 * i + 1
end

def right(i)
     return 2 * i + 2
end

def max_heapify(alist, i, heap_size)
  l = left(i)
  r = right(i)

  if (l < heap_size && alist[l] > alist[i])
    largest = l
  else
    largest = i
  end 

  if (r < heap_size && alist[r] > alist[largest])
    largest = r
  end

  if (i != largest)
    temp = alist[i]
    alist[i] = alist[largest]
    alist[largest] = temp

    max_heapify(alist, largest, heap_size)
  end
end

def build_max_heap(alist)
  heap_size = alist.length

  (heap_size / 2 - 1).downto(0) do |i| 
    max_heapify(alist, i, heap_size)
  end

end

def heap_sort(alist)
  build_max_heap(alist)

  heap_size = alist.length
  while heap_size > 0
    heap_size -= 1

    temp = alist[0]
    alist[0] = alist[heap_size]
    alist[heap_size] = temp

    max_heapify(alist, 0, heap_size)
  end
end

alist = [1, 5, 3, 10, 35, 1, 4, 56]
heap_sort(alist)
print(alist)
  • java实现
import java.util.Arrays;

public class HeapSort {
    public static int left(int i) {
        return 2 * i + 1;
    }

    public static int right(int i) {
        return 2 * i + 2;
    }

    public static void maxHeapify(int[] alist, int i, int heapSize) {
        int l = left(i);
        int r = right(i);

        int largest = i;
        if (l < heapSize && alist[l] > alist[i]) {
            largest = l;
        }
        if (r < heapSize && alist[r] > alist[largest]) {
            largest = r;
        }

        if (largest != i) {
            int temp = alist[i];
            alist[i] = alist[largest];
            alist[largest] = temp;

            maxHeapify(alist, largest, heapSize);
        }
    }

    public static void buildMaxHeap(int[] alist) {
        int heapSize = alist.length;
        for (int i = heapSize / 2 -1; i >= 0; i--) {
            maxHeapify(alist, i, heapSize);
        }
    }

    public static void sort(int[] alist) {
        int heapSize = alist.length;

        buildMaxHeap(alist);

        while (heapSize > 0) {
            heapSize --;

            int temp = alist[0];
            alist[0] = alist[heapSize];
            alist[heapSize] = temp;

            maxHeapify(alist, 0, heapSize);
        }
    }

    public static void main(String[] args) {
        int[] alist = {1, 2, 5, 89, 2, 22, 34, 11, 6};
        sort(alist);
        System.out.println(Arrays.toString(alist));
    }
}
Merge sort
def merge_sort(alist):
    templist = []
    copy_array(alist, templist)
    length = len(alist)
    split_merge(alist, 0, length - 1, templist)

def split_merge(listA, i_begin, i_end, listB):
    if i_begin < i_end:
        i_middle = (i_end + i_begin) / 2 
        split_merge(listA, i_begin, i_middle, listB)
        split_merge(listA, i_middle + 1, i_end, listB)
        merge(listB, i_begin, i_middle + 1, i_end, listA)

def merge(listA, i_left, i_right, i_end, listB):
    i = i_left
    j = i_right
    for k in xrange(i_left, i_end + 1):
        if(i < i_right and ( j > i_end or listA[i] < listA[j])):
            listB[k] = listA[i]
            i += 1
        else:
            listB[k] = listA[j]
            j += 1


def copy_array(alist, templist):
    for element in alist:
        templist.append(element)

def main():
    alist = [4, 5, 2, 10, 1, 3, 10]
    merge_sort(alist)
    print(alist)

if __name__ == "__main__":
    main()


def merge(listA, i_left, i_right, i_end, listB)
  i = i_left
  j = i_right

  for k in (i_left..i_end)
    if i < i_right && (j > i_end || listA[i] < listA[j])
      listB[k] =listA[i]
      i += 1
    else
      listB[k] =  listA[j]
      j += 1
    end
  end
end


def split_merge_sort(listA, i_begin, i_end, listB)
  if i_begin < i_end
    i_middle = (i_begin + i_end) / 2
    split_merge_sort(listA, i_begin, i_middle, listB)
    split_merge_sort(listA, i_middle + 1, i_end, listB)
    merge(listB, i_begin, i_middle + 1, i_end, listA)
  end
end

def copy_array(listA, listB)
  for e in listA
    listB.push(e)
  end
end

def merge_sort(listA)
  listB = []
  copy_array(listA, listB)
  split_merge_sort(listA, 0, listA.length - 1, listB)
end

listA = [1, 2, 10, 3, 6]
merge_sort(listA)

for e in listA
  print e
  print ","
end

binary search
# -*- coding=utf-8 -*-
def binary_search(alist, left, right, num):
    if left <= right:
        middle = (left + right) / 2

        if alist[middle] == num:
            return middle

        if num < alist[middle]:
            return binary_search(alist, left, middle - 1, num)
        else:
            return binary_search(alist, middle + 1, right, num)
    else:
        return -1

def main():
    alist = [1, 3, 5, 6, 7, 8, 10]

    print(binary_search(alist, 0, 6, 9))

if __name__ == "__main__":
    main()

BFPRT(线性查找算法)
DFS(深度优先搜索)
BFS(广度优先搜索)
Dijkstra算法
动态规划算法
朴素贝叶斯分类算法