1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4
5
6 void print(int a[], int n){
7 for(int j= 0; j<n; j++){
8 cout<<a[j] <<" ";
9 }
10 cout<<endl;
11 }
12
13
14
15 /**
16 * 已知H[s…m]除了H[s] 外均满足堆的定义
17 * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,
18 *
19 * @param H是待调整的堆数组
20 * @param s是待调整的数组元素的位置
21 * @param length是数组的长度
22 *
23 */
24 void HeapAdjust(int H[],int s, int length)
25 {
26 int tmp = H[s];
27 int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
28 while (child < length) {
29 if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
30 ++child ;
31 }
32 if(H[s]<H[child]) { // 如果较大的子结点大于父结点
33 H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
34 s = child; // 重新设置s ,即待调整的下一个结点的位置
35 child = 2*s+1;
36 } else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
37 break;
38 }
39 H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
40 }
41 print(H,length);
42 }
43
44
45 /**
46 * 初始堆进行调整
47 * 将H[0..length-1]建成堆
48 * 调整完之后第一个元素是序列的最小的元素
49 */
50 void BuildingHeap(int H[], int length)
51 {
52 //最后一个有孩子的节点的位置 i= (length -1) / 2
53 for (int i = length/2 -1 ; i >= 0; --i)
54 HeapAdjust(H,i,length);
55 }
56 /**
57 * 堆排序算法
58 */
59 void HeapSort(int H[],int length)
60 {
61 //初始堆
62 BuildingHeap(H, length);
63 //从最后一个元素开始对序列进行调整
64 for (int i = length - 1; i > 0; --i)
65 {
66 //交换堆顶元素H[0]和堆中最后一个元素
67 int temp = H[i]; H[i] = H[0]; H[0] = temp;
68 //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
69 HeapAdjust(H,0,i);
70 }
71 }
72
73 int main(){
74 int H[10] = {3,1,5,7,2,4,9,6,10,8};
75 cout<<"初始值：";
76 print(H,10);
77 HeapSort(H,10);
78 //selectSort(a, 8);
79 cout<<"结果：";
80 print(H,10);
81
82 }
基数排序
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<windows.h>
4
5 typedef struct node
6 {
7 int nValue;
8 struct node *pNext;
9 }MyRadix;
10
11 void Sort(int arr[],int nLength,int nBase)
12 {
13 int nNum = 1;
14 MyRadix **pRadix = NULL;
15 int i;
16 int nIndex;
17 MyRadix *pTemp = NULL;
18 MyRadix *pMark = NULL;
19
20 //求被除数
21 while(nBase > 1)
22 {
23 nNum*=10;
24 nBase--;
25 }
26
27 //申请桶
28 pRadix = (MyRadix**)malloc(sizeof(MyRadix*) * 10);
29 memset(pRadix,0,sizeof(MyRadix*) * 10);
30
31 for(i = 0;i<nLength;i++)
32 {
33 nIndex = arr[i]/nNum%10;
34
35 pTemp = (MyRadix*)malloc(sizeof(MyRadix));
36 pTemp->nValue = arr[i];
37 pTemp->pNext = NULL;
38
39 //尾添加
40 if(pRadix[nIndex] == NULL)
41 {
42 pRadix[nIndex] = pTemp;
43 }
44 else
45 {
46 pMark = pRadix[nIndex];
47 while(pMark->pNext != NULL)
48 {
49 pMark = pMark->pNext;
50 }
51 pMark->pNext = pTemp;
52 }
53 }
54
55 //将元素放回原数组
56 nBase = 0;
57 for(i = 0;i<10;i++)
58 {
59 pMark = pRadix[i];
60 while(pMark)
61 {
62 arr[nBase] = pMark->nValue;
63 nBase++;
64 pMark = pMark->pNext;
65 }
66 }
67
68 //释放空间
69 for(i = 0;i<10;i++)
70 {
71 pMark = pRadix[i];
72 while(pMark)
73 {
74 pTemp = pMark;
75 pMark = pMark->pNext;
76 free(pTemp);
77 pTemp = NULL;
78 }
79 }
80
81 free(pRadix);
82 pRadix = NULL;
83 }
84
85 void RadixSort(int arr[],int nLength)
86 {
87 int nMax;
88 int i;
89 int nLoopTimes;
90 if(arr == NULL || nLength <=0)return;
91
92 //找最大值
93 nMax = arr[0];
94 for(i = 1;i<nLength;i++)
95 {
96 if(arr[i] > nMax)
97 {
98 nMax = arr[i];
99 }
100 }
101 //获得入桶次数
102 nLoopTimes = 0;
103 while(nMax)
104 {
105 nMax/=10;
106 nLoopTimes++;
107 }
108
109 //各个位入桶
110 for(i = 1;i<=nLoopTimes;i++)
111 {
112 //当前位入桶
113 Sort(arr,nLength,i);
114 }
115
116 }
117
118 int main()
119 {
120 int arr[] = {24,23,34,270,18,29,110,220,19,46,32};
121 int i;
122 RadixSort(arr,sizeof(arr)/sizeof(arr[0]));
123 for(i = 0;i<sizeof(arr)/sizeof(arr[0]);i++)
124 {
125 printf("%d ",arr[i]);
126 }
127 return 0;
128 }
桶排序
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<windows.h>
4
5 typedef struct node
6 {
7 int nValue;
8 struct node *pPre;
9 struct node *pNext;
10 }MyBucket;
11
12 //创建桶
13 MyBucket **CreateBucket(int arr[],int nLength,int *pSize)
14 {
15 int nMax;
16 int nMin;
17 int nMaxIndex;
18 int nMinIndex;
19 int i;
20 int nNum;
21 int nIndex;
22 MyBucket *pTemp = NULL;
23 MyBucket **pBucket = NULL;
24
25 if(arr == NULL || nLength <=0)return NULL;
26
27 //查询最大值最小值
28 nMax = arr[0];
29 nMin = arr[0];
30 for(i = 1;i<nLength;i++)
31 {
32 if(arr[i] > nMax)
33 {
34 nMax = arr[i];
35 }
36 if(arr[i] < nMin)
37 {
38 nMin = arr[i];
39 }
40 }
41
42 //计算位数
43 nNum = nMax;
44 i = 0;
45 while(nNum >0)
46 {
47 i++;
48 nNum/=10;
49 }
50
51 //计算被除数
52 nNum = 1;
53 while(i >1)
54 {
55 nNum*=10;
56 i--;
57 }
58
59 //根据最大值最小值建桶
60 nMaxIndex = nMax/nNum;
61 nMinIndex = nMin/nNum;
62 *pSize = nMaxIndex-nMinIndex+1;
63
64 pBucket = (MyBucket**)malloc(sizeof(MyBucket*)*(nMaxIndex-nMinIndex+1));
65 memset(pBucket,0,sizeof(MyBucket*)*(nMaxIndex-nMinIndex+1));
66
67 for(i = 0;i<nLength;i++)
68 {
69 nIndex = arr[i]/nNum - nMinIndex;
70
71 pTemp = (MyBucket*)malloc(sizeof(MyBucket));
72 pTemp->nValue = arr[i];
73 pTemp->pPre = NULL;
74
75 //双向链表头添加
76 pTemp->pNext = pBucket[nIndex];
77
78 if(pBucket[nIndex] != NULL)
79 {
80 pBucket[nIndex]->pPre = pTemp;
81 }
82
83 pBucket[nIndex] = pTemp;
84 }
85
86 return pBucket;
87 }
88
89 void Sort(MyBucket *pHead)
90 {
91 MyBucket *pLast= NULL; //有序的最后一个
92 MyBucket *pFirst = NULL; //无序的第一个
93 int nNum;
94
95 pFirst = pHead->pNext;
96
97 while(pFirst != NULL)
98 {
99 //有序数组的最后一个 是无序数组的前一个
100 pLast = pFirst->pPre;
101
102 //标记待插入值
103 nNum = pFirst->nValue;
104
105 //将无序元素放入有序数组
106 while(pLast != NULL && pLast->nValue > nNum)
107 {
108 pLast->pNext->nValue = pLast->nValue;
109 pLast = pLast->pPre;
110 }
111
112 //到达链表头的情况
113 if(pLast == NULL)
114 {
115 pHead->nValue = nNum;
116 }
117 else
118 {
119 pLast->pNext->nValue = nNum;
120 }
121
122 pFirst = pFirst->pNext;
123 }
124 }
125 void BucketSort(int arr[],int nLength)
126 {
127 MyBucket **pBucket = NULL;
128 int i;
129 int nSize;
130 int j;
131 MyBucket *pMark = NULL;
132 MyBucket *pDel = NULL;
133
134 if(arr == NULL || nLength <=0)return;
135
136 pBucket = CreateBucket(arr,nLength,&nSize);
137
138 //各桶内进行排序
139 for(i = 0;i<nSize;i++)
140 {
141 if(pBucket[i] != NULL)
142 {
143 Sort(pBucket[i]);
144 }
145 }
146
147 //元素放回原数组
148 j = 0;
149 for(i = 0;i<nSize;i++)
150 {
151 pMark = pBucket[i];
152 while(pMark)
153 {
154 arr[j] = pMark->nValue;
155 pMark = pMark->pNext;
156 j++;
157 }
158 }
159 //空间释放
160 for(i = 0;i<nSize;i++)
161 {
162 pMark = pBucket[i];
163 while(pMark)
164 {
165 pDel = pMark;
166 pMark = pMark->pNext;
167 free(pDel);
168 pDel = NULL;
169 }
170 }
171
172 free(pBucket);
173 pBucket = NULL;
174 }
175
176
177 int main()
178 {
179 int arr[] = {150,234,343,270,128,239,110,220,119,246,342};
180 int i;
181 BucketSort(arr,sizeof(arr)/sizeof(arr[0]));
182 for(i = 0;i<sizeof(arr)/sizeof(arr[0]);i++)
183 {
184 printf("%d ",arr[i]);
185 }
186 return 0;
187 }