部分轉(zhuǎn)載自CSDN博客 Morewindows Blog
冒泡排序--算法復(fù)雜度為O(n^2)
1.比較相鄰的前后二個數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將二個數(shù)據(jù)交換。
2.這樣對數(shù)組的第0個數(shù)據(jù)到N-1個數(shù)據(jù)進行一次遍歷后，最大的一個數(shù)據(jù)就“沉”到數(shù)組第N-1個位置透罢。
3.N=N-1，如果N不為0就重復(fù)前面二步冠蒋，否則排序完成羽圃。
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：有可能排序已經(jīng)完成，但仍然做了很多次比較..明顯浊服，如果又一次兩兩之間都沒有發(fā)生交換统屈，那么就是排序已經(jīng)完成..
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：再進一步考慮，如果數(shù)組只有前面一部分是無序的牙躺，后面都是有序的，那么要記錄下最后一個無序（最后一次交換發(fā)生）的位置腕扶，下一次后面的序列不用再比較..
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;
}
}
}
直接插入排序 --算法復(fù)雜度 O(n^2)
直接插入排序(InsertionSort)的基本思想是：每次將一個待排序的記錄孽拷，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中的適當位置，直到全部記錄插入完成為止半抱。
初始時脓恕，a[0]自成1個有序區(qū)膜宋，無序區(qū)為a[1..n-1]。令i=1
將a[i]并入當前的有序區(qū)a[0…i-1]中形成a[0…i]的有序區(qū)間炼幔。i++并重復(fù)第二步直到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]有序區(qū)間中找一個合適的位置
for (j = i - 1; j >= 0; j--)
if (a[j] < a[i])
break;
//如找到了一個合適的位置
if (j != i - 1)
{
//將比a[i]大的數(shù)據(jù)向后移
int temp = a[i];
for (k = i - 1; k > j; k--)
a[k + 1] = a[k];
//將a[i]放到正確位置上
a[k + 1] = temp;
}
}
}
更簡單的寫上述插入排序乃秀，把找到合適的位置和數(shù)據(jù)移動結(jié)合起來
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;
}
}
還可以用數(shù)據(jù)交換代替數(shù)據(jù)后移肛著，這樣代碼更簡潔
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]);
}
選擇排序--算法復(fù)雜度 O(n^2)
選擇排序和插入排序類似，都將數(shù)據(jù)分為有序區(qū)和無序區(qū)跺讯，所不同的是插入排序是將無序區(qū)的第一個元素直接插入到有序區(qū)以形成一個更大的有序區(qū)枢贿，而選擇排序是從無序區(qū)選一個最小的元素直接放到有序區(qū)的最后。
每一次找到無序區(qū)內(nèi)的最小值賦給a[i]
注意swap的用法刀脏，如果用位操作局荚，要注意判斷a!=b是否成立，如果沒有這一句愈污，會出現(xiàn)數(shù)字清零..
#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問題
輸入一個整數(shù)比如1234耀态，互相交換各位數(shù)字，并且以大到小排列暂雹，以小到大排列首装，求出兩個排列之差作為下一個數(shù)字..
數(shù)字轉(zhuǎn)存成字符串，選擇排序找到從小到大的排列..
#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);//數(shù)字轉(zhuǎn)化為字符串
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++)//字符串反轉(zhuǎn)得到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;//在數(shù)組num中尋找新生成的數(shù)
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..之后進行每個單詞的排序，首先放到另外一個數(shù)組內(nèi)揍魂，對每個數(shù)組排序..
#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;
}
