堆排序：
1 void HeapAdjust(int *arraydata,int rootnode,int len) 2 { 3 int j; 4 int t; 5 while(2*rootnode+1<len) 6 { 7 j=2*rootnode+1; 8 if ((j+1)<len) //基右子树存在,则比较左右子树的大小 9 { 10 if(arraydata[j]<arraydata[j+1]) //若左子树小于右子树，则调整为右子树于其双亲结点比较 11 { 12 j++; 13 } 14 } 15 if (arraydata[rootnode]<arraydata[j]) //若双亲结点小于兄弟结点，则进行交换 16 { 17 t=arraydata[rootnode]; 18 arraydata[rootnode]=arraydata[j]; 19 arraydata[j]=t; 20 rootnode=j; //堆被破坏，需要重新调整 21 } 22 else 23 break; 24 } 25 } 26 void HeapSort(int *data,int n) 27 { 28 int t,i; 29 int j; 30 for (i=n/2-1;i>=0;i--) 31 { 32 HeapAdjust(data,i,n); 33 } 34 35 for (int k=0;k<n;k++)// 输出原始数据树建的堆数据 36 { 37 cout<<data[k]<<" "; 38 } 39 cout<<endl; 40 41 for(i=n-1;i>0;i--) 42 { 43 t=data[0]; 44 data[0]=data[i]; 45 data[i]=t; 46 47 for (int i=0;i<n;i++) //输出交换后的数据，即将根结构的数据放到最后，使其成为有序序列 48 { 49 cout<<data[i]<<" "; 50 } 51 cout<<endl; 52 53 HeapAdjust(data,0,i); //将前i个数据重新构成堆 54 55 for (int i=0;i<n;i++) //输出堆数据 56 { 57 cout<<data[i]<<" "; 58 } 59 cout<<endl; 60 } 61 } 62 int main(int argc,char* argv) 63 { 64 int b[]={69,65,90,37,92,6,28,54}; 65 n=sizeof (b)/sizeof(b[0]); 66 67 for (int i=0;i<n;i++) 68 { 69 cout<<b[i]<<","; 70 } 71 cout<<endl; 72 73 HeapSort(b,n); 74 75 for (int i=0;i<n;i++) 76 { 77 cout<<b[i]<<","; 78 } 79 cout<<endl; 80 81 return 0; 82 }
参考资料：
1 void mybubble(int *a,int n) 2 { 3 if (NULL==a&&n<=0) 4 { 5 printf("parameter error! "); 6 } 7 8 int i,j; 9 int temp; 10 for(i=0;i<n-1;i++) //控制外层循环，n个数需要n-1次 11 for(j=n-1;j>=i;j--) //从后往前比较 12 //for(j=0;j<n-1-i;j++)//从前往后比较，控制内情循环，每次比较n-1-i次 13 { 14 if (a[j]>a[j+1])//如果前一个数大于后一个数，则交换 15 { 16 temp=a[j]; 17 a[j]=a[j+1]; 18 a[j+1]=temp; 19 } 20 21 } 22 23 24 display(a,n); 25 26 }
1 #include <stdio.h> 2 /* 3 4 选择排序 5 插入排序 6 冒泡排序 7 希尔排序 8 堆排序 9 快速排序 10 11 */ 12 //////////////////////////////////////////////////////// 13 void SelectSort(int *a,int n) 14 { 15 int i,j; 16 int temp=0; 17 int flag=0; 18 19 for (i=0;i<n-1;i++) 20 { 21 temp=a[i]; //暂存要比较的数 22 flag=i; //记录temp中存放数据的标号 23 for (j=i+1;j<n;j++)//从i+1到n间的数据进行操作 24 { 25 if (a[j]<temp) //找出比a[i]中小的数据 26 { 27 temp=a[j]; 28 flag=j; 29 } 30 } 31 32 if (flag!=i)//将最小的数放入a[i]中 33 { 34 a[flag]=a[i]; 35 a[i]=temp; 36 } 37 } 38 } 39 40 ///////////////////////////////////////////////////// 41 void InsertSort(int *a,int n) 42 { 43 int i,j; 44 int temp; 45 for (i=1;i<n;i++) 46 { 47 temp=a[i]; //暂存当前比较的数 48 for (j=i-1;j>=0;j--)//从i-1到0间的数据进行操作 49 { 50 if (temp<a[j]) //检查是否有插入的可能 51 { 52 a[j+1]=a[j]; 53 } 54 else 55 break; 56 } 57 58 a[j+1]=temp;//最后插入 59 } 60 } 61 62 ////////////////////////////////////////////////// 63 void BubbleSort(int *a,int n) 64 { 65 int i,j; 66 int temp; 67 for (i=0;i<n-1;++i) 68 { 69 for (j=n-1;j>i;--j)//从n-1到i，即从前到后，将最小的值放到前面 70 { 71 if (a[j]<a[j-1]) 72 { 73 temp=a[j]; 74 a[j]=a[j-1]; 75 a[j-1]=temp; 76 } 77 } 78 } 79 } 80 81 ///////////////////////////////////////////////////// 82 void ShellSort(int *a,int n) 83 { 84 int i,j; 85 int step; 86 int temp; 87 88 for (step=n/2;step>0;step=step/2) //第k趟排序 89 { 90 for (i=step;i<n;i++) 91 { 92 temp=a[i]; 93 for (j=i-step;j>=0;j-=step) 94 { 95 if (temp<a[j]) 96 { 97 a[j+step]=a[j]; 98 } 99 else 100 break; 101 } 102 a[j+step]=temp; 103 } 104 } 105 106 } 107 ///////////////////////////////////////////////// 108 void AdjustMinHeap(int *a,int pos,int len) 109 { 110 int temp; 111 int child; 112 113 for (temp=a[pos];2*pos+1<=len;pos=child) 114 { 115 child=2*pos+1; 116 if (child<len&&a[child]>a[child+1]) 117 { 118 child++; 119 } 120 if (a[child]<temp) 121 { 122 a[pos]=a[child]; 123 } 124 else 125 break; 126 } 127 a[pos]=temp; 128 } 129 130 void MinHeapSort(int *a,int len) 131 { 132 int i; 133 int temp; 134 for (i=len/2-1;i>=0;i--) 135 { 136 AdjustMinHeap(a,i,len-1); 137 } 138 for (i=len-1;i>=0;i--) 139 { 140 temp=a[0]; 141 a[0]=a[i]; 142 a[i]=temp; 143 AdjustMinHeap(a,0,i-1); 144 } 145 } 146 147 void AdjustMaxHeap(int *a,int pos,int len)//生成大根堆 148 { 149 while((2*pos+1)<len) 150 { 151 int m=2*pos+1; 152 if((2*pos+2)<len) 153 { 154 if(a[2*pos+1]<a[2*pos+2]) 155 m=2*pos+2; 156 } 157 if (a[pos]<a[m]) //堆被破坏，需要调整 158 { 159 int tempData=a[pos]; //交换数据 160 a[pos]=a[m]; 161 a[m]=tempData; 162 163 pos=m; 164 } 165 else 166 break; //堆未破坏，无需调整 167 } 168 } 169 170 void MaxHeapSort(int *a,int len) 171 { 172 int i=0; 173 174 for (i=len/2-1;i>=0;i--) //将数组建成大根堆 175 { 176 AdjustMaxHeap(a,i,len); 177 } 178 179 for (i=len-1;i>0;i--) 180 { 181 int temp=a[0]; //与最后一个记录交换 182 a[0]=a[i]; 183 a[i]=temp; 184 185 AdjustMaxHeap(a,0,i);//重新将数据调整为大根堆 186 } 187 } 188 ////////////////////////////////////////////////// 189 void QuickSort(int *a,int left,int right) 190 { 191 int i,j,temp; 192 i=left; 193 j=right; 194 temp=a[left]; 195 if (left>right) 196 { 197 return; 198 } 199 200 while(i!=j) 201 { 202 while(a[j]>=temp&&j>i) 203 { 204 j--; 205 } 206 207 if (j>i) //将大值放于后面 208 { 209 a[i++]=a[j]; 210 } 211 212 while (a[i]<=temp&&j>i) 213 { 214 i++; 215 } 216 217 if(j>i) //将小值放于前面 218 { 219 a[j--]=a[i]; 220 221 } 222 } 223 224 a[i]=temp; 225 QuickSort(a,left,i-1); 226 QuickSort(a,i+1,right); 227 } 228 229 230 //////////////////////////////////////////////// 231 int main() 232 { 233 234 int i=0; 235 int a[]={38,65,97,76,13,27,49}; 236 int len=sizeof(a)/sizeof(a[0]); 237 238 for(i=0;i<len;i++) 239 printf("%d ",a[i]); 240 printf(" "); 241 242 // SelectSort(a,len); 243 // BubbleSort(a,len); 244 // InsertSort(a,len); 245 // ShellSort(a,len); 246 // MinHeapSort(a,len); 247 // MaxHeapSort(a,len); 248 QuickSort(a,0,len-1); 249 250 for(i=0;i<len;i++) 251 printf("%d ",a[i]); 252 printf(" "); 253 254 return 0; 255 }
1 #include <iostream> 2 3 using namespace std; 4 5 void display(int a[],int len) 6 { 7 for(int i=0;i<len;i++) 8 { 9 printf("%d ",a[i]); 10 } 11 printf(" "); 12 13 } 14 15 16 //插入排序 17 void insert(int *a,int n) 18 { 19 int i,j,temp; 20 21 for(i=1;i<10;i++) /*外循环控制趟数，n个数从第2个数开始到最后共进行n-1次插入*/ 22 { 23 temp=a[i]; /*将待插入数暂存于变量t中*/ 24 for( j=i-1 ; j>=0 && temp<a[j] ; j-- ) /*在有序序列（下标0 ~ i-1）中寻找插入位置*/ 25 a[j+1]=a[j]; /*若未找到插入位置，则当前元素后移一个位置*/ 26 a[j+1]=temp; /*找到插入位置，完成插入*/ 27 } 28 display(a,n); 29 } 30 //希尔排序 31 void shellSort(int a[],int len) 32 { 33 int step; 34 int i,j; 35 int temp; 36 for(step=len/2; step>0;step/=2) //用来控制步长,最后递减到1 37 { 38 // i从第step开始排列，应为插入排序的第一个元素 39 // 可以先不动，从第二个开始排序 40 for(i=step;i<len;i++) 41 { 42 temp = a[i]; 43 for(j=i-step;(j>=0 && temp < a[j]);j-=step) 44 { 45 a[j+step] = a[j]; 46 } 47 a[j+step] = temp; //将第一个位置填上 48 } 49 50 } 51 display(a,len); 52 } 53 //选择排序 54 void choise(int *a,int n) 55 { 56 int i,j,k,temp; 57 for(i=0;i<n-1;i++) /*外循环控制趟数，n个数选n-1趟*/ 58 { 59 k=i; /*假设当前趟的第一个数为最值,记在k中 */ 60 for(j=i+1;j<n;j++) /*从下一个数到最后一个数之间找最值*/ 61 if(a[k]>a[j]) /*若其后有比最值更大的*/ 62 k=j; /*则将其下标记在k中*/ 63 64 if(i!=k) /*若k不为最初的i值，说明在其后找到比其更大的数*/ 65 { /*则交换最值和当前序列的第一个数*/ 66 temp=a[i]; 67 a[i]=a[k]; 68 a[k]=temp; 69 } 70 } 71 display(a,n); 72 } 73 //堆排序 74 /*假设节点i的左右子树都是最大堆，操作使节点i的子树变成最大堆*/ 75 void maxHeap(int A[],int len,int i) 76 { 77 int l,r,large,temp; 78 l=2*i; 79 r=2*i+1; 80 large=i; 81 if(l<len) 82 { 83 if(A[l]>A[i]) 84 { 85 large=l; 86 } 87 } 88 if(r<len) 89 { 90 if(A[r]>A[large]) 91 { 92 large=r; 93 } 94 } 95 96 if(large!=i) 97 { 98 temp=A[large]; 99 A[large]=A[i]; 100 A[i]=temp; 101 maxHeap(A,len,large); 102 } 103 } 104 105 /*建立大根堆*/ 106 void buildMaxHeap(int A[],int len) 107 { 108 int i; 109 for(i=len/2-1;i>=0;i--) 110 maxHeap(A,len,i); 111 } 112 113 114 /*堆排序*/ 115 void maxHeapSort(int A[],int len) 116 { 117 int i,temp; 118 buildMaxHeap(A,len); 119 printf("建立大跟堆 "); 120 for(i=0;i<len;i++) 121 printf("%d ",A[i]); 122 printf(" "); 123 124 for(i=len;i>1;i--) 125 { 126 temp=A[0]; 127 A[0]=A[i-1]; 128 A[i-1]=temp; 129 printf("%d ",A[i-1]); 130 buildMaxHeap(A,i-1); 131 } 132 printf(" "); 133 } 134 //冒泡排序 135 void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/ 136 { 137 int i,j,temp; 138 for(i=0;i<n-1;i++) /*外循环控制排序趟数，n个数排n-1趟 */ 139 for(j=0;j<n-1-i;j++) /*内循环每次比较的次数，第i次比较n-i次*/ 140 if(a[j]>a[j+1]) //相信元素比较，逆序则交换 141 { 142 temp=a[j]; 143 a[j]=a[j+1]; 144 a[j+1]=temp; 145 } 146 display(a,n); 147 } 148 //快速排序 149 void quick_sort(int *arr, int begin, int end) 150 { 151 char pivot = arr[begin]; 152 int i,j; 153 i = begin; 154 j = end; 155 while(i < j) 156 { 157 while(arr[j] >= pivot && i < j) 158 j --; 159 arr[i] = arr[j]; 160 while(arr[i] <= pivot && i < j) 161 i ++; 162 arr[j] = arr[i]; 163 } 164 arr[i] = pivot; 165 if( i-1 > begin) 166 quick_sort(arr, begin, i - 1); 167 if( end > i + 1) 168 quick_sort(arr, i + 1, end); 169 170 //display(arr,end+1); 171 } 172 //基数排序 173 #define GET_MASK_VALUE(x, mask, shift) (((x) & mask) >> (shift)) 174 int find_max(int array[], int len, int mask, int shift) 175 { 176 int i = 0; 177 int max = GET_MASK_VALUE(array[i], mask, shift); 178 179 for (i = 1; i < len; i++) { 180 if (GET_MASK_VALUE(array[i], mask, shift) > max) 181 max = GET_MASK_VALUE(array[i], mask, shift); 182 } 183 184 return max; 185 } 186 187 void count_sort(int array[], int sort[], int len, int mask, int shift) 188 { 189 int i, max; 190 int *temp = NULL; 191 192 max = find_max(array, len, mask, shift); 193 194 printf("mask:%-8x shift:%d ", mask, shift); 195 196 temp = (int *)malloc((max + 1)* sizeof(int)); 197 if (temp == NULL) { 198 return; 199 } 200 201 memset(temp, 0, sizeof(int) * (max + 1)); 202 203 for (i = 0; i < len; i++) { 204 temp[GET_MASK_VALUE(array[i], mask, shift)]++; 205 } 206 207 for (i = 1; i <= max; i++) { 208 temp[i] += temp[i-1]; 209 } 210 211 for (i = (len - 1); i >= 0; i--) { 212 sort[temp[GET_MASK_VALUE(array[i], mask, shift)]-1] = array[i]; 213 temp[GET_MASK_VALUE(array[i], mask, shift)]--; 214 } 215 } 216 217 void radix_sort(int array[], int len, int digit_bits, int bit_width) 218 { 219 int i = 0; 220 int *sort = NULL; 221 int cycles = 0, shift = 0; 222 unsigned int mask = 0; 223 unsigned int initmask = (1 << bit_width) - 1; 224 225 sort = (int *)malloc(sizeof(int) * len); 226 if (sort == NULL) 227 return; 228 229 memset(sort, 0, sizeof(int) * len); 230 231 cycles = digit_bits / bit_width; 232 233 for (i = 0; i < cycles; i++) { 234 mask = initmask << (i * bit_width); 235 shift = i * bit_width; 236 count_sort(array, sort, len, mask, shift); 237 memcpy(array, sort, sizeof(int) * len); 238 } 239 240 return; 241 } 242 243 void main(void) 244 { 245 246 const int Asize=20; 247 printf("------------插入排序----------------------- "); 248 int a[]={9,6,4,2,8,7,5,3,1}; 249 display(a,9); 250 insert(a,9); 251 252 253 printf("------------希尔排序------------------------- "); 254 int b[]={9,6,4,2,8,7,5,3,1}; 255 display(b,9); 256 shellSort(b,9); 257 258 printf("------------冒泡排序------------------------- "); 259 int c[]={9,6,4,2,8,7,5,3,1}; 260 display(c,9); 261 bubble(c,9); 262 263 264 printf("------------快速排序------------------------- "); 265 int d[]={9,6,4,2,8,7,5,3,1}; 266 display(d,9); 267 quick_sort(d,0,8); 268 display(d,9); 269 270 printf("------------选择排序------------------------ "); 271 int e[]={9,6,4,2,8,7,5,3,1}; 272 display(e,9); 273 choise(e,9); 274 275 276 printf("------------堆排序------------------------- "); 277 int f[]={9,6,4,2,8,7,5,3,1}; 278 display(f,9); 279 maxHeapSort(f,9); 280 display(f,9); 281 282 283 printf("------------基数排序--------------------- "); 284 int g[]={9,6,4,2,8,7,5,3,1}; 285 display(g,9); 286 radix_sort(g,9,sizeof(int)*8,4); 287 display(g,9); 288 289 290 291 }
一、冒泡法：
基本思想：如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次相邻元素的两两比较，在第j趟比较中要进行n-j次两两比较。比较的顺序从前往后，经过一趟比较后，将最值沉底（换到最后一个元素位置），最大值沉底为升序，最小值沉底为降序。
相邻元素两两比较，每趟将最值沉底即可确定一个数在结果的位置，确定元素位置的顺序是从后往前，其余元素可能作相对位置的调整。可以进行升序或降序排序。
源代码：
1 void bubble(int *a,int n) /*定义两个参数：数组首地址与数组大小*/ 2 { 3 int i,j,temp; 4 for(i=0;i<n-1;i++) /*外循环控制排序趟数，n个数排n-1趟 */ 5 for(j=0;j<n-1-i;j++) /*内循环每次比较的次数，第i次比较n-i次*/ 6 if(a[j]>a[j+1]) //相信元素比较，逆序则交换 7 { 8 temp=a[j]; 9 a[j]=a[j+1]; 10 a[j+1]=temp; 11 } 12 }
优点：稳定，比较次数已知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。
二、选择排序
基本思想：每趟选出一个最值和无序序列的第一个数交换，n个数共选n-1趟。第i趟假设i为最值下标，然后将最值和i+1至最后一个数比较，找出最值的下标，若最值下标不为初设值，则将最值元素和下标为i的元素交换。
每趟是选出一个最值确定其在结果序列中的位置，确定元素的位置是从前往后，而每趟最多进行一次交换，其余元素的相对位置不变。可进行降序排序或升序排序。
定义外部n-1次循环，假设第一个为最值，放在参数中，在从下一个数以后找最值若后面有比前面假设的最值更大的就放在k中，然后在对k进行分析。若k部位最初的i值。也就是假设的i不是最值，那么就交换最值和当前序列的第一个数
测试代码：
1 void choise(int *a,int n) 2 { 3 int i,j,k,temp; 4 for(i=0;i<n-1;i++) /*外循环控制趟数，n个数选n-1趟*/ 5 { 6 k=i; /*假设当前趟的第一个数为最值,记在k中 */ 7 for(j=i+1;j<n;j++) /*从下一个数到最后一个数之间找最值*/ 8 if(a[k]>a[j]) /*若其后有比最值更大的*/ 9 k=j; /*则将其下标记在k中*/ 10 11 if(i!=k) /*若k不为最初的i值，说明在其后找到比其更大的数*/ 12 { /*则交换最值和当前序列的第一个数*/ 13 temp=a[i]; 14 a[i]=a[k]; 15 a[k]=temp; 16 } 17 } 18 }
优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少；
缺点：相对之下还是慢。
三、插入排序
基本思想：将序列分为有序序列和无序列，依次从无序序列中取出元素值插入到有序序列的合适位置。初始是有序序列中只有第一个数，其余n-1个数组成无序序列，则n个数需进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找，在未找到插入点之前可以同时向后移动元素，为插入元素准备空间。
每趟从无序序列中取出第一个数插入到有序序列的合适位置，元素的最终位置在最后一趟插入后才能确定位置。也可是先用循环查找插入位置（可从前往后或从后往前），再将插入位置之后的元素（有序列中）逐个后移一个位置，最后完成插入。该算法的特点是在寻找插入位置的同时完成元素的移动。因为元素的移动必须从后往前，则可将两个操作结合在一起完成，提高算法效率。仍可进行升序或降序排序。
算法实现：假设待排序的元素有n个，对应的关键字分别是a1,a2,..an，因为第1个元素是有序的，所以从第2个元素开始，将a2与a1进行比较，如果a2<a1，则将a2插入到a1之前；否则，说明已经有序，不需要移动a2,这样有序的元素个数变为2.然后将a3与a1和a2进行比较，确定a3的位置。首先将a3与a2进行比较，如果a3>=a2,则说明a1 a2,a3已经是有序排序。如果a3<a2，则继续将a3与a1比较，如果a3<a1，则将a3插入到a1之前，否则，将a3插入到a1与a2之间，即完成了a1,a2,a3的排列。依次类推，直到最后一个关键字an插入到n-1个有序排列。
测试代码：
1 void insert(int *a,int n) 2 { 3 int i,j,temp; 4 5 for(i=1;i<10;i++) /*外循环控制趟数，n个数从第2个数开始到最后共进行n-1次插入*/ 6 { 7 temp=a[i]; /*将待插入数暂存于变量t中*/ 8 for( j=i-1 ; j>=0 && temp<a[j] ; j-- ) /*在有序序列（下标0 ~ i-1）中寻找插入位置*/ 9 a[j+1]=a[j]; /*若未找到插入位置，则当前元素后移一个位置*/ 10 a[j+1]=temp; /*找到插入位置，完成插入*/ 11 } 12 13 }
优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。
四、快速排序
基本思想：
测试代码：
优点：极快，数据移动少；
缺点：不稳定。