Hi Java!

1、 堆排序定义
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。
注意：
①堆中任一子树亦是堆。
②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。
3、堆排序特点
堆排序(HeapSort)是一树形选择排序。
堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的记录。
4、堆排序与直接插入排序的区别
直 接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比 较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行 了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
5、堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 void selection_sort(int list[], int n)
 {
   int i, j, min;
 
   for (i = 0; i < n - 1; i++)
   {
     min = i;
     for (j = i+1; j < n; j++)
     {
        if (list[j] < list[min])
        {
           min = j;
        }
     }
     swap(&list[i], &list[min]);
   }
 }

关键代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

 void quicksort(int list[],int m,int n)
 {
	int key,i,j,k;
	if( m < n)
	{
	   k = choose_pivot(m,n);
	   swap(&list[m],&list[k]);
	   key = list[m];
	   i = m+1;
	   j = n;
	   while(i <= j)
	   {
		  while((i <= n) && (list[i] <= key))
				 i++;
		  while((j >= m) && (list[j] > key))
				 j--;
		  if( i < j)
				 swap(&list[i],&list[j]);
	   }
 
	   swap(&list[m],&list[j]);
	   quicksort(list,m,j-1);
	   quicksort(list,j+1,n);
	}
 }

原文：http://cprogramminglanguage.net/quicksort-algorithm-c-source-code.aspx