編程珠璣第二版快速排序
1 qsort4(0, n-1);
2 isort3();
3
4 void qsort4(l, u)
5 {
6 if (u - l < cutoff) //cutoff是一個小整數，如果要排序的數組很小，可以用插入排序，速度更快
7 return;
8 swap(L, randint(l, u)) //將第一個數據與后面的數據隨即交換，避免要排序的數據已是升序排列或者第一個數據很小
9 t = x[l]; //t為中間元素，所有數據與其進行比較，小于t的放到左邊，大于t的放到右邊
10 i = l;
11 j = u+1;
12 loop
13 do
14 {
15 i++;
16 } while (i <= u && x[i] < t); //從第二個數據開始比較，遇到大于t的數據終止循環
17
18 do
19 {
20 j--;
21 } while (x[j] > t); //從最后一個數據進行比較，遇到小于t的終止循環
22
23 if (i > j) //如果i>j，數據分組成功，跳出循環
24 break;
25 temp = x[i]; //交換上面兩個循環終止時的數據
26 x[i] = x[j];
27 x[j] = temp;
28
29 swap(l, j); //交換x[i]與x[j]的值，分組完成
30 qsort4(l, j-1); //排序小于t的數據
31 qsort4(j+1, u); //排序大于t的數據
32 }
33
34 void isort3() //插入排序，當排序的數據很少時可以用此排序
35 {
36 int i,j;
37 for i = [l, n)
38 t = x[i];
39 for (j=i; j>0 && x[j-1]>t; j--)
40 {
41 x[j] = x[j-1];
42 }
43 x[j] = t;
44 }
轉自：http://www.shnenglu.com/humanchao/archive/2008/08/18/59241.html
void QuickSort(int* pData,int left,int right)
{
int i = left, j = right;
int middle = pData[(left+right)/2]; // midlle value
int iTemp;
do
{
while (pData[i] < middle && i < right) i++;
while (pData[j] > middle && j > left) j--;
if (i < j) // swap
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++; j--;
}
else if (i == j)
{
i++; j--;
}
} while (i < j);
if (left < j) QuickSort(pData,left,j);
if (right > i) QuickSort(pData,i,right);
}
1 // array是待調整的堆數組，i是待調整的數組元素的位置，nlength是數組的長度
2 void HeapAdjust(int array[],int i,int nLength) //本函數功能是：根據數組array構建大根堆
3 {
4 int nChild;
5 int nTemp;
6 for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
7 {
8 // 子結點的位置=2*（父結點位置）+ 1
9 nChild = 2 * i + 1;
10 // 得到子結點中較大的結點
11 if (nChild < nLength - 1 && array[nChild + 1] > array[nChild])
12 ++nChild;
13 // 如果較大的子結點大于父結點那么把較大的子結點往上移動，替換它的父結點
14 if (nTemp < array[nChild])
15 {
16 array[i]= array[nChild];
17 }
18 else // 否則退出循環
19 {
20 break;
21 }
22 // 最后把需要調整的元素值放到合適的位置
23 array[nChild]= nTemp;
24 }
25 }
26 // 堆排序算法
27 void HeapSort(int array[],int length)
28 {
29 // 調整序列的前半部分元素，調整完之后第一個元素是序列的最大的元素
30 for (int i = length / 2 - 1; i >= 0; --i)
31 {
32 HeapAdjust(array,i,length);
33 }
34 // 從最后一個元素開始對序列進行調整，不斷的縮小調整的范圍直到第一個元素
35 for (int i = length - 1; i > 0; --i)
36 {
37 // 把第一個元素和當前的最后一個元素交換，
38 // 保證當前的最后一個位置的元素都是在現在的這個序列之中最大的
39 Swap(&array[0],&array[i]);
40 // 不斷縮小調整heap的范圍，每一次調整完畢保證第一個元素是當前序列的最大值
41 HeapAdjust(array,0,i);
42 }
43 }
堆排序算法（C++描述）
1 #define MAX 100//數據元素的最大個數
2 typedef struct
3 {
4 int r[MAX];
5 int length;
6 }SqList;//定義一個線性表用于存放數據元素
7 void HeapAdjust(SqList &L,int s,int m)
8 {
9 //已知L.r[s
m]中記錄除L.r[s]外均滿足堆的定義，本函數用于使L.r[sm]成為一個大頂堆
10 int j;
11 int e=L.r[s];
12 for(j=2*s;j<=m;j*=2)
13 {
14 if(j<M&&L.R[J]<L.R[J+1]) ++j;
15 if(e>=L.r[j]) break;
16 L.r[s]=L.r[j];
17 s=j;
18 }
19 L.r[s]=e;
20 }
21 void HeapSort(SqList &L)
22 {
23 //對順序表L進行堆排序
24 int i,e;
25 for(i=L.length/2;i>0;i--)
26 HeapAdjust(L,i,L.length);
27 for(i=L.length;i>1;i--)
28 {
29 //將大頂堆的頂記錄和最后一個記錄相互交換
30 e=L.r[1];
31 L.r[1]=L.r[i];
32 L.r[i]=e;
33 HeapAdjust(L,1,i-1);
34 }
35 }
posted on 2012-03-30 12:47
王海光 閱讀(617)
評論(0) 編輯 收藏 引用 所屬分類:
算法