1.桶排序
//对0～10范围内的5个数桶升序 int a[11],t＝0; for (int i=0; i <=10; i++) { a[i]=0;//设置11个空桶，用于记录用户输入的数;n个范围 } for (int i= 0; i< 5; i++) { scanf("%d",&t); a[t]+=1;//将输入的数放进桶中;m个数 } for (int i = 0;i<=10; i++) {//对11个桶进行判断；n个范围 for (int j = 1; a[i]>=j; j++) { //装入桶多少次，就打印多少次；m个数 printf("%d ",i);//得到几号的桶 } } printf(" 时间复杂度为o(n+m+n+m) 即o(n+m)这是一个非常快的排序");
2.冒泡排序
对n个数排序，相邻两数比较，比较n-1趟，每趟归位一个数，每一趟减少i 次比较。
//使用冒泡对10个数升序？ //每一趟确定将1个数归位，对n个数排序只需要进行n－1趟即可完成对n个数归位 int t=0; int n=10; int a[10]; for (int i = 0; i < n; i++) { scanf("%d",&a[i]); } for (int i = 0; i < n-1; i++) {//n-1趟 for (int j=0; j < n-i-1; j++) {//每一趟减少i 次比较 if (a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for (int i =0; i < n; i++) { printf("%d ",a[i]); } //printf(" 时间复杂度为o(n*n) 这是一个非常耗时的排序");
3.快速排序
情况：下标i、j不相等，二分法；下标i、j相等，交换基准。
#include <stdio.h> int a[10]; void quicksort(int left,int right); void quicksort(int left,int right) { if (left>right) {//结束条件 return; } int i=left,j=right; int t,basic; basic = a[left];//定基准 while (i!=j) { while (a[j]>=basic&&i<j) { j--;//下标要先从右往左找 } while (a[i]<=basic&&i<j) { i++;//下标再从左往右找 } //找出2数下标后，交换2数 if (i<j) { t=a[i]; a[i]=a[j]; a[j]=t; } } //i、j相遇，基准归位 a[left]=a[i]; a[i]=basic; quicksort(left, i-1); //继续处理左边，递归过程，当传入为0和－1时结束 quicksort(i+1, right);//继续处理右边，递归过程 } int main(int argc, const char * argv[]) { //使用快速排序对10个数升序？ //对第一个数作基准，设置右哨兵和左哨兵，往中间靠，右哨兵找少于基准的数，左哨兵找大于基准的数，满足后交换两值 //右左哨兵相遇时，基准与相遇处的值交换 int n = 10; for (int i= 0; i < n; i++) { scanf("%d",&a[i]); } quicksort(0,n-1);//传入左右下标 for (int i = 0; i < n; i++) { printf("%d ",a[i]); } printf(" 时间复杂度为o(n*logn) 平均耗时比冒泡排序短"); return 0; }
4.归并排序（分治思想）
int b[8]; int a[8] = {10,4,6,3,8,2,5,7}; [self mergeSort:a tempArr:b startIndex:0 endIndex:7]; for (int i = 0; i < 8; i++) { NSLog(@"%d ",a[i]); }
.
- (void)mergeSort:(int [])sourceArr tempArr:(int[])tempArr startIndex:(int)startIndex endIndex:(int)endIndex { if (startIndex < endIndex) { int midIndex = startIndex + (endIndex - startIndex)/2; [self mergeSort:sourceArr tempArr:tempArr startIndex:startIndex endIndex:midIndex]; [self mergeSort:sourceArr tempArr:tempArr startIndex:midIndex+1 endIndex:endIndex]; [self merge:sourceArr tempArr:tempArr startIndex:startIndex endIndex:endIndex midIndex:midIndex]; } }
.从小到大排序
- (void)merge:(int [])sourceArr tempArr:(int [])tempArr startIndex:(int)startIndex endIndex:(int)endIndex midIndex:(int)midIndex { int i = startIndex,j = midIndex + 1,k = startIndex; //2根手指比划，交换位置 while (i != midIndex+1 && j!= endIndex+1) { //小的放在前面 if (sourceArr[i] >= sourceArr[j]) { tempArr[k++] = sourceArr[j++]; } else { tempArr[k++] = sourceArr[i++]; } } //补刀，将最后的一个数入队 while (i != midIndex + 1) { tempArr[k++] = sourceArr[i++]; } while (j != endIndex + 1) { tempArr[k++] = sourceArr[j++]; } for (int i = 0; i < endIndex+1; i++) { printf("%d ",tempArr[i]); } printf(" "); //完成排序，入箱 for (int i = startIndex; i <= endIndex; i++) { sourceArr[i] = tempArr[i]; } }
其它
1.判断是否回文数
int ispal(int n); int main(int argc, const char * argv[]) { //3.回文数 for (int i = 0; i < 1000; i++) { if (ispal(i)) { printf("___%d ",i); } } } return 0; } //20302 //m = 2,m = 20,m = 203,m = 2030,m = 20302 //t = 2030,t = 203,t = 20,t = 2,t = 0 int ispal(int n) { int m = 0; int t = n;//求商，去尾位 while (t)//当商为0时结束 { //重新构造新数，新数=新数*10+余数 m = m * 10 + t % 10; t /= 10; } return m == n; }
2.枚举火柴题目
//手上有24根火柴，计算出a、b、c的值，a、b、c范围0～9，0～9对应用的火柴的根数{6,2,5,5,4,5,6,3,7,6}，实现等式a+b＝c int a,b,c,m,sum = 0; scanf("%d",&m);//读入火柴的个数 //因为1用的火柴根数最小，只用了2根火柴，再＋和＝用了4根火柴，剩下20根，10个1分a、b、c，得到1111的范围 for (a = 0; a <= 1111; a++) { for (b = 0; b <= 1111; b++) { c = a + b; if (fun(a)+fun(b)+fun(c)==m-4) { printf("%d+%d=%d ",a,b,c); sum++; } } }
.
//枚举火柴 int fun(int x) { int num = 0; //用一个数组来记录0-9每个数字需要用的火柴数 int f[10] = {6,2,5,5,4,5,6,3,7,6}; while (x/10!=0)//不存在个位数，最小2位数 { num += f[x%10];//得到个位数的所表示的火柴根数 x = x/10;//去掉个位数 } num += f[x];//需要加上个位数 return num; }