C/C++ 排序算法 C/C++ 常用排序算法整理汇总分享
lyshark 人气:0想了解C/C++ 常用排序算法整理汇总讲解的相关内容吗,lyshark在本文为您仔细讲解C/C++ 排序算法的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:c,排序算法,c++,排序算法,下面大家一起来学习吧。
(伪)冒泡排序算法:
相邻的两个元素之间,如果反序则交换数值,直到没有反序的记录为止.
#include <stdio.h> void BubbleSort(int Array[], int ArraySize) { int x, y, temporary; for (x = 0; x < ArraySize - 1; x++) { for (y = x + 1; y < ArraySize; y++) { if (Array[x] > Array[y]) { temporary = Array[y]; Array[y] = Array[x]; Array[x] = temporary; } } } } int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 }; BubbleSort(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } system("pause"); return 0; }
(真)冒泡排序算法:
正宗的冒泡排序就是从下往上两两比较,所以看上去就像是泡泡向上冒一样.
#include <stdio.h> void BubbleSort(int Array[], int ArraySize) { int x, y, temporary; for (x = 0; x < ArraySize - 1; x++) { for (y = ArraySize - 1; y > x; y--) { if (Array[y-1] > Array[y]) { temporary = Array[y-1]; Array[y-1] = Array[y]; Array[y] = temporary; } } } } int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 }; BubbleSort(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } system("pause"); return 0; }
选择排序算法:
该算法通过Array-x次关键字比较,从Array-x+1个记录中选出关键字最小的记录,并和第x个记录交换.
#include <stdio.h> void SelectSort(int Array[], int ArraySize) { int x, y, minimum, temporary; for (x = 0; x < ArraySize - 1; x++) { minimum = x; // 假设x是最小的数 for (y = x + 1; y < ArraySize; y++) { // 将假设中的最小值进行比对 if (Array[y] < Array[minimum]) minimum = y; } if (minimum != x) { // 循环结束后进行交换 temporary = Array[minimum]; Array[minimum] = Array[x]; Array[x] = temporary; } } } int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 }; SelectSort(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } system("pause"); return 0; }
直接插入排序:
该算法将一个记录插入到已经排好序的有序表中,从而得到一个新的,记录数增加1的有序表.
#include <stdio.h> void InsertSort(int Array[], int ArraySize) { int x, y, temporary; for (x = 1; x < ArraySize; x++) { if (Array[x] < Array[x - 1]) { temporary = Array[x]; // 把小的元素放入temp for (y = x - 1; Array[y] > temporary; y--) { Array[y + 1] = Array[y]; } Array[y + 1] = temporary; } } } int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 }; InsertSort(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } system("pause"); return 0; }
(分组)希尔排序:
在直接插入排序进行升级,把记录进行分组,分割成若干个子序列,把每一个子序列分别进行插入排序.
#include <stdio.h> void ShellSort(int Array[], int ArraySize) { int x, y, temporary; int interval = ArraySize; // 设置排序间隔 do { interval = interval / 3 + 1; for (x = interval; x < ArraySize; x++) { if (Array[x] < Array[x - interval]) { temporary = Array[x]; // 把小的元素放入temp for (y = x - interval; Array[y] > temporary; y -= interval) { Array[y + interval] = Array[y]; } Array[y + interval] = temporary; } } } while (interval > 1); } int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 }; ShellSort(a, 10); for (int i = 0; i < 10; i++) { printf("%d ", a[i]); } system("pause"); return 0; }
归并排序算法:
将数组拆分成两部分,然后将每部分再次拆成两部分,直到无法拆了为止,然后两两比较,最后在归并到一起.
#include <stdio.h> #define MAXSIZE 10 // 实现归并,并把最后的结果存放到list1里面 void merging(int *list1,int list1_size,int *list2,int list2_size) { int list1_sub = 0, list2_sub = 0, k = 0; int temporary[MAXSIZE]; while (list1_sub < list1_size && list2_sub < list2_size) { if (list1[list1_sub] < list2[list2_sub]) temporary[k++] = list1[list1_sub++]; else temporary[k++] = list2[list2_sub++]; } while (list1_sub < list1_size) temporary[k++] = list1[list1_sub++]; while (list2_sub < list2_size) temporary[k++] = list2[list2_sub++]; // 最后将归并后的结果存入到list1变量中 for (int m = 0; m < (list1_size + list2_size); m++) list1[m] = temporary[m]; } // 拆分数组,拆分以后传入merging函数实现归并 void MergeSort(int Array[], int ArraySize) { // 如果大于1则终止拆解数组 if (ArraySize > 1) { int *list1 = Array; // 左边部分 int list1_size = ArraySize / 2; // 左边的尺寸,每次是n/2一半 int *list2 = Array + ArraySize / 2; // 右半部分,就是左半部分的地址加上右半部分的尺寸 int list2_size = ArraySize - list1_size; // 右半部分尺寸 MergeSort(list1, list1_size); // 递归拆解数组1 MergeSort(list2, list2_size); // 递归拆解数组2 merging(list1, list1_size, list2, list2_size); // 归并 } } int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 }; MergeSort(a, 10); for (int i = 0; i < 10; i++) printf("%d ", a[i]); system("pause"); return 0; }
迭代归并排序:
代码指针存在问题.
#include <stdio.h> #include <stdlib.h> void MergeSort(int k[], int n) { int i, left_min, left_max, right_min, right_max; // 申请临时空间 int *temp = (int *)malloc(n * sizeof(int)); for (i = 1; i < n; i *= 2) // i => 步长,每次对比两个元素 { for (left_min = 0; left_min < n - i; left_min = right_max) { right_min = left_max = left_min + i; right_max = left_max + i; if (right_max > n) // 有时数组无法整除,我们来处理一下 { right_max = n; } int next = 0; while (left_min < left_max && right_min < right_max) { if (k[left_min] < k[right_min]) { temp[next++] = k[left_min]; } else { temp[next++] = k[right_min]; } } while (left_min < left_max) { k[--right_min] = k[--left_min]; } while (next >0) { k[--right_min] = temp[--next]; } } } } int main(int argc, char* argv[]) { int a[10] = { 2, 5, 6, 8, 2, 3, 9, 1, 8, 0 }; MergeSort(a, 10); for (int i = 0; i < 10; i++) printf("%d ", a[i]); system("pause"); return 0; }
迭代归并排序2:
代码指针存在问题.
#include <stdio.h> #include <stdlib.h> // 定义链表节点类型 struct LinkNode { int data; struct LinkNode *next; }; struct LinkNode *init_link() { // 创建一个头结点,头结点不需要添加任何数据 struct LinkNode *header = malloc(sizeof(struct LinkNode)); header->data = 0; header->next = NULL; struct LinkNode *p_end = header; // 创建一个尾指针 int val = -1; while (1) { scanf("%d", &val); // 输入插入的数据 if (val == -1) // 如果输入-1说明输入结束了 break; // 先创建新节点 struct LinkNode *newnode = malloc(sizeof(struct LinkNode)); newnode->data = val; newnode->next = NULL; // 将节点插入到链表中 p_end->next = newnode; // 更新尾部指针指向 p_end = newnode; } return header; } // 遍历链表 int foreach_link(struct LinkNode *header) { if (NULL == header || header->next == NULL) return 0; while (header->next != NULL) { printf("%d \n", header->data); header = header->next; } return 1; } // 在header节点中oldval插入数据 void insert_link(struct LinkNode *header,int oldval,int newval) { struct LinkNode *pPrev = header; struct LinkNode *Current = pPrev->next; if (NULL == header) return; while (Current != NULL) { if (Current->data == oldval) break; pPrev = Current; Current = Current->next; } // 如果值不存在则默认插入到尾部 //if (Current == NULL) // return; // 创建新节点 struct LinkNode *newnode = malloc(sizeof(struct LinkNode)); newnode->data = newval; newnode->next = NULL; // 新节点插入到链表中 newnode->next = Current; pPrev->next = newnode; } // 清空链表 void clear_link(struct LinkNode *header) { // 辅助指针 struct LinkNode *Current = header->next; while (Current != NULL) { // 保存下一个节点地址 struct LinkNode *pNext = Current->next; printf("清空数据: %d \n", Current->data); free(Current); Current = pNext; } header->next = NULL; } // 删除值为val的节点 int remove_link(struct LinkNode *header, int delValue) { if (NULL == header) return; // 设置两个指针,指向头结点和尾结点 struct LinkNode *pPrev = header; struct LinkNode *Current = pPrev->next; while (Current != NULL) { if (Current->data == delValue) { // 删除节点的过程 pPrev->next = Current->next; free(Current); Current = NULL; } } // 移动两个辅助指针 pPrev = Current; Current = Current->next; } // 销毁链表 void destroy_link(struct LinkNode *header) { if (NULL == header) return; struct LinkNode *Curent = header; while (Curent != NULL) { // 先来保存一下下一个节点地址 struct LinkNode *pNext = Curent->next; free(Curent); // 指针向后移动 Curent = pNext; } } // 反响排序 void reverse_link(struct LinkNode *header) { if (NULL == header) return; struct LinkNode *pPrev = NULL; struct LinkNode *Current = header->next; struct LinkNode * pNext = NULL; while (Current != NULL) { pNext = Current->next; Current->next = pPrev; pPrev = Current; Current = pNext; } header->next = pPrev; } int main(int argc, char* argv[]) { struct LinkNode * header = init_link(); reverse_link(header); foreach_link(header); clear_link(header); system("pause"); return 0; }
以下代码来源于网络
技巧01:冒泡排序
#include <stdio.h> int main(int argc, char *argv[]) { int i,j,t,a[11]; printf ("please input 10 numbers:\n"); for(i=1;i<11;i++) scanf("%d",&a[i]); for(i=1;i<10;i++) //i代表比较的趟数 for(j=1;j<11-i;j++) //j代表每趟两两比较的次数 if (a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } printf ("the sorted numbers:\n"); for(i=1;i<=10;i++) printf ("%5d",a[i]); return 0; }
技巧02:选择排序
#include <stdio.h> int main(int argc, char *argv[]) { int i,j,t,a[11]; printf ("please input 10 numbers:\n"); for(i=1;i<11;i++) scanf("%d",&a[i]); for(i=1;i<=9;i++) for(j=i+1;j<=10;j++) if (a[i]>a[j]) { t=a[i]; a[i]=a[j]; a[j]=t; } printf ("the sorted numbers:\n"); for(i=1;i<=10;i++) printf ("%5d",a[i]); return 0; }
技巧03:直接插入排序
#include <stdio.h> void insort(int s[],int n) { //数组的下标从2开始,0做监视哨,1 一个数据无可比性 int i,j; for (i=2; i<=n; i++) { s[0]=s[i]; j=i-1; while(s[0]<s[j]) { s[j+1]=s[j]; j--; } s[j+1]=s[0]; } } int main(int argc, char *argv[]) { int a[11],i; printf ("please input number:\n"); for(i=1;i<=10;i++) scanf("%d",&a[i]); printf ("the original order:\n"); for(i=1;i<11;i++) printf ("%5d",a[i]); insort(a,10); printf ("\nthe sorted numbers:\n"); for(i=1;i<11;i++) printf ("%5d",a[i]); return 0; }
技巧04:归并排序
#include <stdio.h> void merge(int r[],int s[],int x1,int x2,int x3) { //实现一次归并排序函数 int i,j,k; i=x1; //第一部分的开始位置 j=x2+1; //第二部分的开始位置 k=x1; while((i<=x2)&&(j<=x3)) //当i和j都在两个要合并的部分中 if (r[i]<=r[j]) //筛选两部分中较小的元素放到数组s中 { s[k]=r[j]; i++; k++; } else { s[k]=r[j]; j++; k++; } while(i<=x2) //将x1,x2范围内的未比较的数顺次加到数组r中 s[k++]=r[i++]; while(j<=x3) //将x2,x3范围内的未比较的数顺次加到数组r中 s[k++]=r[j++]; } void merge_sort(int r[],int s[],int m,int n) { int p; int t[20]; if(m==n) s[m]=r[m]; else { p=(m+n)/2; merge_sort(r,t,m,p); //递归调用merge_sort函数将r[m],r[p]归并成有序的t[m],t[p] merge_sort(r,t,p+1,n); //递归调用merge_sort函数将r[p+1],r[n]归并成有序的t[p+1],t[n] merge(t,s,m,p,n); //调有函数将前两部分归并到s[m],s[n] } } main() { int a[11]; int i; printf ("please input 10 numbers:\n"); for(i=1;i<=10;i++) //从键盘中输入10个数 scanf("%d",&a[i]); merge_sort(a,a,1,10); //调用merge_sort函数进行归并排序 printf ("the sorted numbers:\n"); for(i=1;i<=10;i++) printf ("%5d",a[i]); //将排序后的结构输出 return 0; }
技巧05:希尔排序(插入排序的改进)
#include <stdio.h> void shsort(int s[],int n) { int i,j,d; d=n/2; //确定固定增量值 while(d>=1) { for (i=d+1; i<=n; i++) //数组下标从d+1开始进行直接插入排序 { s[0]=s[i]; //设置监视哨 j=i-d; //确定要进行比较的元素的最右边位置 while((j>0)&&(s[0]<s[j])) { s[j+d]=s[j]; //数据右移 j=j-d; //向左移d个位置 } s[j+d]=s[0]; //在确定的位置插入s[i] } d=d/2; //增量变为原来的一半 } } int main(int argc, char *argv[]) { int a[11],i; printf ("please input numbers:\n"); for(i=1;i<=10;i++) scanf("%d",&a[i]); shsort(a,10); printf ("the sorted numbers:\n"); for(i=1;i<=10;i++) printf ("%5d",a[i]); return 0; }
技巧06:快速排序(冒泡排序的改进)
主要的算法思想是在带排序的n个数据中取第一个数据作为基准值,将所有的记录分为3组,使得
第一组中各数据值均小于或等于基准值,第二组便是做基准值的数据,第三组中个数举值均大于
或等于基准值。这便实现了第一趟分隔,然后再对第一组和第三组分别重复上述方法。
#include <stdio.h> void qusort(int s[],int start,int end) { //自定义快排函数 int i,j; i=start; j=end; s[0]=s[start]; //设置基准值 while(i<j) { while(i<j&&s[0]<s[j]) j--; //位置左移 if (i<j) { s[i]=s[j]; //将s[j]放到s[i]的位置上 i++; //位置右移 } while(i<j&&s[i]<=s[0]) i++; //位置右移 if (i<j) { s[j]=s[i]; //将大于基准值的s[j]放到s[i]位置 j--; //位置右移 } } s[i]=s[0]; //将基准值放入指定位置 if(start<i) qusort(s,start,j-1); //对分隔出的部分递归调用函数qusort() if(i<end) qusort(s,j+1,end); } int main(int argc, char *argv[]) { int a[11],i; printf ("please input numbers:\n"); for(i=1;i<=10;i++) scanf("%d",&a[i]); qusort(a,1,10); printf ("the sorted numbers:\n"); for(i=1;i<=10;i++) printf ("%5d",a[i]); return 0; }
技巧07:顺序查找
#include <stdio.h> void search(int key,int a[],int n) { int i,count = 0,count1=0; for (i=0; i<n; i++) { count++; if (a[i]==key) { printf ("serch %d times a[%d]=%d\n",count,i,key); count1++; } } if(count1==0) printf ("no found!\n"); } int main(int argc, char *argv[]) { int n,key,a[100],i; printf ("please input the length of array:\n"); scanf("%d",&n); printf ("please input element:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); printf ("please input the number which do you want to search:\n"); scanf("%d",&key); search(key,a,n); return 0; }
技巧08:二分查找
#include <stdio.h> void binary_search(int key,int a[],int n) { int low,high,mid,count=0,count1=0; low = 0; high = n-1; while(low<high) { count++; //记录查找次数 mid=(low+high)/2; //求出中间位置 if(key<a[mid]) //当key小于中间值 high=mid-1; //确定左子表范围 else if(key>a[mid]) //当key大于中间值 low=mid+1; //确定右子表范围 else if(key==a[mid]) //当key等于中间值证明查找成功 { printf ("success!\nsearch %d times! a[%d]=%d\n",count,mid,key); count1++; //count1记录查找成功次数 break; } } if(count1==0) printf ("no found!\n"); } int main(int argc, char *argv[]) { int i,key,a[100],n; printf ("please input the length of array:\n"); scanf("%d",&n); printf ("please input the element:\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); printf ("please input the number which do you want to serch:\n"); scanf("%d",&key); binary_search(key,a,n); return 0; }
技巧09:分块查找
#include <stdio.h> struct index //定义块的结构 { int key; int start; int end; }index_table[4]; //定义结构体数组 int block_search(int key,int a[]) //自定义实现分块查找 { int i,j; i=1; while(i<=3&&key>index_table[i].key) //确定在哪个块中 i++; if(i>3) //大于分得的块数,则返回0 return 0; j=index_table[i].start; //j等于块范围的起始值 while(j<=index_table[i].end&&a[j]!=key) //在确定的块内进行查找 j++; if(j>index_table[i].end) //如果大于块范围的结束值,则说明没有要查找的数 j=0; return j; } int main(int argc, char *argv[]) { int i,j=0,k,key,a[16]; printf ("please input the number:\n"); for(i=1;i<16;i++) scanf("%d",&a[i]); for (i=1; i<=3; i++) { index_table[i].start=j+1; //确定每个范围的起始行 j=j+1; index_table[i].end=j+4; //确定每个块范围的结束值 j=j+4; index_table[i].key=a[j]; //确定每个块范围中元素的最大值 } printf ("please inpu the number whick do you want to search:\n"); scanf("%d",&key); k=block_search(key,a); if(k!=0) printf ("success ! the position is :%d\n",k); else printf ("no found!\n"); return 0; }
技巧10:哈系查找(没能很好的运行)
#include <stdio.h> #include <time.h> #define Max 11 #define N 8 int hashtable[Max]; int func(int value) { return value % Max; //哈希函数 } int search(int key) //自定义函数实现哈希函数 { int pos,t; pos=func(key); //哈希函数确定出的位置 t=pos; //t存放确定出的位置 while(hashtable[t]!=key && hashtable[t]!=-1) //如果该位置上不等与要查找的关键字且不为空 { t=(t+1)%Max; //利用线性探测求出下一个位置 if(pos==t) //如果经多次探测又回到原来用哈希函数求出的位置则 //说明要查找的数不存在 return -1; } if(hashtable[t]==-1) //如果探测的位置是-1则说明要查找的数不存在 return 0; else return t; } void creathash(int key) //自定义函数创建哈系表 { int pos,t; pos = func(key); //哈希函数确定元素的位置 t = pos; while(hashtable[t]!=-1) //如果该位置有元素存在则在则进行线性探测再散列 { t=(t+1)%Max; if(pos==t) //如果冲突处理后确定的位置与原位置相同则说明哈系表已满 { printf ("hash table is full\n"); return ; } } hashtable[t]=key; //将元素放入确定的位置 } int main(int argc, char *argv[]) { int flag[50]; int i,j,t; for(i=0;i<Max;i++) hashtable[i]=-1; //哈希表中初始化位置全置-1 for(i=0;i<50;i++) flag[i]=0; //50以内所有数未产生时均标志为0 rand((unsigned long)time(0)); //利用系统时间做种子产生随机数 i=0; while(i != N) { t=rand()%50; //产生一个50以内的随机数附给t if (flag[t]=0) //查看t是否产生过 { creathash(t); //调用函数创建哈希表 printf ("%2d:\n",t); //将该元素输出 for (j=0; j < Max; j++) printf ("(%2d) \n",hashtable[j]); //输出哈希表的内容 printf ("\n"); flag[t]=1; //将产生的这个数标志为1 i++; //i自加 } } printf ("please input number whick do you want to search:\n"); scanf("%d",&t); //输入要查找的元素 if (t>0&&t<50) { i=search(t); //调用search进行哈系查找 if(i != -1) printf ("success! the position is:%d\n",i); //若找到该元素则输出其位置 else printf ("sorry,no found!\n"); //未找到输出提示信息 } else printf ("input error!\n"); return 0; }
加载全部内容