部分转载自CSDN博客 Morewindows Blog
冒泡排序--算法复杂度为O(n^2)
1.比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2.这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3.N=N-1，如果N不为0就重复前面二步，否则排序完成。
void bubble1(int a[],int n)
{
int tmp;
for(int i=0;i<n;i++)
for(int j=1;j<n-i;j++)
if(a[j-1]>a[j]) { tmp=a[j-1];a[j-1]=a[j];a[j]=tmp;}
}
问题1：有可能排序已经完成，但仍然做了很多次比较..明显，如果又一次两两之间都没有发生交换，那么就是排序已经完成..
void bubble2(int a[],int n)
{
int tmp,k=n;
bool flag=true;
while(flag)
{
flag=false;
for(int j=1;j<k;j++)
if(a[j-1]>a[j])
{
tmp=a[j-1];a[j-1]=a[j];a[j]=tmp;
flag=true;
}
k--;
}
}
问题2：再进一步考虑，如果数组只有前面一部分是无序的，后面都是有序的，那么要记录下最后一个无序（最后一次交换发生）的位置，下一次后面的序列不用再比较..
void bubble3(int a[], int n)
{
int tmp,flag=n;
int j,k;
while(flag)
{
k=flag;
flag=0;
for(j=1;j<k;j++)
if(a[j-1]>a[j])
{ tmp=a[j-1];a[j-1]=a[j];a[j]=tmp;
flag=j;
}
}
}
直接插入排序 --算法复杂度 O(n^2)
直接插入排序(InsertionSort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。i++并重复第二步直到i==n-1。排序完成。
void Insertsort1(int a[], int n)
{
int i, j, k;
for (i = 1; i < n; i++)
{
//为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置
for (j = i - 1; j >= 0; j--)
if (a[j] < a[i])
break;
//如找到了一个合适的位置
if (j != i - 1)
{
//将比a[i]大的数据向后移
int temp = a[i];
for (k = i - 1; k > j; k--)
a[k + 1] = a[k];
//将a[i]放到正确位置上
a[k + 1] = temp;
}
}
}
更简单的写上述插入排序，把找到合适的位置和数据移动结合起来
void Insertsort2(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
if (a[i] < a[i - 1])//否则说明a[i]可以直接加入到序列末尾
{
int temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--)
a[j + 1] = a[j];
a[j + 1] = temp;
}
}
还可以用数据交换代替数据后移，这样代码更简洁
void Insertsort3(int a[], int n)
{
int i, j;
for (i = 1; i < n; i++)
for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--)
Swap(a[j], a[j + 1]);
}
选择排序--算法复杂度 O(n^2)
选择排序和插入排序类似，都将数据分为有序区和无序区，所不同的是插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而选择排序是从无序区选一个最小的元素直接放到有序区的最后。
每一次找到无序区内的最小值赋给a[i]
注意swap的用法，如果用位操作，要注意判断a!=b是否成立，如果没有这一句，会出现数字清零..
#include <stdio.h>
void swap1(int &a, int &b)
{
if(a!=b)
{
a = a^b;
b = a^b;
a = a^b;
}
}
void swap2(int &a, int &b)
{
int tmp;
tmp = a; a=b; b=tmp;
}
void mysort(int a[],int n)
{
int i,j,minIndex;
for(i=0;i<n;i++)
{
minIndex = i;
for(j=i+1;j<n;j++)
if(a[minIndex]>a[j]) minIndex = j;
swap2(a[i],a[minIndex]);
}
}
int main()
{
int a[10]={6,4,5,2,3,8,1,7,9,10};
mysort(a,10);
for(int i=0;i<10;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
1.6174问题
输入一个整数比如1234，互相交换各位数字，并且以大到小排列，以小到大排列，求出两个排列之差作为下一个数字..
数字转存成字符串，选择排序找到从小到大的排列..
#include<stdio.h>
#include<string.h>
int num[2000],count;
int get_next(int x)
{
int a,b,n;
char tmp;
char s[10];
sprintf(s,"%d",x);//数字转化为字符串
n=strlen(s);
for(int i=0;i<n;i++)//选择排序得到从小到大的b
for(int j=i+1;j<n;j++)
if(s[i]>s[j]) {tmp=s[i];s[i]=s[j];s[j]=tmp;}
sscanf(s,"%d",&b);
for(i=0;i<n/2;i++)//字符串反转得到a
{
tmp=s[i];s[i]=s[n-1-i];s[n-1-i]=tmp;
}
sscanf(s,"%d",&a);
return a-b;
}
int main()
{
scanf("%d",&num[0]);
printf("%d",num[0]);
count=1;
for(;;)
{
num[count]=get_next(num[count-1]);
printf("-> %d",num[count]);
int found=0;//在数组num中寻找新生成的数
for(int i=0;i<count;i++)
if(num[i] == num[count]) {found=1;break;}
if(found) break;
count++;
}
printf("\n");
return 0;
}
2.字母重排问题
输入了所有单词，可以对所有单词进行排序，这时用到的是cmp_string..之后进行每个单词的排序，首先放到另外一个数组内，对每个数组排序..
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n;
char word[2000][10],sorted[2000][10];
int cmp_char(const void* _a, const void* _b)
{
char* a=(char*) _a;
char* b=(char*) _b;
return *a - *b;//从小到大排列,返回要求a>b返回1,a<b返回0.
}
int cmp_string(const void* _a, const void* _b)
{
char* a=(char*) _a;
char* b=(char*) _b;
return strcmp(a,b);//从小到大排列,返回要求a>b返回1,a<b返回-1.
}
int main()
{
n=0;
for(;;)
{
scanf("%s",word[n]);
if(word[n][0]=='*') break;
n++;
}
qsort(word,n,sizeof(word[0]),cmp_string);//给所有单词排序
for(int i=0;i<n;i++)//给每个单词排序
{
strcpy(sorted[i],word[i]);
qsort(sorted[i],strlen(sorted[i]),sizeof(char),cmp_char);
}
char s[10];
while(scanf("%s",s)==1)
{
qsort(s,strlen(s),sizeof(char),cmp_char);
int found=0;
for(int i=0;i<n;i++)
if(strcmp(sorted[i],s)==0)
{
found=1;
printf("%s",word[i]);//在字典里找到了
}
if(!found) printf(":(");
printf("\n");
}
return 0;
}
