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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include<iostream>
using namespace std;
//冒泡 (稳定) 时间复杂度太低下，最坏和平均是0（n^2），最好是0(n)
//******************************
//void BubbleSort1(int a[],int n){
// for(int i=0;i<n;i++){
// for(int j=i+1;j<n;j++){//网上好多这个地方写的跟我的不一样，但是这种傻瓜式的挨个比较太好理解
// if(a[i]>a[j])
// swap(a[i],a[j]);
// }
// }
// for(int i=0;i<n;i++)
// cout<<a[i]<<" ";
//}
//快排，快啊（不稳定）。 最好和平均为0（nlogn），最坏0（n^2）
//************************************
int part(int a[],int low,int high){//划分成左右子数组，找到中间位置
int temp=a[high];//最后一个元素作为中间元素
int i=low-1;//i是慢速下标
for(int j=low;j<high;j++){//挨个检查元素，比中间值小的在放在它的左边，大的放在右边
if(a[j]<=temp){
i++;
swap(a[i],a[j]);
}
}
swap(a[i+1],a[high]);
return i+1;//找到第一个比中间值大的元素，返回它的位置,这就是中间元素所在位置
}
void QuickSort(int a[],int low, int high){
if(low<high){
int mid=part(a,low,high);
QuickSort(a,low,mid-1);
QuickSort(a,mid+1,high);
}
}
//插入排序，数据很小时候使用
//****************************888
void InsertSort(int a[],int n){
for(int i=1;i<n;i++){//temp是被排序的数字，从第二个数字之后插入已经排好的数组
int temp=a[i];
int j;
for(j=i-1;j>=0&&a[j]>temp;j--){//j代表已经排好序的数字，从后往前比较
a[j+1]=a[j];
}
a[j+1]=temp;
}
}
//堆排。利用堆这种数据结构，特殊的二叉树
//堆排太不好理解了
//随时准备调整满足大顶堆
//***************************************************8
void MaxHeap(int a[], int start,int endd){//父节点，最后一个叶子节点
int dad=start;
int son=dad*2+1;
while(son<endd){
if(son+1<endd && a[son]<a[son+1])//找到子节点最大de那个
son++;
if(a[dad]>a[son])
break;
else{
swap(a[dad],a[son]);
dad=son;
son=dad*2+1;
}
}
}
void HeapSort(int a[],int n){
for(int i=n/2-1;i>=0;i--)//找到最后一个父节点,依次到第一个父节点。初始化，调整好大顶堆
MaxHeap(a,i,n);
for(int i=n-1;i>0;i--){
swap(a[0],a[i]);//将当前根节点0和最后一个节点i调换
MaxHeap(a,0,i);//i为调整后的根节点，不是最大，所以重新调整
}
}
int main(){
int a[]={1,5,6,7,8,9,0,3,2,1};
// BubbleSort1(a,4);
// QuickSort(a,0,9);
//InsertSort(a,10);
HeapSort(a,10);
for(int i=0;i<10;i++)
cout<<a[i]<<" ";
return 0;
}
|
