冒泡排序（Bubble Sort疾渴，臺灣譯為：泡沫排序或氣泡排序）是一種簡單的排序算法千贯。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個元素搞坝，如果他們的順序錯誤就把他們交換過來搔谴。走訪數(shù)列的工作是重復(fù)地進行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成桩撮。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端
/*
用選擇法對10個數(shù)進行排序
*/
#include<stdio.h>
void main()
{
int i,j,a[10];
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<9;i++)?
{//n個數(shù)要進行n-1趟比較
for(j=0;j<=9-i;j++)? ? ? ? ? //每趟比較n-i次
if(a[j]>a[j+1])? ? ? ? ? //依次比較兩個相鄰的數(shù)敦第，將小數(shù)放在前面，大數(shù)放在后面
{
int t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
for(i=0;i<10;++i)? ? ? ? ? ? ? //輸出比較之后的數(shù)組
printf(" %d",a[i]);
}
另一種常見的寫法
/*
冒泡排序的另外一種寫法
*/
#include<stdio.h>
void BubbleSort(int a[],int n)
{
int i,j;
for(i=n-1;i>0;--i)? ? ? ? ? //從n-1循環(huán)的到0店量，也是n次
for(j=0;j<i;j++)
if(a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
void main()
{
int a[10],i;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
BubbleSort(a,10);
printf("排序后的數(shù)組：\n");
for(i=0;i<10;i++)
printf(" %d",a[i]);
}
選擇排序(Selection sort)是一種簡單直觀的排序算法芜果。它的工作原理如下。首先在未排序序列中找到最小元素融师，存放到排序序列的起始位置右钾，然后，再從剩余未排序元素中繼續(xù)尋找最小元素诬滩，然后放到排序序列末尾(目前已被排序的序列)霹粥。以此類推，直到所有元素均排序完畢疼鸟。
#include<stdio.h>
void SelectSort(int a[],int n)?
{?
? ? int i,j;?
? ? for(i=0;i<n-1;i++)? ? ? ? ? ? ? //n個數(shù)要進行n-1趟比較后控，每次確定一個最小數(shù)放在a[i]中?
? ? {?
? ? ? ? int k=i;? ? ? ? ? ? ? ? ? ? //假設(shè)a[0]是最小的數(shù)，把下標(biāo)0放在變量K里面空镜，?
? ? ? ? for(j=i+1;j<n;j++)? ? ? ? ? ?
? ? ? ? ? ? if(a[k]>a[j])? k=j;? ? //如果a[k]>a[j] 前面的數(shù)比后面的數(shù)大浩淘，交換下標(biāo)捌朴，此時k指向小的數(shù)?
? ? ? ? if(k!=i)?
? ? ? ? {?
? ? ? ? ? ? int temp=a[i];?
? ? ? ? ? ? a[i]=a[k];?
? ? ? ? ? ? a[k]=temp;?
? ? ? ? }?
? ? }?
}?
void main()?
{?
? ? int a[10],i;?
? ? for(i=0;i<10;i++)?
? ? ? ? scanf("%d",&a[i]);?
? ? SelectSort(a,10);?
? ? printf("排序后的數(shù)組：\n");?
? ? for(i=0;i<10;i++)?
? ? ? ? printf(" %d",a[i]);?
}?
希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步张抄。然后算法再取越來越小的步長進行排序砂蔽，算法的最后一步就是普通的插入排序，但是到了這步署惯，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）左驾。
假設(shè)有一個很小的數(shù)據(jù)在一個已按升序排好序的數(shù)組的末端。如果用復(fù)雜度為O(n2)的排序（冒泡排序或插入排序）极谊，可能會進行n次的比較和交換才能將該數(shù)據(jù)移至正確位置诡右。而希爾排序會用較大的步長移動數(shù)據(jù)，所以小數(shù)據(jù)只需進行少數(shù)比較和交換即可到正確位置轻猖。
一個更好理解的希爾排序?qū)崿F(xiàn)：將數(shù)組列在一個表中并對列排序（用插入排序）帆吻。重復(fù)這過程，不過每次用更長的列來進行咙边。最后整個表就只有一列了猜煮。將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身僅僅對原數(shù)組進行排序（通過增加索引的步長败许，例如是用i += step_size而不是i++）王带。
例如，假設(shè)有這樣一組數(shù)[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]市殷，如果我們以步長為5開始進行排序辫秧，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應(yīng)該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對每列進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
當(dāng)我們以單行來讀取數(shù)據(jù)時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經(jīng)移至正確位置了被丧，然后再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變?yōu)椋?/p>
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進行排序（此時就是簡單的插入排序了）盟戏。
//希爾排序
#include<stdio.h>
#define LT(a,b) ((a)<(b))
#define MAX_SIZE 20
#define T 3? ?
#define N 10
typedef int KeyType;
typedef int InfoType;
typedef struct
{
KeyType key;
InfoType otherinfo;
}RedType;
typedef struct
{
RedType r[MAX_SIZE+1];
int length;
}SqList;
void PrintSqList(SqList L)
{
int i;
for(i=1;i<L.length;i++)
{
printf("(%d %d)",L.r[i].key,L.r[i].otherinfo);
}
printf("\n");
}
int? PrintSqlListKey(SqList L)
{
int i;
for(i=1;i<L.length;i++)
{
printf("%d ",L.r[i].key);
}
printf("\n");
return 0;
}
void ShellInsert(SqList &L,int dk)
{
int i,j;
for(i=dk+1;i<=L.length;i++)
{
if LT(L.r[i].key,L.r[i-dk].key)
{
L.r[0]=L.r[i];
for(j=i-dk;j<0&& LT(L.r[i].key,L.r[j].key);j-=dk)
{
L.r[j+dk]=L.r[j];
}
L.r[j+dk]=L.r[0];
}
}
}
void ShellSort(SqList &L,int dlta[],int t)
{
int k;
for(k=0;k<t;k++)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //對所有增量序列
{
ShellInsert(L,dlta[k]);
printf("dlta[%d]=%d,第%d趟排序結(jié)果（僅輸出關(guān)鍵字）:",k,dlta[k],k+1);
PrintSqlListKey(L);
}
}
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,65},{13,6},{27,7},{49,8},{55,9},{4,10}};
SqList m;
int i,dt[T]={5,3,1};
for(i=0;i<N;i++)
{
m.r[i+1]=d[i];
}
m.length=N;
printf("希爾排序前：\n");
PrintSqList(m);
printf("\n");
ShellSort(m,dt,T);
printf("希爾排序后：\n");
PrintSqList(m);
printf("\n");
}
歡迎工作一到五年的Java工程師朋友們加入Java學(xué)習(xí)之路：733234221
群內(nèi)提供免費的Java架構(gòu)學(xué)習(xí)資料（里面有高可用、高并發(fā)甥桂、高性能及分布式柿究、Jvm性能調(diào)優(yōu)、Spring源碼黄选，MyBatis蝇摸，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構(gòu)資料）合理利用自己每一分每一秒的時間來學(xué)習(xí)提升自己，不要再用"沒有時間“來掩飾自己思想上的懶惰办陷！趁年輕貌夕，使勁拼，給未來的自己一個交代
