赞
踩
冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
算法步骤:以升序排列为例
①比较第一个数与第二个数,若为逆序a[0]>a[1],则交换;然后比较第二个数与第三个数;依此类推,直至第n-1个数和第n个数比较为止——第一趟冒泡排序,最终,最大的数被安置在最后一个元素位置上。
②对前n-1个数进行第二趟冒泡排序,最终,使次大的数被安置在第n-1个元素位置。
③重复上述过程,共经过n-1次冒泡排序后,排序结束。
/*=============================================== * 文件名称:bubble.c * 创 建 者: xm * 创建日期:2022年08月14日 * 描 述: ================================================*/ #include <stdio.h> void bubble_sort(int arr[],int len) { int i,j,tmp; for(i=0;i<len;i++) { for(j=0;j<len-1-i;j++) { if(arr[j]>arr[j+1])//当前数大于后一个数则交换 { tmp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=tmp; } } } } int main(int argc, char *argv[]) { int arr[]={10,5,23,12,7,1,3,30,40,5}; int i,len; len=(int)sizeof(arr)/sizeof(arr[0]); printf("测试数据\n"); for(i=0;i<len;i++) { printf("%d ",arr[i]); } bubble_sort(arr,len); printf("\n排序后\n"); for(i=0;i<len;i++) { printf("%d ",arr[i]); } return 0; }
每一趟选出较大或较小的值,将它与排好序后位于位置的值进行交换。每一趟在n-i+1个元素中选取关键字最小(最大)的元素作为有序序列中第i个记录。
算法步骤:(以升序排列为例)
①首先通过n-1次比较,从n个数中找出最小的,将它与第一个数交换——第一次选择排序,结果最小的数被安置在第一个元素位置上。
②再通过n-2次比较,从剩余的n-1个数中找出关键字次小的记录,将它与第二个数交换——第二次选择排序。
③重复上述过程,共经过n-1次排序后,排序结束。
/*=============================================== * 文件名称:select_sort.c * 创 建 者: xm * 创建日期:2022年08月14日 * 描 述: ================================================*/ #include <stdio.h> void select_sort(int arr[],int len) { int i,j,t,tmp; for(i=0;i<len-1;i++) { t=i; for(j=i+1;j<len;j++)//得到最小数的下标 { if(arr[j]<arr[t]) { t=j; } } //当前循环的下标数据和最小数的下标数据交换 tmp=arr[t]; arr[t]=arr[i]; arr[i]=tmp; } } int main(int argc, char *argv[]) { int arr[]={10,5,23,12,7,1,3,30,40,5}; int i,len; len=(int)sizeof(arr)/sizeof(arr[0]); printf("测试数据\n"); for(i=0;i<len;i++) { printf("%d ",arr[i]); } select_sort(arr,len); printf("\n排序后\n"); for(i=0;i<len;i++) { printf("%d ",arr[i]); } return 0; }
插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
算法步骤:
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
/*=============================================== * 文件名称:insert_sort.c * 创 建 者: xm * 创建日期:2022年08月14日 * 描 述: ================================================*/ #include <stdio.h> void insert_sort(int arr[],int len) { int i,j,key; for(i=1;i<len;i++)//无序序列 { key=arr[i];//保存待插入元素 j=i-1; while((j>=0) && (arr[j]>key)) { arr[j+1]=arr[j]; j--; } arr[j+1]=key; } } int main(int argc, char *argv[]) { int arr[]={10,5,23,12,7,1,3,30,40,5}; int i,len; len=(int)sizeof(arr)/sizeof(arr[0]); printf("测试数据\n"); for(i=0;i<len;i++) { printf("%d ",arr[i]); } insert_sort(arr,len); printf("\n排序后\n"); for(i=0;i<len;i++) { printf("%d ",arr[i]); } return 0; }
冒泡排序一次只能消除一个逆序,快速排序中的一次交换可能消除多个逆序.
算法步骤:
①从数列中挑出一个元素,称为 “基准值”;
②重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
③递归地把小于基准值元素的子数列和大于基准值元素的子数列排序;
/*=============================================== * 文件名称:quick_sort.c * 创 建 者: xm * 创建日期:2022年08月14日 * 描 述: ================================================*/ #include <stdio.h> void quick_sort(int arr[],int left,int right) { int i=left,j=right; if(left>=right)return;//左指针大于等于右指针则结束 int mid=arr[left];//取基准点 while(i<j) { while((i<j) && (mid<=arr[j]))j--; arr[i]=arr[j]; while((i<j) && (mid>=arr[i]))i++; arr[j]=arr[i]; } arr[i]=mid; quick_sort(arr,left,i-1); quick_sort(arr,i+1,right); } int main(int argc, char *argv[]) { int arr[]={10,5,23,12,7,1,3,30,40,5}; int i,len; len=(int)sizeof(arr)/sizeof(arr[0]); printf("测试数据\n"); for(i=0;i<len;i++) { printf("%d ",arr[i]); } quick_sort(arr,0,len-1); printf("\n排序后\n"); for(i=0;i<len;i++) { printf("%d ",arr[i]); } return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。