2种排序

• 快速排序
• • 快速排序伪码描述
  • • 选主元
  • 快速排序代码实现
• 表排序
• • 物理排序
• 桶排序
• • 桶排序伪代码
  • 基数排序（特殊的桶排序）
  • 基数排序用法--多关键字排序
• 排序算法的比较

快速排序

分而治之，递归， 选主元 ，类似于二分法

快速排序伪码描述

这里的代码只是容易看懂的代码，并不能完成功能
简单描述：面对一个数组，首先把首元素中间元素和末尾元素按从小到大排序，然后把中间元素放在倒数第二个元素的位置。这时候不需要再接着考虑首元素和末尾元素，因为第一个元素小于我们选择的主元，末尾元素大于主元，已经达到要求。
快速排序可以使得主元一步到位。

#include<stdio.h>
int main()
{
	int 
}

void Swap(int m, int n)
{
	int temp;
	temp = m;
	m = n;
	n = temp;
}

int Median3(int A[], int Left, int Right)
{
	int Center = (Left + Right) / 2;
	if (A[Left] > A[Center])
		Swap(A[Left], A[Center]);
	if(A[Left]>A[Right])
		Swap(A[Left], A[Right]);
	if(A[Center] > A[Right])
		Swap(A[Center], A[Right]);
}

void Quicksort(int A[], int  Left, int Right)
{
	int pivot,i,j;
	pivot = Median3(A, Left, Right);
	i = Left; j = Right - 1;
	for (;;)
	{
		while (A[++i] < pivot);
		while (A[--j] > pivot);
		if (i < j)
		{
			Swap(A[i], A[j]);
		}
		else
			break;
	}
	Swap(A[i], A[Right - 1]);
	Quicksort(A, Left, i - 1);
	Quicksort(A, i + 1, Right);
}

void Quick_sort(int A[],int N)
{
	Quicksort(A, 0, N - 1);
}

选主元

int Median3(int A[], int Left, int Right)
{
	int Center = (Left + Right) / 2;
	if (A[Left] > A[Center])
		Swap(A[Left], A[Center]);
	if(A[Left]>A[Right])
		Swap(A[Left], A[Right]);
	if(A[Center] > A[Right])
		Swap(A[Center], A[Right]);
	Swap(p2 + Center, p2+ Right - 1);
	return *(p2+Right-1);

}

快速排序代码实现

#include<stdio.h>

int main()
{
	void paixu_7(int* p0, int N);
	int A[10] = { 9,5,7,8,4,6,1,2,0,3 };
	int* pointer;
	pointer = A;
	paixu_7(pointer, 10);
	for (int i = 0; i < 20; i++)
		printf("%d ",A[i]);
	return 0;
}

void Swap(int *m, int *n)
{
	int temp;
	temp = *m;
	*m = *n;
	*n = temp;
}

int Median3(int *p2, int Left, int Right)
{
	void Swap(int* m, int* n);
	int Center = (Left + Right) / 2;
	if (*(p2+Left) > *(p2 + Center))
		Swap(p2 + Left, p2 + Center);
	if(*(p2 + Left) > *(p2+Right))
		Swap(p2 + Left, p2 + Right);
	if(*(p2 + Center) > *(p2 + Right))
		Swap(p2 + Center, p2 + Right);

	Swap(p2 + Center, p2+ Right - 1);
	return *(p2+Right-1);
}

void Quicksort(int *p1, int  Left, int Right)
{
	int Median3(int* p2, int Left, int Right);
	int pivot,i,j;
	pivot = Median3(p1, Left, Right);
	i = Left-1; j = Right - 2;
	for (;;)
	{
		while (*(p1+i) < pivot)
			i++;
		while (*(p1+j) > pivot)
			j--;
		if (i < j)
		{
			Swap(p1+ i, p1 + j);
		}
		else
			break;
	}
	Swap(p1+i,p1+Right-1);
	Quicksort(p1, Left, i - 1);
	Quicksort(p1, i + 1, Right);
}

void paixu_7(int *p0,int N)
{
	Quicksort(p0, 0, N - 1);
}

表排序

待排列的元素不只是一个数字，他是一个庞大的结构体。移动的不是这些结构体数据，只需要移动指向这些数据的指针。我们需要把这些指针按要求储存在一个空间里，也叫间接排序，利用指针数组，这里说的指针只是元素的下标，不是C语言里边的指针
因为元素可能是由某种结构体类型，如果选择变动结构体元素的位置将会比较麻烦
举例:比如说数组A=[3,5,2]，现在我们需要把按顺序输出元素。我们采用便排序，声明table[3]=[0,1,2],其中的元素表示数组元素的初始位置。当比较元素3>2的时候，我们变table[3]=[2,1,0],输出先输出a[2]。这种方法就是表排序

物理排序

N个数字的排列由若干独立的环组成，

判断一个环的结束

桶排序

仅仅基于比较元素来进行的排序，任一种排序方法都会出现很差的一种状态。
桶排序：位每一个值设置一个桶。一个数组，元素是指针，每个指针是一个链表的头指针。每个链表就是一个桶

比如：如果需要排列是个人的成绩，每个人成绩都是0-9；那么所有的可能成绩有10个，那么我们就创建一个10个桶，也就是10个链表。链表的首地址存在一个数组里边。读取一个学生的成绩，就放在对应成绩的桶里边。最后依次输出每个桶的值。但是当桶的个数远远大于学生个数时，比如学生10个，成绩有1000个可能的取值，那么就用到了基数排序。

桶排序伪代码

void Bucket_Sort(ElementType A[], int N)
{
	count[]//初始化桶
	while(读入一个学生的成绩)
		将该生插入count[grade]链表
	for(i=0;i<M;i++)
		if(count[i])
			输出整个count[i]链表

}

基数排序（特殊的桶排序）

• 次位优先
  
  每一列就是就是一个桶。

基数排序用法–多关键字排序

比如扑克牌的排序，关键字有花色和数字。
方法1：主位优先排序MSD，先建立四个花色桶。然后在每个桶里边按照数字排序。
方法2：次位优先LSD，先建立13个面值桶，然后建立四个花色桶

排序算法的比较