Sort

排序

冒泡排序

非递归版

void bubble_sort(SqList &L)
{
	int TwT=1;//标志，用于记录在这一趟数据有没有交换，若没有交换则表明没有
	for(int i=0;i<L.length-1&&TwT==1;i++)
	{
		TwT=0;
		for(int j=1;j<L.length-i;j++)
		{
			if(L.data[j-1]>L.data[j])
			{
				TwT=1;
				swap(L,j-1,j);
			}
		}
	}
}

递归版

//冒泡排序--递归版
void bubble_sort_rec(SqList &L,int n)
{
	if(n==1){return;}

	for(int i=1;i<n;i++)
	{
		if(L.data[i-1]>L.data[i])
			swap(L,i-1,i);
	}
	bubble_sort_rec(L,n-1);
}

选择排序

void select_sort(SqList &L)//时间复杂度(n-1)/2
{
	for(int i=0;i<L.length-1;i++)//最后一个不用排，故经过n-1轮
	{
		int index=i;
		int min=L.data[i];
		for(int j=i+1;j<L.length;j++)//排好序只需要n-1趟
		{
			if(L.data[j]<L.data[i])
			{
				min=L.data[j];
				index=j;
			}
		}
		if(i!=index){
		swap(L,index,i);
		}
	}
}

直接插入排序

void insert_sort(SqList &L)
{	//无暂存元素
	for(int i=0;i<L.length-1;i++)
		for(int j=i+1;L.data[j]<L.data[j-1]&&j>0;j--)
			{swap(L,j,j-1);}
}