目录
一、排序算法介绍
1、选择法排序
选择法排序在排序过程中一共需要进行 n(n-1)/2 次比较，互相交换 n-1 次。选择法排序简单、容易实现，适用于数量较小的排序。
2、冒泡法排序
最好的情况是正序，因此只要比较一次即可；最坏的情况是逆序，需要比较 n*n 次。冒泡法排序是稳定的排序方法，当待排序列有序时，效果比较好。
3、交换法排序
交换法排序和冒泡法排序类似，正序时最快，逆序时最慢，排列有序数据时效果最好。
4、插入法排序
插入法排序需要经过 n-1 次插入过程，如果数据恰好应该插入到序列的最后端，则不需要移动数据，可节省时间。因此，若原始数据基本有序，此算法具有较快的运算速度。
5、折半法排序
折半法排序对于较大的 n 时，是速度最快的排序算法；当时当 n 很小时，此方法往往比其他排序算法还要慢。折半法排序是不稳定的，对应有相同关键字的记录，排序后的结果可能会颠倒次序。
以上5种排序算法：
插入法、冒泡法、交换法排序的速度较慢
，但参加排序的序列局部或整体有序时，这种排序能打到较快的速度；
当 n 较小时，对稳定性不做要求时，宜选用选择法排序；对稳定性有要求时，宜选用插入法或者冒泡法排序
。
二、算法代码实现
1、选择法排序
（1）选择法排序是指 每次选择所要排序的数组中的最大值（最小值）的数组元素，将这个数组元素与最前边没有进行排序的数组元素的值互换。
（2）每次都将下一个数字和剩余数字中的最小数字进行位置互换，直到将一组数字按从小到大排序。
（3） 排序的比较次数：n(n-1)/2，每次循环选出最大（最小）值，并交换位置。
#include<stdio.h>
int main()
{
int i,j; // 存储数值最小的数组元素的数值和该元素的位置
int a[10]; // 存储输入的数据
int iTemp;
int iPos;
printf("为数组元素赋值： \n");
// 从键盘为数组元素赋值
for(i=0; i<10; i++)
{
printf("a[%d] = ",i);
scanf("%d",&a[i]);
}
// 从小到大排序
for(i=0; i<9; i++) // 设置外层循环为下标 0~8 的元素
{
iTemp = a[i]; // 设置当前元素的最小值
iPos = i; // 记录当前元素的位置
for(j=i+1; j<10; j++) // 设置内层循环为 i+1 ~ 9
{
if(a[j] < iTemp) // 如果当前元素比最小值还小
{
iTemp = a[j]; // 重新设置最小值
iPos = j; // 记录新的元素位置
}
}
// 交换两个元素值
a[iPos] = a[i];
a[i] = iTemp;
}
// 输出数组
for(i=0; i<10; i++)
{
printf("%d\t",a[i]); // 输出制表符
if(i == 4) // 如果是第五个元素，则换行，方便查看
{
printf("\n");
}
}
return 0;
}
2、冒泡法排序
（1）冒泡法排序是指 每次比较数组中相邻的两个数组元素的值，将较小的数排在较大的数前面(从小到大排列)。
（2）第一次排序过程中将最小的数字移动到第一的位置，并将其他数字依次向后移动。
（3）每次都将剩余数字中的最小数字移动到当前剩余数字的最前方，直到将一组数字按从小到大的排序为止。
#include<iostream.h>
int main()
{
int i,j;
int a[10]; // 声明一个整形数组
int iTemp;
printf("为数组元素赋值：\n");
// 通过键盘为数组元素赋值
for(i=0; i<10; i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
// 从小到大排序
for(i=1; i<10; i++) // 外层循环元素下标为1~9
{
for(j=9; j>=i; j--) // 内层循环元素下标为i~9
{
if(a[i] < a[j-1]) // 如果前一个数比后一个数大，交换数据
{
iTemp = a[j-1];
a[j-1] = a[j];
a[j] = iTemp;
}
}
}
// 输出数组
for(i=0; i<10; i++)
{
printf("%d\t",a[i]);
if(i == 4)
{
printf("\n");
}
}
return 0;
}
3、交换法排序
（1）交换法排序是指 将每一位数字与其后的所有数一一进行比较，如果发现符合条件的的数据则交换数据。
（2）首先，用第一个数依次与其后的所有数字进行比较，如果存在比其值大(小)的数，则交换这两个数后，继续向后比较其他数，直到最后一个数。
（3）如果遇到比当前数字小的数则交换位置，依次类推，直到将一组数字按照从小到大排序为止。
#include<stdio.h>
int main()
{
int i,j;
int a[10];
int iTemp;
printf("请为数组元素赋值：\n");
// 通过键盘为数组元素赋值
for(i=0; i<10; i++) // 为元素循环赋值
{
printf("a[%d]= ",i);
scanf("%d",&a[i]);
}
// 从小到大排序
for(i=0; i<9; i++) // 外层循环元素下标为 0~8
{
for(j=i+1; j<10; j++) // 内层循环元素下标为 i+1到9
{
if(a[j] < a[i]) // 如果当前值比其他值大
{
iTemp = a[i]; // 交换两个数值
a[i] = a[j];
a[j] = iTemp;
}
}
}
// 输出数组
for(i=0; i<10; i++)
{
printf("%d\t",a[i]);
if(i == 4)
{
printf("\n");
}
}
return 0;
}
4、插入法排序
（1）插入法排序是指 抽出一个数据，在前面的数据中寻找相应的位置插入，然后继续下一个数据，直到完成排序。
（2）第一次排序时将第一个数字取出，放在第一的位置；然后进行第二次排序，先取出第二个数字，与第一个进行比较，如果小则插入在前，如果大则插入在后。
（3）不断取出未进行排序的数字与排序好的数字进行比较，(先与排在后的面的数字进行比较)，并插入到相应的位置，直到完成排序。
#include<stdio.h>
int main()
{
int i;
int a[10]; // 存储用户输入的数字
int iTemp; // 存储两个元素交换时的中间变量和记录元素位置
int iPos;
printf("请为数组元素赋值：\n");
// 通过键盘为数组元素赋值
for(i=0; i<10; i++) // 为元素循环赋值
{
printf("a[%d]= ",i);
scanf("%d",&a[i]);
}
// 从小到大排序
for(i=0; i<10; i++) // 循环数组中的元素
{
iTemp = a[i]; // 设置插入值
iPos = i-1;
while((iPos >= 0) && (iTemp < a[iPos])) // 寻找插入值的位置
{
a[iPos+1] = a[iPos]; // 插入数值
iPos--;
}
a[iPos+1] = iTemp;
}
// 输出数组
for(i=0; i<10; i++)
{
printf("%d\t",a[i]);
if(i == 4)
{
printf("\n");
}
}
return 0;
}
5、折半法排序
（1）折半法排序又称为快速法排序，是指 选择一个中间值 middle(在程序中使用数组的中间值)，然后把比中间值小的数据放在左边，比中间值大的数据放在右边。
（2）第一次比较完成后分别对中间值两边的数据进行递归比较，直到将一组数字按照从小到大排序为止。
1）在第一次排序中，首先取中间值，从左右两侧分别取出数据与中间值进行比较：
2）(左侧比较从第一个元素开始) 当左侧取出的数据比中间值大时，则交换两个互相比较的数组元素值；
3）(右侧比较从最后一个元素开始) 当右侧取出的数据比中间值大时，取前一个数组元素的值继续与中间值进行比较，如果右侧这个值比中间值小，则交换位置。
4）当中间值两侧的数据都比较一遍以后，数组以第一个元素为起点，以中间值的元素为终点，按照上面的方法继续进行比较；
5）右侧以中间值为起点，数组最后一个元素为终点，按照上述方法继续比较。
#include<stdio.h>
// 声明一个排序函数
void CelerityRun(int left, int right, int array[]);
int main()
{
int i;
int a[10];
printf("为数组元素赋值：\n");
// 通过键盘为数组元素赋值
for(i=0; i<10; i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
// 从小到大排序函数
CelerityRun(0,9,a);
// 输出数组
for(i=0; i<10; i++)
{
printf("%d\t",a[i]); // 输出制表符
if(i == 4) // 如果是第五个元素，则换行，方便查看
{
printf("\n");
}
}
return 0;
}
// 排序函数功能实现
void CelerityRun(int left, int right, int array[])
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = array[(left + right)/2]; // 求中间值
do
{
while((array[i] < middle) && (i < right)) // 第一个内层循环，从最左边开始找小于中间值的数，如果找到大于中间值的数结束
{
i++; // 左侧数组的值分别与中间值比较一次，找打大于中间值的数结束左侧循环
}
while((array[j] > middle) && (j > left)) // 第二个内层循环，从最右边开始找大于中间值的数，如果找到小于中间值的数结束
{
j++;
}
if(i <= j) // 找到了一对值，进行数值交换
{
iTemp = array[i];
array[i] = array[j];
array[j] = iTemp;
i++;
j--;
}
} while (i <= j); // do-while 设计外层循环，如果两边的下标交错(保证左右两边的数都与中间值比较了一次)，就停止循环（完成一次排序）
// 递归排序左边的数据
if(left < j)
{
CelerityRun(left,j,array);
}
// 递归排序右边的数据
if(right > i)
{
CelerityRun(right,i,array);
}
}