懶排序演算法
懶就先建一個視圖，然後對視圖排序。
空間富裕就都insert 到一個臨時表，在時間列上建索引，然後select
我同意歸並排序是好方法，但如果是遠程資料庫，建議不要做
② 菜鳥的一個C++插入法排序問題
插入排序沒有那麼復雜。
另外，請注意編程習慣：排序函數就是用來排序的，別把輸出寫在排序函數裡面。
void insert( int* a, int num )
{
for( int i=1; i<num; i++ ){//對於從第二個到最後為止的每一個數
int j;
int cur=a[i];//先把這個數另存一份
for( j=i; j>0&&a[j-1]>cur; j-- )//從這個位置向左找每個大於這個數的數
a[j] = a[j-1];//大就向右移動一個位置
a[j] = cur;//最後在移出的空位里插入這個數
}
}
32
32 12 : (12=>cur) ==> 32 32 ==> 12 32
12 32 45 : (45=>cur) ==> 12 32 45
12 32 45 0 : (0=>cur) ==> 12 32 45 45 ==> 12 32 32 45 ==> 12 12 32 45 ==> 0 12 32 45
③ py冒泡法排序
冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。
它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。
這個演算法的名字由來是因為越大的元素會經由交換慢慢「浮」到數列的頂端，故名冒泡排序。
以上是網路詞條對冒泡排序的官方解釋。
但是我要說一下我的個人理解，我覺得冒泡排序的核心思想是：每次比較兩個數，如果他們順序錯誤（大於或者小於），那麼就把他們置換。
例如：如果要將五個無序的數字做升序排列（也就是從小到大排列），那麼利用冒泡排序如何實現呢？
首先，比較第一個數和第二個數的大小，由於是從小到大排列，所以如果第一個數大於第二個數，則將這兩個數互換位置，反之則不變。
然後進行第二個數和第三個數比較，同上。
這樣依次比較一輪後，你會發現，總共比了4次，也就是說，如果有n個數進行比較，那麼需要n-1次才能完成。
上面過程主要完成了一輪比較，最終確定了一個最大的數，並且排在5個數的最後，也就是第五個數。
那麼也就意味著需要在進行第一個數到第四個數的一輪比較，確定最大值。
接著從第一個數到第三個數......
這樣規律就很明顯了，五個數需要比較四輪，就能將5個數升序排列，所以n個數需要比較n-1輪。
以上就是冒泡排序的實現思路，接下來看代碼！
如何實現？
到底該怎麼實現呢？看了上面的分析，我相信你也能編出來吧！
print(list)
演算法的優劣主要看它的時間復雜度，冒泡排序的時間復雜度為：O(N^2)
可以看出，冒泡排序的時間復雜度偏高，所以它還不是最優演算法！
④ vb.net 排列組合演算法
看了你說遞歸的效率低。那麼你可以不用的。
給出的方法就是先生成第一個排列，然後每次調用下面的函數給出下一個排列，這樣生成的效率很高，這個函數可以內聯。
這個是很經典的排列組合演算法啊？在網上能搜到一大堆。
大概是那種帶指向的移動的演算法。我給你搜一個吧。
我找了幾個，這個是我覺得說的比較清楚的，你可以仔細參考一下，看不懂的話再搜點別的好了。。
全排列的演算法跟這個不太一樣的。需要有點改動的。
至於語言的話，應該不會有太大問題吧。。basic版的確實比較少，現在我也比較懶不想動手寫。。還是要靠你自己啦。
★生成排列的演算法：
比如要生成5，4，3，2，1的全排列，首先找出一個最小的排列12345, 然後依次調用n!次STL演算法中的next_permutation()即可輸出所有的全排列情況。所以這種演算法的細節就是STL algorithm中next_permutation()的實現機制。詳細的實現代碼，大夥可以參考侯捷的《STL源代碼剖析》，在這里我只說一下我的理解：
1> 首先從最尾端開始往前尋找兩個相鄰元素，令第一個元素為*i,第二個元素為*ii，且滿足*i<*ii，找到這樣一組相鄰的元素後。
2> 再從最尾端開始往前檢驗，找出第一個大於*i的元素，令為*k，將i,k元素對調。
3> 再將ii及ii之後的所有元素顛倒排列，此即所求之"下一個"排列。
prev_permutation()演算法的思路也基本相同，只不過它們尋找的"拐點"不同，在next_permutation()演算法中尋找的是峰值拐點，而在prev_permutation()演算法中尋找的是谷值拐點。另外，在第二步中，prev_permutation()要找的是第一個小於*i的元素而不是第一個大於*i的元素。
具體例子，有空再舉，現在時間太晚了:)
★生成組合的演算法：
如下面截圖所示，分全組合和r-組合兩種情況。
這里有一段核心代碼：
//--------------------------------------------------------
// Generate next combination (algorithm from Rosen p. 286)
//--------------------------------------------------------
public int[] getNext () {
if (numLeft.equals (total)) {
numLeft = numLeft.subtract (BigInteger.ONE);
return a;
}
int i = r - 1;
while (a[i] == n - r + i) {
i--;
}
a[i] = a[i] + 1;
for (int j = i + 1; j < r; j++) {
a[j] = a[i] + j - i;
}
numLeft = numLeft.subtract (BigInteger.ONE);
return a; //這里返回的a數組，存儲的就是下標的排列組合。
}
到這里，也許大夥會有一個疑問，假如要求的不是數字的排列組合，而是字元或字元串的排列組合呢？怎麼辦？其實很簡單，你只要拿數組的下標來做排列組合，返回他們下標的排列組合，然後再到原數組中讀取字元串值，就可以輸出全部的排列組合結果。
⑤ 懂c++編程的進來幫我解答題目
// 只需找出最小的四個數，放到指定位置，
// 再找到最大的放到指定位置即可。
#include <iostream>
using namespace std;
void swap( int *a, int *b )
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int main()
{
int num[5][5] = { {2, 3, 9, 10, 11}, {31, 44, 6, 8, 7}, {66, 74, 1, 4, 7},
{55, 66, 77, 88, 99}, {23, 34, 45, 56, 67} };
int *p;
int *q;
int *begin, *end;
begin = &(num[0][0]);
end = &(num[0][0]) + 25;
// 列印排序前矩陣
p = begin;
for ( int i = 1; i <= 25; i++ )
{
printf( "%d ", *p );
if ( i % 5 == 0)
printf( "\n" );
p++;
}
// 實現最小四個數放到num[0][0], num[0][1], num[0][2], num[0][3]
p = begin;
for ( int j = 0; j < 4; j++ )
{
for ( q = p; q < end; q++ )
if ( *p > *q )
swap( p, q );
p++;
}
swap( &num[0][1], &num[0][4] ); // 第二小的放到右上角
swap( &num[0][2], &num[4][0] ); // 第三小的放到左下角
swap( &num[0][3], &num[4][4] ); // 第四小的放到右下角
// 實現最大數放到num[2][2]
int max = *p;
for ( p = begin; p < end; p++ )
if ( *p > max )
{
q = p;
max = *p;
}
swap( q, &num[2][2] );
// 列印排序後矩陣
printf( "排序後：\n " );
p = begin;
for ( int i = 1; i <= 25; i++ )
{
printf( "%d ", *p );
if ( i % 5 == 0)
printf( "\n" );
p++;
}
return 0;
}
方便起見我直接給矩陣賦值了，若你想人工輸入，自己改一下。
實現的結果：
2 3 9 10 11
31 44 6 8 7
66 74 1 4 7
55 66 77 88 99
23 34 45 56 67
排序後：
1 11 23 67 2
31 44 10 9 8
66 74 99 6 7
55 66 77 88 7
3 34 45 56 4
請按任意鍵繼續. . .
這是按我對你題目的理解寫的程序，不知是否合要求。祝好運。
⑥ java中利用PriorityQueue實現排序 效率怎樣
演算法效率夠用就好，沒必要最優。PriorityQueue的演算法應該算不錯的了，快速排序可能會優於它，效果應該不是很明顯
如果你需要的是排好序的數組，那麼多出一個數組的內存開銷。
⑦ 關於排序演算法比較的問題
樓上的說法不準確吧，不能說比較和交換的次數不是一個級別的，交換也不是最多隻有n次。比如一個逆序的數組進行升序的冒泡排序，交換就遠遠超過n次。
但是假設比較次數為P(n)，交換次數為Q(n)，那麼因為交換發生在比較之後（基本上排序演算法都是這樣，樓主可以自己想想），必然有Q(n)<=P(n)。如果時間復雜度為T(n)，那麼顯然根據時間復雜度的定義（極限定義），用大O表示法可以忽略Q(n)項（或用P(n)代替Q(n)），僅用P對T進行表示。
因為大O表示法是對時間復雜度上限的一個估計，而這種每比較一次就需要交換的情況確實存在（最差情況），所以在T(n)中使用P(n)對Q(n)進行替換並不會擴大對上限估計，而只是乘以了系數2，在大O表示法中常數項是不寫入的。
這些數學分析一般在國內的演算法教材中都不寫入的，MIT的《ITA》注重這方面的敘述。
關於總結其實樓主可以自己去搜，上來問這行為太懶了。不過我也幫你找來吧。
冒泡法：
這是最原始，也是眾所周知的最慢的演算法了。他的名字的由來因為它的工作看來象是冒泡： 復雜度為O(n*n)。當數據為正序，將不會有交換。復雜度為O(0)。
直接插入排序：O(n*n)
選擇排序：O(n*n)
快速排序：平均時間復雜度log2(n)*n，所有內部排序方法中最高好的，大多數情況下總是最好的。
歸並排序：log2(n)*n
堆排序：log2(n)*n
希爾排序：演算法的復雜度為n的1.2次冪
⑧ 求C++高手做一個排序系統，用C++做。（一定要是C++）！
#include <iostream>
#define NUM 5 //無序表元素個數
#define MAX 1000 //元素最大值
using namespace std;
int list[NUM*10]={0}; //存儲無序表及排序結果
int merge_list[NUM*10]={0}; //歸並排序時用於存無序表
int merge_link[NUM*10]={0}; //歸並排序時輔助
void init();
void init_list(int);
void out(int[], int, int);
void swap(int, int);
//1 直接插入排序 -------------------------------------------------------
void insert_sort(int len)
{
int insertNum;
for (int i=0; i<len; i++)
{
insertNum = list[i]; // 待插入元素
int j = i;
while (j>0 && insertNum<list[j-1]) // 尋找插入位置
{
list[j] = list[j-1];
j--;
}
list[j] = insertNum;
}
}
//2 二分插入排序
void binary_insert_sort(int len)
{
int middle;
for (int i=0; i<len; i++)
{
int insertNum = list[i];
int left = 0;
int right = i-1;
while (left <= right) //二分法尋找插入位置
{
middle = (left + right)/2;
if (insertNum > list[middle]) left = middle+1;
else right = middle-1;
}
for (int j=i; j>left; j--) list[j] = list[j-1];
list[left] = insertNum;
}
}
//3 希爾排序------------------------------------------------------------
void shell_sort(int len)
{
int insertNum;
int gap = len/2; //初始增量
while (gap) //當gap>=1
{
for (int i=gap; i<len; i++) //對gap間隔子序列進行插入排序
{
insertNum = list[i]; //待插入元素
int j = i;
while (j>=gap && insertNum<list[j-gap])
{ //尋找插入位置
list[j] = list[j-gap];
j -= gap;
}
list[j] = insertNum; //插入
}
gap = gap/2; //縮小增量
}
}
//4 直接選擇排序 -------------------------------------------------------
void select_sort(int len)
{
int k;
for (int i=0; i<len; i++)
{
k = i;
for (int j=i+1; j<len; j++) // 找最小元素
if (list[j] < list[k]) k = j;
swap(i, k); // 將最小元素放入i位置
}
}
//5 堆排序-------------------------------------------------------------
// 堆的建立或調整
void filterDown(int current, int last)
{
int child = 2*current+1; //child為current的子女位置
int temp = list[current]; //暫存子樹根結點
while (child <= last) //判斷是否到最後結尾
{
if (child<last && list[child]<list[child+1]) child++;
//讓child指向兩子女中的大者
if (temp >= list[child]) break; //temp的關鍵碼大則不做調整
else //否則子女中的大者上移
{
list[current] = list[child];
current = child;
child = 2*child+1;
}
}
list[current] = temp; //temp中暫存元素放到合適位置
}
void heap_sort(int len)
{
for (int i=(len-2)/2; i>=0; i--) filterDown(i, len-1);
//建立堆
for (i=len-1; i>0; i--)
{
swap(0, i);
filterDown(0, i-1); //不斷調整堆為最大堆
}
}
//6 冒泡排序------------------------------------------------------------
void bubble_sort(int len)
{
for (int i=0; i<len; i++)
for (int j=i+1; j<len; j++)
if (list[i] > list[j]) swap(i, j);
}
//7 Shaker排序------------------------------------------------------------
void shaker_sort(int len)
{
int i, left = 0, right = len - 1,shift = 0;
while(left < right)
{
for(i = left; i < right; i++) //向右進行氣泡排序
{
if(list[i] > list[i+1])
{
swap(i, i+1);
shift = i;
}
}
right = shift;
for(i = right; i > left; i--) //向左進行氣泡排序
{
if(list[i] < list[i-1])
{
swap(i ,i-1);
shift = i;
}
}
left = shift;
}
}
//8 快速排序------------------------------------------------------------
void quick_sort(int left, int right)
{
int i = left;
int j = right;
int pivot = list[left];
while (i<j)
{
while (i<j && list[j]>=pivot) j--; //找到比基數小的元素
if(i < j) swap(i, j);
while (i<j && list[i]<=pivot) i++; //找到比基數大的元素
if(i < j) swap(i, j);
}
if (i!=left) quick_sort(left, i-1); //對list[left...i-1]排序
if (j!=right) quick_sort(j+1, right); //對list[j+1...right]排序
}
//9 歸並排序:遞歸-----------------------------------------------------------
//具體方法:以merger_link[]提供鏈表功能。merger_link[i]對應在有序子序列中
//merger_list[i]後一個結點在原merger_list[]中的下標；
//merger_link[0]總是表示有序子序列開始的結點在merge_list[]中的下標；
//st1,st2為兩個有序序列的第一個結點；
//將他們歸並，並返回其第一個結點的下標，即merger_link[0]
int list_merge(int st1, int st2)
{
int k = 0, i = st1, j = st2;
while (i && j) //當兩序列未檢測完
if (merge_list[i] <= merge_list[j]) //將merge_list[i]和merge_list[j]
{ //中小的連接到merger_link[k]後
merge_link[k] = i;
k = i;
i = merge_link[i];
}else
{
merge_link[k] = j;
k = j;
j = merge_link[j];
}
if (!i) merge_link[k] = j; //將剩餘未檢測完的merge_list[]
else merge_link[k] = i; //連接到merger_link[k]後
return merge_link[0];
}
int merge_sort(int left, int right)
{
if (left>=right) return left;
int middle = (left + right)/2;
//對左右兩子序列進行歸並
return list_merge(merge_sort(left,middle), merge_sort(middle+1,right));
}
//10 計數排序
void counting_sort(int len, int max)
{
int result[NUM]; //臨時保存結果
int* mark = new int[max]; //標記無序表中元素
memset(mark, 0, max * sizeof(int));
for (int i = 0; i < len; i++) mark[list[i]]++;
//統計元素出現次數
for (i = 1; i < max; i++) mark[i] += mark[i - 1];
//計算元素在有序表中位置
for (i = len - 1; i >= 0; i--)
{
result[mark[list[i]] - 1] = list[i];//通過mark[]直接將list[i]
mark[list[i]]--; //有序存入result[]
}
delete []mark;
//轉存到list以便輸出結果
for (i=0; i<len; i++) list[i] = result[i];
}
//-------- 主過程-----------------------------------------------------
int main()
{
init();
int inp;
while (true)
{
cout<<"請選擇: "; //選擇排序方法
cin >> inp;
init_list(inp); //初始化無序表
switch(inp) //各種排序
{
case 1: insert_sort(NUM);break;
case 2: binary_insert_sort(NUM);break;
case 3: shell_sort(NUM);break;
case 4: select_sort(NUM);break;
case 5: heap_sort(NUM);break;
case 6: bubble_sort(NUM);break;
case 7: shaker_sort(NUM);break;
case 8: quick_sort(0, NUM-1);break;
case 9: merge_sort(1, NUM);break;
case 10:counting_sort(NUM, MAX);break;
case 0: exit(0);break;
}
cout<< "排序結果:"<<endl; //輸出排序結果
if (inp!=9) out(list, 0, NUM);
else {
int i = merge_link[0];
int j = 0;
while (i)
{
j++;
cout<<merge_list[i]<<" ";
i = merge_link[i];
if (j%18 == 0) cout <<endl;
}
cout <<endl;
}
}
return 0;
}
// 輔助方法---------------------------------------------------------------
// 初始化界面
void init()
{
cout <<endl;
cout << " 十種常用排序演算法(升序)" <<endl;
cout << " ---------------------------------"<<endl;
cout << " 1. 直接插入排序" <<endl;
cout << " 2. 二分插入排序" <<endl;
cout << " 3. 希爾排序" <<endl;
cout << " 4. 直接選擇排序" <<endl;
cout << " 5. 堆排序" <<endl;
cout << " 6. 冒泡排序" <<endl;
cout << " 7. Shaker排序" <<endl;
cout << " 8. 快速排序" <<endl;
cout << " 9. 歸並排序" <<endl;
cout << " 10.計數排序" <<endl;
cout << " 0. 退出" <<endl;
cout << " ---------------------------------"<<endl;
}
//初始化無序表
void init_list(int inp)
{
if (inp == 0) return;
cout<<"待排序數列:"<<endl;
if (inp == 9) //為歸並排序生成無序表
{
for (int i=1; i<=NUM; i++)
{
merge_list[i] = rand()%MAX;
merge_link[i] = 0;
}
out(merge_list,1,NUM);
}
else //為其他排序生成無序表
{
for (int i=0; i<NUM; i++) list[i]=rand()%MAX;
out(list, 0, NUM);
}
}
// 輸出結果
void out(int result[], int st, int len)
{
for (int i=st; i<st+len; i++)
{
cout<< result[i] << " ";
if ((i+1)%18 == 0) cout<<endl;
}
cout <<endl;
}
//交換list[i]和list[j]
void swap(int i, int j)
{
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
⑨ linux下編寫2個排序演算法
正好之前寫過，代碼直接貼出來吧
bubble_sort.c
#include <stdio.h>
#define swap(a, b) \
(a) = (a) + (b);\
(b) = (a) - (b);\
(a) = (a) - (b)
void bubble_sort(int a[], int n)
{
int i = 0;
bool change = true;
for (; i < n; ++i)
{
change = false;
for (int j = i; j < n - 1; ++j)
{
if (a[j] > a[j+1])
{
swap(a[j], a[j+1]);
change = true;
}
}
}
}
int main()
{
int a[] = {1, 8, 4, 5, 10, 9};
bubble_sort(a, 6);
for (int i = 0; i < 6; ++i)
{
printf("%d\t",a[i]);
}
putchar((char)'\n');
return 0;
}
shell_sort.c
#include <stdio.h>
#define swap(a, b) \
(a) = (a) + (b);\
(b) = (a) - (b);\
(a) = (a) - (b)
void shell_sort(int a[], unsigned int len)
{
int i, j;/*two iterators*/
int increment;
for (increment = len/2; increment >= 1; increment /=2)
{
for (i = increment; i < len; i++)
{
for (j = i; j >= increment; j-=increment)
{
if (a[j] > a[j - increment])
{
swap(a[j], a[j - increment]);
}
}
}
}
}
int main()
{
int i ;/*a iterator*/
int a[] = {8, 2, 7, 6, 3, 1, 4, 10};
shell_sort(a, 8);
for (i = 0; i < 8; i++)
{
printf("%d\t",a[i]);
}
putchar((char)'\n');
}
冒泡排序和希爾排序，理論上，冒泡法的精確上界為O(n^2)，希爾排序在選定好的增量時能突破這個上界。
⑩ 怎麼讓Heap sort 變為穩定排序
演算法引進：
在這里我直接引用《大話數據結構》裡面的開頭：
在前面講到 簡單選擇排序 ，它在待排序的 n 個記錄中選擇一個最小的記錄需要比較 n - 1 次，本來這也可以理解，查找第一個數據需要比較這么多次是正常的，否則如何知道他是最小的記錄。
可惜的是，這樣的操作並沒有把每一趟的比較結果保存下來，在後一趟的比較重，有許多比較在前一趟已經做過了，但由於前一趟排序時未保存這些比較結果，所以後一趟排序時又重復執行了這些比較操作，因而記錄的比較次數較多。
如果可以做到每次在選擇到最小記錄的同時，並根據比較結果對其他記錄做出相應的調整，那樣排序的總體效率就會非常高了。而堆排序，就是對簡單選擇排序進行的一種改進，這種改進的效果是非常明顯的。
基本思想：
在介紹堆排序之前，我們先來介紹一下堆：
《大話數據結構》里的定義：堆 是具有下列性質的完全二叉樹：每個節點的值都大於或等於其左右孩子節點的值，成為大頂堆（大根堆）；或者每個節點的值都小於或等於其左右節點的值，成為小頂堆（小根堆）。
當時我在看到這里的時候也對有「堆是否是完全二叉樹」有過疑問，網上也有說不是完全二叉樹的，但是無論堆是不是完全二叉樹，尚且保留意見。我們只要知道，在這里我們採用完全二叉樹形式的大根堆（小跟堆），主要是為了方便存儲和計算（後面我們會看到帶來的便利）。
堆排序演算法：
堆排序就是利用堆（假設利用大根堆）進行排序的方法，它的基本思想是：將待排序的序列構造成一個大根堆。此時，整個序列的最大值就是堆頂的根節點。將它移走（其實就是將其與堆數組的末尾元素交換，此時末尾元素就是最大值），然後將剩餘的 n - 1 個序列重新構造成一個堆，這樣就會得到 n 個元素中的次小的值。如此反復執行，便能得到一個有序序列了。
大根堆排序演算法的基本操作：
①建堆，建堆是不斷調整堆的過程，從 len/2 處開始調整，一直到第一個節點，此處 len 是堆中元素的個數。建堆的過程是線性的過程，從 len/2 到 0 處一直調用調整堆的過程，相當於 o(h1) + o(h2) …+ o(hlen/2) 其中 h 表示節點的深度， len/2 表示節點的個數，這是一個求和的過程，結果是線性的 O(n)。
②調整堆：調整堆在構建堆的過程中會用到，而且在堆排序過程中也會用到。利用的思想是比較節點i和它的孩子節點 left(i) , right(i)，選出三者最大(或者最小)者，如果最大（小）值不是節點i而是它的一個孩子節點，那邊交互節點i和該節點，然後再調用調整堆過程，這是一個遞歸的過程。調整堆的過程時間復雜度與堆的深度有關系，是 lgn 的操作，因為是沿著深度方向進行調整的。
③堆排序：堆排序是利用上面的兩個過程來進行的。首先是根據元素構建堆。然後將堆的根節點取出(一般是與最後一個節點進行交換)，將前面 len-1 個節點繼續進行堆調整的過程，然後再將根節點取出，這樣一直到所有節點都取出。堆排序過程的時間復雜度是 O(nlgn)。因為建堆的時間復雜度是 O(n)（調用一次）；調整堆的時間復雜度是 lgn，調用了 n-1 次，所以堆排序的時間復雜度是 O(nlgn)。
在這個過程中是需要大量的圖示才能看的明白的，但是我懶。。。。。。
演算法實現：
<?php //堆排序（對簡單選擇排序的改進） function swap(array &$arr,$a,$b){ $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; } //調整 $arr[$start]的關鍵字，使$arr[$start]、$arr[$start+1]、、、$arr[$end]成為一個大根堆（根節點最大的完全二叉樹） //注意這里節點 s 的左右孩子是 2*s + 1 和 2*s+2 （數組開始下標為 0 時） function HeapAdjust(array &$arr,$start,$end){ $temp = $arr[$start]; //沿關鍵字較大的孩子節點向下篩選 //左右孩子計算（我這里數組開始下標識 0） //左孩子2 * $start + 1，右孩子2 * $start + 2 for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){ if($j != $end && $arr[$j] < $arr[$j + 1]){ $j ++; //轉化為右孩子 } if($temp >= $arr[$j]){ break; //已經滿足大根堆 } //將根節點設置為子節點的較大值 $arr[$start] = $arr[$j]; //繼續往下 $start = $j; } $arr[$start] = $temp; } function HeapSort(array &$arr){ $count = count($arr); //先將數組構造成大根堆（由於是完全二叉樹，所以這里用floor($count/2)-1，下標小於或等於這數的節點都是有孩子的節點) for($i = floor($count / 2) - 1;$i >= 0;$i --){ HeapAdjust($arr,$i,$count); } for($i = $count - 1;$i >= 0;$i --){ //將堆頂元素與最後一個元素交換，獲取到最大元素（交換後的最後一個元素），將最大元素放到數組末尾 swap($arr,0,$i); //經過交換，將最後一個元素（最大元素）脫離大根堆，並將未經排序的新樹($arr[0...$i-1])重新調整為大根堆 HeapAdjust($arr,0,$i - 1); } } $arr = array(9,1,5,8,3,7,4,6,2); HeapSort($arr); var_mp($arr);
時間復雜度分析：
它的運行時間只要是消耗在初始構建對和在重建堆屎的反復篩選上。
總體上來說，堆排序的時間復雜度是 O(nlogn)。由於堆排序對原始記錄的排序狀態並不敏感，因此它無論是最好、最差和平均時間復雜度都是 O(nlogn)。這在性能上顯然要遠遠好於冒泡、簡單選擇、直接插入的 O(n^2) 的時間復雜度了。
堆排序是一種不穩定排序方法。
本篇博客參考自《大話數據結構》，在此僅作記錄，方便以後查閱，大神勿噴！