锐客网

  1. 首页 > it技术 > >

C/C++|C/C++ 常用排序算法整理汇总分享

(伪)冒泡排序算法: 相邻的两个元素之间,如果反序则交换数值,直到没有反序的记录为止.

#include 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 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 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 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]; // 把小的元素放入tempfor (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; }

(分组)希尔排序: 【C/C++|C/C++ 常用排序算法整理汇总分享】在直接插入排序进行升级,把记录进行分组,分割成若干个子序列,把每一个子序列分别进行插入排序.
#include 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]; // 把小的元素放入tempfor (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 #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++]; elsetemporary[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); // 递归拆解数组1MergeSort(list2, list2_size); // 递归拆解数组2merging(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 #include 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 #include // 定义链表节点类型struct LinkNode{ int data; struct LinkNode *next; }; struct LinkNode *init_link(){// 创建一个头结点,头结点不需要添加任何数据 struct LinkNode *header = malloc(sizeof(struct LinkNode)); header->data = https://www.it610.com/article/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 = https://www.it610.com/article/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 =https://www.it610.com/article/= oldval)break; pPrev = Current; Current = Current->next; } // 如果值不存在则默认插入到尾部 //if (Current == NULL) // return; // 创建新节点 struct LinkNode *newnode = malloc(sizeof(struct LinkNode)); newnode->data = https://www.it610.com/article/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 =https://www.it610.com/article/= 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 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 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 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]
技巧04：归并排序
#include 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 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]
技巧06:快速排序(冒泡排序的改进） 主要的算法思想是在带排序的n个数据中取第一个数据作为基准值，将所有的记录分为3组，使得
第一组中各数据值均小于或等于基准值，第二组便是做基准值的数据，第三组中个数举值均大于
或等于基准值。这便实现了第一趟分隔，然后再对第一组和第三组分别重复上述方法。
#include void qusort(int s[],int start,int end){//自定义快排函数int i,j; i=start; j=end; s[0]=s[start]; //设置基准值while(i 技巧07：顺序查找
#include void search(int key,int a[],int n){int i,count = 0,count1=0; for (i=0; i
技巧08：二分查找
#include void binary_search(int key,int a[],int n){int low,high,mid,count=0,count1=0; low = 0; high = n-1; while(low
技巧09：分块查找
#include 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)//大于分得的块数，则返回0return 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); elseprintf ("no found!\n"); return 0; }

技巧10:哈系查找（没能很好的运行）
#include #include #define Max 11#define N 8int 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; i0&&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; }

文章出处：https://www.cnblogs.com/lyshark
以上就是C/C++ 常用排序算法整理汇总分享的详细内容，更多关于C/C++ 排序算法的资料请关注脚本之家其它相关文章！

    推荐阅读


    上一篇：Spring|Spring boot基于JPA访问MySQL数据库的实现

    下一篇：如何自定义feign调用实现hystrix超时、异常熔断