1.
堆排序是一种优秀的排序算法，时间复杂度O(nlogn)，主要思想是用数组构造一个最大堆，满足跟节点的value>子节点的value，然后将堆顶元素（value最大）与最后一个叶子节点交换，再调整堆，使其满足最大堆的性质，重复上述步骤n-1次后就得到一个有序序列。
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAX 111111
#define LEFT(i) (i << 1)
#define RIGHT(i) (i << 1|1)
using namespace std;
int a[MAX], Heap_Size, a_Length;
void Max_Heapify(int i){
int largest, l, r;
l = LEFT(i);
r = RIGHT(i);
if(l <= Heap_Size && a[l] > a[i]) largest = l;
else largest = i;
if(r <= Heap_Size && a[r] > a[largest]) largest = r;
if(largest != i){
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
Max_Heapify(largest);
}
return;
}
void Build_Heap(){
for(int i = a_Length/; i >= ; i --)
Max_Heapify(i);
return;
}
void Heap_Sort(){
Build_Heap();
for(int i = a_Length; i >= ; i --){
int temp = a[];
a[] = a[i];
a[i] = temp;
Heap_Size--;
Max_Heapify();
}
return ;
}
int main(){
freopen("data.cpp", "r", stdin);
freopen("out.cpp", "w", stdout);
while(~scanf("%d", &a_Length)){
Heap_Size = a_Length;
for(int i = ; i <= a_Length; i ++) scanf("%d", a+i);
Heap_Sort();
printf("Length = %d\n", a_Length);
for(int i = ; i < a_Length; i ++) printf("%d ", a[i]);
printf("%d\n\n\n", a[a_Length]);
}
return ;
}
2.
快速排序：主要思想就是随机选定一个数x，以该数为基准，将数组划分，左边都小于或等于它，右边都大于它，这样就将数组划分成左右两部分，而数x则是处于正确位置，然后再重复上述过程分别处理左右部分，直到数组有序。时间复杂度O(nlogn).
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define MAX 111111
using namespace std;
int a[MAX], a_length;
int Rand_Partition(int p, int r){
int x = a[r], i = p-;
for(int j = p; j < r; j ++){
if(a[j] <= x){
i ++;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
a[r] = a[i+];
a[i+] = x;
return i+;
}
void Qucik_Sort(int p, int r){
if(p < r){ //与调用Rand_Partition（）函数效果一样;
int i = p-;
for(int j = p; j < r; j ++){
if(a[j] <= a[r]){
i ++;
swap(a[i], a[j]);
}
}
swap(a[r], a[i+]);
int q = i+; //end;
/* int q = Rand_Partition(p, r); */
Qucik_Sort(p, q-);
Qucik_Sort(q+, r);
}
}
int main(){
freopen("data.cpp", "r", stdin);
freopen("Quick_sort_out.cpp", "w", stdout);
while(~scanf("%d", &a_length)){
printf("Length = %d\n", a_length);
for(int i = ; i < a_length; i ++) scanf("%d", a+i);
Qucik_Sort(, a_length-);
for(int i = ; i < a_length-; i ++) printf("%d ", a[i]);
printf("%d\n\n\n", a[a_length-]);
}
return ;
}
3.
归并排序，采用分治策略，主要思想是假定数组a和b已经是有序的，那么可以在O(n)的时间内将他们合并成一个有序序列，现在将数组平均分成两部分，但这两部分并不是有序的，因此需要再次将这两个部分再分，使问题规模逐渐变小，继续递归划分，当子数组足够小时（即只有一个元素），可以直接求解，因为此时一个元素就是有序的。然后就可以合并这两个部分了，合并完之后就形成一个局部有序序列（我们最终要得到整个有序序列），此时向上回溯与其他有序部分进行合并，当回溯到跟节点时，整个序列就合并完毕，因此得到一个有序序列。
分治策略一般分为三步：（1）：分解原问题使问题规模变小以便我们直接处理，对于上述问题就是将原序列分解，当分解到子序列只有一个元素时就可直接求解（因为一个元素的序列已经是有序的了）；（2）治，即解决问题；（3）合并，将子问题解决之后要向上合并从而得到原问题的解。
分治策略一般使用递归来实现。
#include<stdio.h>
#include<string.h>
int a[];
int l[];
int r[];
void merge(int p, int mid, int q)
{
int nl = mid - p + ;
int nr = q - mid;
int i, j, k;
for(i = ; i < nl; i ++)
l[i] = a[p+i];
for(i = ; i <= nr; i ++)
r[i - ] = a[mid+i];
l[nl] = << ;
r[nr] = << ;
i = ;
j = ;
for(k = p; k <= q; k ++)
{
if(l[i] <= r[j])
a[k] = l[i++];
else
a[k] = r[j++];
}
} void merge_sort(int l, int r)
{
if(l < r)
{
int mid = (l + r) >> ;
merge_sort(l, mid);
merge_sort(mid + , r);
merge(l, mid, r);
}
} int main(int argc, char const *argv[])
{
int n, i;
freopen("data.cpp", "r", stdin);
freopen("Merge_out.cpp", "w", stdout);
while(~scanf("%d", &n))
{
printf("Length = %d\n", n);
for(i = ; i < n; i ++)
scanf("%d", &a[i]);
merge_sort(, n-);
for(i = ; i < n-; i ++)
printf("%d ",a[i]);
printf("%d\n\n\n", a[i]);
}
return ;
}
4.
最后一个是用二叉搜索树通过中序遍历得到的有序序列，时间复杂度也是O(nlogn)较简单和容易理解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
typedef struct Node{
int key;
Node *left;
Node *right;
Node(){
left = NULL;
right = NULL;
}
}Node;
Node *root;
stack<Node*>s;
void Insert(int key){
Node *tmp = new Node();
tmp->key = key;
Node *ff = root;
Node *flag = NULL;
while(ff){
flag = ff;
if(key <= ff->key) ff = ff->left;
else ff = ff->right;
}
if(flag == NULL){
root = new Node();
root->key = key;
return;
}
if(flag->key >= key) flag->left = tmp;
else flag->right = tmp;
} void Visist_Treee_1(Node *tmp){
if(tmp){
Visist_Treee_1(tmp->left);
printf("%d ", tmp->key);
Visist_Treee_1(tmp->right);
}
} /* void Visist_Treee_2(Node *tmp){ */
/* while(!s.empty()) s.pop(); */
/* s.push(tmp); */
/* while(!s.empty()){ */
/* Node *p = s.top(); */
/* s.pop(); */
/* while(p->left) s.push(p), p = p->left; */
/* Node *q = s.top(); */
/* s.pop(); */
/* printf("%d ", q->key); */
/* if(q->right) s.push(q); */
/* } */
/* } */ int main(){
int n, temp;
freopen("data.cpp", "r", stdin);
freopen("Binary_Tree_out.cpp", "w", stdout);
while(~scanf("%d", &n)){
root = NULL;
printf("Length = %d\n", n);
for(int i = ; i < n; i ++){
scanf("%d", &temp);
Insert(temp);
}
Visist_Treee_1(root);
printf("\n\n\n");
/* Visist_Treee_2(root); */
}
}