首页 > 代码库 > 算法5--排序
算法5--排序
主要是一些常见的排序方法的实现
1 冒泡排序算法
排序算法的理论和实现比较简单；
对于冒泡排序算法的改进，一种比较好的方法是，每次中间排序之后，都进行排序状态检测，如果已经排好序，就退出排序过程，否则基于冒泡排序；
但是：对于数组排序状态的检测，我没有比较好的办法；如果个数比较少，还可以容易得出，但是数组元素个数比较多的时候，该如何做？
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 #define SIZE 10 6 7 int sortjudge(int *a,int len) 8 { 9 if (/* condition */)10 {11 /* code */12 }13 }14 void bubblesort(int *a,int len)15 {16 int temp;17 for (int i = 0; i < len-1; i++)18 {19 for (int j = len-1; j>i; j--)20 {21 if (a[j-1]>a[j])22 {23 temp=a[j-1];24 a[j-1]=a[j];25 a[j]=temp;26 }27 }28 printf("the %d down sort answer :", i+1);29 for (int k = 0; k < len; k++)30 {31 printf("%d ", a[k]);32 }33 printf("\n");34 }35 36 }37 38 39 int main()40 {41 int array[SIZE];42 srand(time(NULL));43 for (int i = 0; i < SIZE; i++)44 {45 array[i]=rand()/1000;46 }47 printf("before sort:\n");48 for (int j = 0; j < SIZE; j++)49 {50 printf("%d ",array[j]);51 }52 printf("\n");53 bubblesort(array,SIZE);54 printf("after sort:\n");55 for (int k = 0; k < SIZE; k++)56 {57 printf("%d ",array[k]);58 }59 printf("\n");60 return 0;61 }
2 选择排序
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 #define SIZE 10 6 7 void selectionsort(int *a , int len) 8 { 9 int temp;10 for (int i=0; i<len-1; i++)11 {12 int k=i;13 for (int j=i+1; j<len; j++)14 {15 if (a[j]<a[k])16 {17 k=j;18 }19 }20 if (k!=i)21 {22 temp=a[i];23 a[i]=a[k];24 a[k]=temp;25 }26 printf("the %d sorted answer is :" , i+1);27 for (int m = 0; m<len; m++)28 {29 printf("%d",a[m]);30 }31 printf("\n");32 }33 }34 35 36 int main()37 {38 int array[SIZE];39 srand(time(NULL));40 for (int i = 0; i < SIZE; i++)41 {42 array[i]=rand()/1000;43 }44 printf("before sort:\n");45 for (int j = 0; j < SIZE; j++)46 {47 printf("%d ",array[j]);48 }49 printf("\n");50 selectionsort(array,SIZE);51 printf("after sort:\n");52 for (int k = 0; k < SIZE; k++)53 {54 printf("%d ",array[k]);55 }56 printf("\n");57 return 0;58 }
3 插入排序
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 #define SIZE 10 6 7 void insertionsort(int *a,int len) 8 { 9 for (int i = 1; i < len; i++)10 {11 int t=a[i];12 int j=i-1;13 while(j>=0&&t<a[j])14 {15 a[j+1]=a[j];16 j--;17 }18 a[j+1]=t;19 printf("the %d step sort answer:", i);20 for (int k = 0; k < len; k++)21 {22 printf("%d ",a[k] );23 }24 printf("\n");25 }26 }27 28 int main()29 {30 int array[SIZE];31 32 srand(time(NULL));33 34 for (int i = 0; i < SIZE; i++)35 {36 array[i]=rand()/1000+100;37 }38 printf("before sort:\n");39 for (int j = 0; j < SIZE; j++)40 {41 printf("%d ",array[j]);42 }43 printf("\n");44 insertionsort(array,SIZE);45 printf("after sort:\n");46 for (int k = 0; k < SIZE; k++)47 {48 printf("%d ",array[k]);49 }50 printf("\n");51 return 0;52 }
4 shell排序
#include <stdio.h>#include <stdlib.h>#include <time.h>#define SIZE 10void shellsort(int *a,int len){ int times=0; for (int i = len/2; i >=1; i/=2) { for (int j = i; j < len; j++) { int temp=a[j]; int k=j-i; while(k>=0&&temp<a[k]) { a[k+i]=a[k]; k-=i; } a[k+i]=temp; } times=times+1; printf("the %d steps answer:", times); for (int h = 0; h < len; h++) { printf("%d ",a[h]); } printf("\n"); }}int main(){ int array[SIZE]; srand(time(NULL)); for (int i = 0; i < SIZE; i++) { array[i]=rand()/1000+100; } printf("before sort:\n"); for (int j = 0; j < SIZE; j++) { printf("%d ",array[j]); } printf("\n"); shellsort(array,SIZE); printf("after sort:\n"); for (int k = 0; k < SIZE; k++) { printf("%d ",array[k]); } printf("\n"); return 0;}
5 快速排序
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 #define SIZE 10 6 7 void exchange(int m,int n) 8 { 9 int temp=0;10 temp=m;11 m=n;12 n=temp;13 }14 15 int partion(int *a,int left,int right)16 {17 int x=a[right];18 int i=left;19 for (int j=left ; j <= right; j++)20 {21 if (a[j]<=x)22 {23 i=i+1;24 exchange(a[i],a[j]);25 }26 }27 exchange(a[i+1],a[right]);28 printf("the partion postion is \n", i);29 return i;30 }31 32 33 void quicksort(int *a,int left,int right)34 {35 if (left<right)36 {37 int q=partion(a,left,right);38 quicksort(a,left,q-1);39 quicksort(a,q+1,right);40 }41 }42 43 int main()44 {45 int array[SIZE];46 47 srand(time(NULL));48 49 for (int i = 0; i < SIZE; i++)50 {51 array[i]=rand()/1000+100;52 }53 printf("before sort:\n");54 for (int j = 0; j < SIZE; j++)55 {56 printf("%d ",array[j]);57 }58 printf("\n");59 60 quicksort(array,0,SIZE-1);61 62 printf("after sort:\n");63 for (int k = 0; k < SIZE; k++)64 {65 printf("%d ",array[k]);66 }67 printf("\n");68 return 0;69 }
6 堆排序
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 #define SIZE 10 6 7 int left(int i){return i*2;} 8 9 int right(int i){return i*2+1;}10 11 int parent(int i){return i/2;}12 13 void swap(int a,int b)14 {15 int tem=a;16 a=b;17 b=tem;18 }19 20 void max_heapify(int *a,int i)21 {22 int length=SIZE;23 int l=left(i);24 int r=right(i);25 int largest;26 if (l<=SIZE&&a[l]>a[i])27 {28 largest=l;29 }30 else31 largest=i;32 if (r<=length&&a[r]>a[i])33 {34 largest=r;35 }36 if (largest!=i)37 {38 swap(a[largest],a[i]);39 max_heapify(a,largest);40 }41 }42 43 void build_max_heap(int *a)44 {45 int length=SIZE;46 for (int i = length/2; i >0; i--)47 {48 max_heapify(a,i);49 }50 }51 52 53 void heapsort(int *a)54 {55 int length=SIZE;56 build_max_heap(a);57 58 for (int i = length; i >=2; i--)59 {60 printf("%d ", a[0]);61 swap(a[0],a[i]);62 length=length-1;63 max_heapify(a,1);64 }65 }66 67 68 int main()69 {70 int array[SIZE];71 int length=10;72 srand(time(NULL));73 74 for (int i = 0; i < SIZE; i++)75 {76 array[i]=rand()/1000+100;77 }78 printf("before sort:\n");79 for (int j = 0; j < SIZE; j++)80 {81 printf("%d ",array[j]);82 }83 printf("\n");84 85 heapsort(array);86 87 printf("after sort:\n");88 for (int k = 0; k < SIZE; k++)89 {90 printf("%d ",array[k]);91 }92 printf("\n");93 return 0;94 }
7 归并排序
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 #define SIZE 10 6 #define big NULL 7 /* 8 void merge(int *a,int p,int q,int r) 9 { 10 int len1=q-p+1; 11 int len2=r-q+1; 12 int len3=len1+1; 13 int len4=len2+1; 14 int l[len3]={}; 15 int r[len4]={}; 16 for (int i = 0; i < len1; i++) 17 { 18 l[i]=a[p+i-1]; 19 } 20 for (int j = 0; j < len2; j++) 21 { 22 r[j]=a[q+j]; 23 } 24 int l[len3]=big; 25 int r[len4]=big; 26 int i=1; 27 int j=1; 28 for (int k = p; k < r; k++) 29 { 30 if (l[i]<=r[j]&&l[i]!=big&&r[j]!=big) 31 { 32 a[k]=l[i]; 33 i++; 34 } 35 else 36 { 37 a[k]=r[j]; 38 j++; 39 } 40 } 41 } 42 */ 43 void merge2(int *a,int p,int q,int r) 44 { 45 int len1=q-p+1; 46 int len2=r-q+1; 47 int len3=r-p+1; 48 int left[len1]; 49 int right[len2]; 50 for (int i = 0; i < len1; i++) 51 { 52 left[i]=a[p+i-1]; 53 } 54 for (int j = 0; j < len2; j++) 55 { 56 right[j]=a[q+j]; 57 } 58 while(len1>=0&&len2>=0) 59 { 60 a[len3--]=left[len1]>=right[len2] ? left[len1] : right[len2]; 61 } 62 while(len1>0) 63 { 64 a[len3--]=left[len1--]; 65 } 66 while(len2>0) 67 { 68 a[len3--]=right[len2--]; 69 } 70 71 } 72 73 74 void mergesort(int *a,int p,int r) 75 { 76 if (p<r) 77 { 78 int q=(p+r)/2; 79 mergesort(a,p,q); 80 mergesort(a,q+1,r); 81 merge2(a,p,q,r); 82 } 83 } 84 85 int main() 86 { 87 int array[SIZE]; 88 89 srand(time(NULL)); 90 91 for (int i = 0; i < SIZE; i++) 92 { 93 array[i]=rand()/1000+100; 94 } 95 printf("before sort:\n"); 96 for (int j = 0; j < SIZE; j++) 97 { 98 printf("%d ",array[j]); 99 }100 printf("\n");101 102 mergesort(array,0,SIZE-1);103 104 printf("after sort:\n");105 for (int k = 0; k < SIZE; k++)106 {107 printf("%d ",array[k]);108 }109 printf("\n");110 return 0;111 }
算法5--排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。