首页 > 代码库 > 七种排序算法的实现和总结
七种排序算法的实现和总结
最近把七种排序算法集中在一起写了一遍。
注释里有比较详细的说明。
1 /*排序算法大集合**/ 2 #include <stdio.h> 3 #include <string.h> 4 #include <stdlib.h> 5 6 //------------------快速排序------------------// 7 /* 8 核心: 9 如果你知道多少人该站你前面,多少人站你后面,你一定知道你该站哪个位置。 10 算法: 11 1.选取分界数,参考这个分界数,大于参考数放在右边,小于的放在左边。 12 2.对左右两边的序列分别递归进行1处理 13 3.将整个序列合并得到有序结果 14 */ 15 //分区函数 16 int Part(int Array[],int left, int right) 17 { 18 int temp; 19 temp = Array[left];//选取第一个数为分界数 20 while(left < right) 21 { 22 while(left < right && Array[right] > temp) 23 { 24 right--; 25 } 26 Array[left] = Array[right]; 27 while(left<right && Array[left]<=temp) 28 { 29 left++; 30 } 31 Array[right] = Array[left]; 32 } 33 Array[left] = temp; 34 return left; 35 } 36 void Quicksort(int Array[],int left, int right) 37 { 38 if(left < right) 39 { 40 int p= Part(Array, left, right); 41 Quicksort(Array, left, p-1); 42 Quicksort(Array, p+1, right); 43 } 44 } 45 //------------------插入排序------------------// 46 /* 47 核心: 48 每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子序列中的适当位置,直到全部记录插入完成为止。 49 算法: 50 1.初始时,a[0]自成1个有序区,无序区为a[1..n-1]。令i=1 51 2.将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。 52 3. i++并重复第二步直到i==n-1。排序完成。 53 */ 54 void InsertSort(int a[], int n) 55 { 56 int i, j, temp; 57 for(i = 1; i < n; ++i) 58 { 59 if(a[i] < a[i - 1]) 60 { 61 temp = a[i]; 62 for(j = i - 1; j >= 0 && a[j] > temp; --j) 63 a[j + 1] = a[j]; 64 a[j + 1] = temp; 65 } 66 } 67 } 68 //------------------选择排序------------------// 69 /* 70 核心: 71 选择排序将数据分为有序区和无序区从无序区选一个最小的元素直接放到有序区的最后。 72 算法: 73 1.初始时,数组全为无序区为a[0..n-1]。令i=0 74 2.在无序区a[i…n-1]中选取一个最小的元素,将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。 75 3.i++并重复第二步直到i==n-1。排序完成。 76 */ 77 void SelectionSort(int a[], int n) 78 { 79 int min, i, j; 80 for(i = 0; i < n - 1; ++i) 81 { 82 min = i; 83 for(j = i + 1; j < n; ++j) 84 if(a[j] < a[min]) 85 min = j; 86 87 if(min != i) 88 { 89 int t = a[i]; 90 a[i] = a[min]; 91 a[min] = t; 92 } 93 } 94 } 95 96 //------------------冒泡排序------------------// 97 /* 98 算法: 99 1.比较相邻的前后二个数据,如果前面数据大于后面的数据,就将二个数据交换。100 2.这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置。101 3.N=N-1,如果N不为0就重复前面二步,否则排序完成。102 分析:103 冒泡排序毕竟是一种效率低下的排序方法,在数据规模很小时,可以采用。数据规模比较大时,最好用其它排序方法。104 */105 void swap(int &a, int &b)106 {107 int t = a;108 a = b;109 b = t;110 }111 112 void BubbleSort(int a[], int n)113 {114 int i, j, flag = n;//用flag来记录a[flag]后面的有序数列,便不再比较115 while(flag > 0)116 {117 j = flag;118 flag = 0;119 for(i = 0; i < j; ++i)120 if(a[i] < a[i - 1])121 {122 swap(a[i], a[i - 1]);123 flag = j;124 }125 }126 }127 128 //------------------堆排序------------------//129 /*130 数据结构:131 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:132 任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。133 堆分为大顶堆和小顶堆,134 大顶堆的堆顶的关键字肯定是所有关键字中最大的,135 小顶堆的堆顶的关键字是所有关键字中最小的。136 算法:137 1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无序区;138 2)将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]; 139 3)由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,140 然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。141 不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。142 */143 void HeapAdjust(int a[], int i, int size)//堆的构造144 {145 int LeftChild = i * 2;146 int RightChild = LeftChild + 1;147 if(i <= size / 2)148 {149 int max = i;150 if(a[LeftChild] > a[max])151 max = LeftChild;152 if(RightChild <= size && a[RightChild] > a[max])153 max = RightChild;154 if(max != i)155 {156 swap(a[i], a[max]);157 HeapAdjust(a, max, size);158 }159 }160 }161 162 void HeapSort(int a[], int size)163 {164 int i;165 for(i = size / 2; i >= 1; --i)//堆的初始化166 HeapAdjust(a, i, size);167 168 for(i = size; i > 1; --i)169 {170 swap(a[1], a[i]);171 HeapAdjust(a, 1, i - 1);172 }173 }174 175 //------------------归并排序------------------//176 /*177 算法:178 并:179 将二个有序数列合并,只要从比较二个数列的第一个数,180 谁小就先取谁,取了后就在对应数列中删除这个数。181 然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。182 将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。183 归:184 当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,185 然后再合并相邻的二个小组就可以了。186 这样通过先递归的分解数列,187 再合并数列就完成了归并排序。188 */189 void MergeArray(int a[], int first, int mid, int last, int temp[])190 //使a[first...mid]和a[mid+1...last]两部分归并为有序数列191 {192 int i = first, j = mid + 1;193 int m = mid, n = last;194 int k = 0;195 while(i <= m && j <= n)196 {197 if(a[i] < a[j])198 temp[k++] = a[i++];199 else200 temp[k++] = a[j++];201 }202 203 while(i <= m)204 temp[k++] = a[i++];205 while(j <= n)206 temp[k++] = a[j++];207 208 for(i = 0; i < k; ++i)209 a[first + i] = temp[i];210 }211 212 void mergesort(int a[], int first, int last, int temp[])213 {214 if(first < last)215 {216 int mid = (first + last) / 2;217 mergesort(a, first, mid, temp);218 mergesort(a, mid + 1, last, temp);219 MergeArray(a, first, mid, last, temp);220 }221 }222 223 bool MergeSort(int a[], int n)224 {225 int *p = new int[n];226 if(p == NULL)227 return false; //若内存分配失败则返回FALSE228 mergesort(a, 0, n - 1, p);229 delete []p;230 return true;231 }232 233 //------------------LSD基数排序------------------//234 /*235 算法:236 1、分配,先从个位开始,根据位值(0-9)分别放到0~9号桶中237 2、收集,再将放置在0~9号桶中的数据按顺序放到数组中238 3、重复(1)(2)过程,从个位到最高位239 */240 //a[]为常量表,用来取num的第pos位的数字241 const int a[] = {1, 1, 10, 100, 1000, 10000,242 100000, 1000000, 10000000, 100000000, 1000000000};243 244 int GetNumInPos(int num, int pos)//取num的第pos位的数字245 {246 return ((num / a[pos]) % 10);247 }248 249 int FindMaxDigit(int array[], int size)//找到数组中最大的位数250 {251 int cnt = 1, x = 10;252 for(int i = 0; i < size; ++i)253 {254 while(array[i] >= a[cnt + 1])255 ++cnt;256 }257 return cnt;258 }259 260 void RadixSort(int array[], int size)261 {262 int *radixArrays[10]; //分配0~9的桶子空间263 int i;264 int KeyNum = FindMaxDigit(array, size);265 for(i = 0; i < 10; ++i)266 {267 radixArrays[i] = (int *)malloc(sizeof(int) * (size + 1));268 radixArrays[i][0] = 0; //此处记录各组数据的个数269 }270 271 int pos;272 for(pos = 1; pos <=KeyNum; ++pos)273 {274 for(i = 0; i < size; ++i)275 {276 int num = GetNumInPos(array[i], pos);277 int index = ++radixArrays[num][0];278 radixArrays[num][index] = array[i];279 }280 //收集281 int j;282 for(i = 0, j = 0; i < 10; ++i)283 {284 for(int k = 1; k <= radixArrays[i][0]; ++k)285 array[j++] = radixArrays[i][k];286 radixArrays[i][0] = 0;287 }288 }289 for(i = 0; i < 10; ++i)290 free(radixArrays[i]); //释放分配的空间291 }292 293 void PrintArr(int a[], int n)294 {295 for(int i = 0; i < n; ++i)296 printf("%d ", a[i]);297 printf("\n");298 }299 300 int main(void)301 {302 int array1[] = {12, 14, 54, 5, 6, 3, 9, 8, 47, 89}, array2[15];303 304 memcpy(array2, array1, sizeof(array1));305 int Left = 0, Right = 9;306 Quicksort(array2, Left, Right);307 printf("快速排序:\n");308 PrintArr(array2, 10);309 310 memcpy(array2, array1, sizeof(array1));311 InsertSort(array2, 10);312 printf("插入排序:\n");313 PrintArr(array2, 10);314 315 memcpy(array2, array1, sizeof(array1));316 SelectionSort(array2, 10);317 printf("选择排序:\n");318 PrintArr(array2, 10);319 320 memcpy(array2, array1, sizeof(array1));321 BubbleSort(array2, 10);322 printf("冒泡排序:\n");323 PrintArr(array2, 10);324 325 //堆排序是从a[1]开始排所以要对数组进行一下调整 326 int i;327 for(i = 0; i < 10; ++i)328 array2[i + 1] = array1[i];329 HeapSort(array2, 10);330 printf("堆排序:\n");331 for(i = 0; i < 10; ++i)332 printf("%d ", array2[i + 1]);333 printf("\n");334 335 memcpy(array2, array1, sizeof(array1));336 MergeSort(array2, 10);337 printf("归并排序:\n");338 PrintArr(array2, 10);339 340 memcpy(array2, array1, sizeof(array1));341 RadixSort(array2, 10);342 printf("基数排序:\n");343 PrintArr(array2, 10);344 345 return 0;346 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。