c语言各种常见排序（直接插入排序、折半插入排序、冒泡排序、选择排序、堆排序）

001	#include <stdio.h>

002	#include <stdlib.h>

003	int main()

004

{

005	int L[11]={0,70,38,65,97,76,93,1,15,68,64}; //0不做排序只是当做哨兵，或者临时交换空间使用。

006

int i=0;

007	printf("未排序前序列:\n");

008	for(i=1;i<=10;i++)

009

{

010	printf("%d ",L[i]);

011

}

012	printf("\n-------------------------------------\n");

013	insertSort(L); //直接插入排序

014	//BInsertSort(L); //折半插入排序

015	//bubbleSort(L);//冒泡排序

016	//selectSort(L); //选择排序

017	//heapSort(L,10); //堆排序

018	printf("排序后序列:\n");

019	for(i=1;i<=10;i++)

020

{

021	printf("%d ",L[i]);

022

}

023

return 0;

024

}

025	void insertSort(int L[11])//插入排序 插入排序的最差和平均情况的性能是O(n^2)

026

{

027	int i=0,j=0;

028	for(i=2;i<=10;++i)

029

{

030	L[0]=L[i]; //监视哨

031	for(j=i-1;L[0]<L[j];--j)

032

{

033	L[j+1]=L[j]; //记录后移

034

}

035	L[j+1]=L[0];//插入记录

036

}

037

}

038	void BInsertSort(int L[11]) //折半查找排序

039

{

040	int i=0,j=0,low=0,high=0,m=0;

041	for(i=2;i<=10;++i)

042

{

043	L[0]=L[i]; //监视哨

044	low=1;high=i-1;

045	while(low<=high){

046	m=(low+high)/2; //折半

047	if(L[0]<L[m])

048

high=m-1;

049

else

050

low=m+1;

051

}

052	for(j=i-1;L[0]<L[j];--j)

053	L[j+1]=L[j]; //记录后移

054	L[high+1]=L[0]; //插入

055

}

056

}

057	void bubbleSort(int L[11]) //冒泡排序复杂度是O(n^2)

058

{

059	int i=0,j=0;

060	for(i=1;i<=10;++i)

061

{

062	for(j=1;j<=10-i;++j)

063

{

064	if(L[j]>L[j+1])

065

{

066	L[0]=L[j];

067	L[j]=L[j+1]; //用辅助空间交换两个值

068	L[j+1]=L[0];

069

}

070

}

071

}

072

}

073	void selectSort(int L[11]) //选择排序 复杂度为：O(n^2)

074

{

075	int i=0,j=0,min_idx=0;

076	for(i=1;i<=10;++i)

077

{

078	min_idx=i;

079	for(j=i+1;j<=10;++j)

080

{

081	if(L[j]<L[min_idx])

082

{

083	min_idx=j;

084

}

085

}

086	if(min_idx!=i)

087

{

088	L[0]=L[i];

089	L[i]=L[min_idx]; //交换最小值与L[i]

090	L[min_idx]=L[0];

091

}

092

}

093

}

094	void heapSort(int L[11],int n) //堆排序

095

{

096

int i=0;

097	for(i=n/2;i>0;--i)

098	heapAjust(L,i,n);

099	for(i=n;i>1;--i)

100

{

101	L[0]=L[1];

102	L[1]=L[i];

103	L[i]=L[0];

104	heapAjust(L,1,i-1);

105

}

106

}

107	void heapAjust(int L[11],int s,int m) //建大顶堆，使L[s...m]为大顶堆

108

{

109	int rc=L[s],i=0;

110	for(i=2*s;i<=m;i*=2)

111

{

112	if(i<m&&L[i]<L[i+1])

113

++i;

114	if(rc>=L[i])

115

break;

116	L[s]=L[i];

117

s=i;

118

}

119

L[s]=rc;

120

}