（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;//因为手中的牌一直有序
}
}
///
- 快速排序
//不稳定
#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; }
