懒排序算法
懒就先建一个视图，然后对视图排序。
空间富裕就都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) 的时间复杂度了。
堆排序是一种不稳定排序方法。
本篇博客参考自《大话数据结构》，在此仅作记录，方便以后查阅，大神勿喷！