【11】排序

排序方法 1.影响排序的效率有哪些

（1）交换次数

（2）移动次数

2.稳定排序和非稳定排序

设文件f=（R1……Ri……Rj……Rn）中记录Ri、Rj（i≠j，i、j=1……n）的key相等，即Ki=Kj。

若在排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称这种排序是稳定的，其含义是它

没有破坏原本已有序的次序。反之，若排序后Ri与Rj的次序有可能颠倒，则这种排序

是非稳定的，即它有可能破坏了原本已有序记录的次序。

12 3 34a 1 423 34b

//不稳定排序

如果你排序结束后 34b 在 34a 的前面，说明相同数据被交换了为，此时称为不稳定排序

1 3 12 34b 34a 423

//稳定排序

1 3 12 34a 34b 423

3.排序方法 1 冒泡排序

//1. 冒泡排序

void bubbleSort(int *p, int n)
{
	int i,j;
	int temp;
	for(i = 0; i < n-1; i++)
	{
		for(j = 0; j < n-1-i; j++)
		{
			if(p[j] > p[j+1])
			{
				temp = p[j];
				p[j] = p[j+1];
				p[j+1] = temp;
			}
		}
	}
}

///

2. 选择排序

选择排序的原理与冒泡排序相比更加容易理解：选定一个标准位，将待排序序列中的元素与标准位元素逐一比较，反序则互换
其中所谓的标准位实际上也是数组中的一个下标位，在选定了这个下标位之后，在一轮排序中这个标准位将不再移动，
然后将待排序序列——也就是这个标准位之后所有元素组成的序列——中的元素逐个和标准位上的值进行比较
如果某一个待排序序列上的值比标准位上的值更小（升序排序）或者更大（降序排序），那么就将这个元素和标准位上的元素进行互换即可
标准位的选择一般选取待排序序列的第一个下标作为标准位使用

//2.选择法排序
//不稳定举例
//33 68 46 33 25 80 19 12

void selectSort(int *p, int n)
{
	int i,j;
	int temp;
	for(i = 0; i < n-1; i++)
	{
		for(j = n-1; j > i; j--)
		{
			if(p[j] < p[i]) //p[i]代表每一轮的基准值 i是基准值的位置
			{
				temp = p[i];
				p[i] = p[j];
				p[j] = temp;
			}
		}
	}

}

///

3. 插值排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，

就是第一个元素。比较是从有序序列的末尾开 始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它

大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相 等的，那么插入元

素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序

后的顺序，所以插入排序是稳 定的。

0 1 2  3   4 5  6
6 2 3 'J' 5 9 'K' //最开始数组 

//最开始
//裁判手里: 2 3 ‘J’ 5 9 ‘K’
//我手里： 6

//3.插值排序(思想类似于斗地主抓牌)
//每抓一张牌之后，都将自己手里的牌变成有序的
//始终保证我手里的牌是有序的
// 裁判员 5 9 ‘K’

// 我：6 //默认最开始的时候，我的手里已经有了一张牌

//抓一张牌
2
//将2这张牌插入到我手里的牌中
//将抓到的牌与当前我手里的牌进行追个比较如果找到的牌小，就交换位置

//我 2 6

//再抓一张牌
3
//将3这张牌插入到我手里的牌中
//将抓到的牌与当前我手里的牌进行追个比较如果找到的牌小，就交换位置
//我 2 3 6
//再抓一张牌
‘J’
//将’J’这张牌插入到我手里的牌中
//将抓到的牌与当前我手里的牌进行追个比较如果找到的牌小，就交换位置
//我 2 3 6 //因为手里的牌永远是有序的，所以当抓到的’J’比手里面最大的6还大，那么也就没有必要再将’J’和2 3比较

void insertSort(int *p, int n)
{
int i,j;
int temp;
for(i = 1; i < n; i++) //代表开始抓牌，因为默认手里已经有一张牌，所以i的下标 从1开始，终止下标是数组中最后一个元素，也就是最后一张牌
{ //需要将每一张牌插入到手里
	

for(j = i; j > 0; j--)//j == i 代表 j此时为你抓到的牌
{
	if(p[j] < p[j-1]) //将抓到手里的牌与目前手里的牌进行比较,注意比较的顺序是从后往前比
	{
		temp = p[j];
		p[j] = p[j-1];
		p[j-1] = temp;
	}
	else
	{
		break;//因为手中的牌一直有序
	}
}

///

4. 快速排序

//不稳定

#include 

//piovt 枢轴
int getPiovt(int *p,int low, int high)
{
	int flag = p[low];//flag是镖旗
	while(low < high)
	{
		//最开始从右向左进行扫描
		while(flag <= p[high] && low < high)//只要p[high] >= flag 那么就high--
			high--;
		if(low < high)
		{
			p[low] = p[high];//将小于flag的数移动到左边
			low++;//准备改变扫描的方向，从左向右进行扫描
		}
		while(flag >= p[low] && low < high)//只要p[low] <= flag 那么就low++
			low++;
		if(low < high)
		{
			p[high] = p[low];//将大于flag的数，移动到右边
			high--;//准备改变扫描的方向，从右往左进行扫描
		}
	}
	//将flag赋值到枢轴位置
	p[low] = flag;
	return low;//最后循环结束low == high 此时的位置就是枢轴位置
}


void showArray(int *p, int n)
{
	int i;
	//从右向左进行扫描
	for(i = 0; i < n; i++)
	{
		printf("%d ",p[i]);
	}

printf("\n");

}
//写一个递归函数，进行快排
void quickSort(int *p, int low,int high)
{
	int piovt = getPiovt(p,low,high);
	if(low < piovt-1)//递归快排枢轴的左侧
		quickSort(p,low,piovt-1);
	if(piovt+1 < high)//递归快排枢轴的右侧
		quickSort(p,piovt+1,high);
}

int main(int argc, const char *argv[])
{
	//快排思想：先找到枢轴的位置，枢轴左侧的数都小于等于枢轴位置数据，右侧大于等于
	int a[8] = {32,2,54,6,78,23,17,76};
	showArray(a,8);
	quickSort(a,0,7);
	printf("快速排序之后---------------\n");
	showArray(a,8);
	return 0;
}