Heap Sort

Quick Sort

1、快速排序：选一个元素i，把比i小的元素放在i前面、比i大的元素放在i后面，再递归地把i的前后二部分进行快速排序。

2、选的元素i有讲究，最好的情况是i为最中间的元素。

3、算法最坏的情况：O(n^2)

Merge Sort

1、归并排序：将已有序的子序列合并，得到完全有序的序列（即先使每个子序列有序，再使子序列段间有序）。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

2、例子：

设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8,1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11；

3、时间复杂度：O(nlogn)

Heap Sort

Def

A heap is a complete binary tree with possibly some rightmost leaves removed. If we place elements in a heap, then for every node v, the value placed in v must not be larger than the values placed in the children of v.

//此处为小根堆的定义

· The children of A[i] are A[2i+1] and A[2i+2];

· The father of A[i] is A[(i-1)/2].

Algorithm

Time Complexity Analysis

1、MakeHeap(H[n]): //错位相减法

so time is O(n).

2、FixHeap(i):

· The height h of the heap H[n]: h <= logn+1

· The number of the leaves in heap H[n]:

minimum: 1 (h=logn+1)

maximum: > n/2 (h=logn)

FixHeap(i) runs h times, so its time is O(logn).

3、HeapSort(H[n]):

“while” runs n times, so its time is O(nlogn).

4、The whole time complexity: O(nlogn)