[数据结构与算法]数据结构---交换排序

交换排序

算法思想：两两比较待

冒泡排序

过于简单不多做介绍，想象一下气泡往上冒，每一轮会有一个数会排在最终位置上

void BubbleSort(int a[])
{
	
	for(int i=n-1;i>0;i--)
	{
		int flag=0;//本趟冒泡是否发生交换的标志
		//如果没有发生交换，说明表已经有序提前结束循环 
		for(int j=1;j<=i;j++)
		{
			if(a[j]>a[j+1])
			{
				int temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
				flag=1;
			}
		}
		if(!flag)
		break;
	}
}

1、算法分析：
①时间复杂度：O（n^2）
②空间复杂度：O（1）
③稳定排序

快速排序

1、算法思想：在待排序的n个记录中任取一个记录（这里每次取表中的第一个）作为枢纽。经过一次排序后，将比枢纽大的数排在枢纽的右边，比枢纽小的数排在左边。然后接着分别对左右子表进行同样的操作，直至每一子表只有一个记录

2、算法步骤：
①选择表中第一个数作为枢轴，并将枢轴暂存在a[0]位置上，附设两个指针low,high，初始时分别指向表的下界和上界
②从表的最右侧向左搜索，找到第一个比a[0]小的值，执行a[low]=a[high]
③从表的最左侧位置向右搜索找到第一个关键字大于a[0]的值，执行a[high]=a[low]
④重复②③步骤，直至low与high相等为止，此时high或low的位置即为枢轴在此趟排序中的最终位置，原表被分为左右子表

#include<iostream>
using namespace std;

int a[9]={1000,49,38,65,97,76,13,27,49};
int n=8;
int Partition(int a[],int low,int high)
{
	a[0]=a[low]; //枢轴记录为low赋值给0 
	while(low<high)
	{
		while(low<high&&a[high]>=a[0])high--;
		a[low]=a[high];
		while(low<high&&a[low]<=a[0])low++;
		a[high]=a[low];
	}
	a[low]=a[0];
	return low;
}
void QuickSort(int a[],int low,int high)
{
	if(low<high)
	{
		int mid = Partition(a,low,high);
		QuickSort(a,low,mid-1); //左子表递归
		QuickSort(a,mid+1,high); //右子表递归
	}
}

int main()
{
	cout<<"排序前:"<<endl;
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}	
	cout<<endl<<"排序后:"<<endl;
	QuickSort(a,1,n);
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}

}

3、算分分析：
时间复杂度：O（n*log2n）
空间复杂度：O（log2n）或O（n），主要是递归所用的栈

4、算法特点：
①不稳定排序
②难用于链式结构（只要用了二分法基本都难以使用链式结构）
③适合初始记录无序，n较大时的情况