排序算法有很多，这里先按照算法的复杂程度由浅入深的介绍一些常用的排序算法。
1.插入排序：
这是一种非常直观的排序算法。它的基本思路就是：从数组的第二个元素开始，依次取数组中的元素，将它与前面的的元素相比较，插入到这个元素的前面或者后面（这取决于你想从大往小排序还是从小往大排序）。然后再取下一个元素，跟前两个已经有序的数比较，插入到合适的位置。依次类推。下面看一下程序：
//插入排序
void insertSort(pArrayList list)
{
int tmp;
//遍历每个元素
for(int i = 0; i <list->length;++i)
{
//找这个元素之前的元素
for(int j = 0; j <= i;++j)
{
//如果当前元素小于之前的元素，则把当前元素插入到之前元素的位置
if(list->data[j] > list->data[i])
{
deleteElem(list,i,&tmp);
insertElem(list,j,tmp);
}
}
}
}
注意到，我们使用的是之前介绍过的ArrayList来承载数组，而pArrayList是指向这个结构体的指针。其实由于插入的过程中，前面的元素是有序的，所以我们可以完全利用在查找方法里介绍过的“折半”的思路来完成插入时的查找操作：
//折半插入排序
void BinaryInsertSort(pArrayList list)
{
//遍历每个元素
for(int i = 0; i <list->length;++i)
{
//由于当前元素之前的所有元素已经排好序了，所以可以通过折半查找位置来加快排序
BinaryInsert(list,i);
}
}
//具体的折半查找操作
void BinaryInsert(pArrayList list, int curr)
{
int low = 0;
int high = curr;
int mid ;
int tmp;
while(low <= high)
{
mid = (low + high) / 2;
//如果当前元素小于中间元素
if(list->data[mid] > list->data[curr])
{
//将当前元素插入到中间元素的位置
deleteElem(list,curr,&tmp);
insertElem(list,mid,tmp);
//记录当前元素的新位置
curr = mid;
//缩小比较的范围
high = mid-1;
}
else
{
//缩小比较的范围
low = mid+1;
}
}
}
这样会更快一些。
2.选择排序。
这也是一种直观的排序方式。从0~n-1个元素中选择最小的元素，与第0个元素交换；从1~n-1个元素中选择最小的元素，与第一个元素位置交换，依次类推。
//选择排序
void selectSort(pArrayList list)
{
int minIndex;
int tmp;
//起始位置不断递增
for(int i = 0 ; i < list->length; ++i)
{
//找出从起始位置到最后一个元素的最小值，并返回它的位置
minIndex = selectMiniElem(list,i);
//如果二者位置不等，则交换它们
if(minIndex != i)
{
tmp = list->data[i];
list->data[i] = list->data[minIndex];
list->data[minIndex] = tmp;
}
}
}
//返回i~length中最小的元素的下标
int selectMiniElem(pArrayList list, int index)
{
//min初始为很大的数
int min = 100000;
int minIndex;
for(int i = index ; i < list->length;++i)
{
if(list->data[i] < min)
{
min = list->data[i];
minIndex = i;
}
}
return minIndex;
}
3.冒泡排序
这个方法的基本思路是：用第0个元素与第1个比较，如果第0个比第1个大，那么交换它们的位置。然后第1个与第2个比较，前一个比后一个大，继续交换它们的位置，这样以此类推。一轮循环结束以后，最大的元素就跑到了数组的末尾。然后在这样比较数组的前n-1个元素，然第二大的元素跑到数组的倒数第二个位置……这样以此类推，就能比较出所有元素了。值得注意的是，如果有一轮冒泡的过程中，并没有任何元素发生位置的交换，那么此时数组已经有序了，不用继续循环了：
void BubbleSort(pArrayList list)
{
int tmp;
int change = 0;
//比较的轮数
for(int i = 0; i < list->length-1;++i)
{
change = 0;
//每个元素与他之后的元素比较
for(int j = 0; j < list->length - i -1;++j)
{
//如果它比之后的元素大，交换二者的位置
if(list->data[j] > list->data[j+1])
{
tmp = list->data[j];
list->data[j] = list->data[j+1];
list->data[j+1] = tmp;
++change;
}
}
//如果没有发生任何交换，那么数组已经有序了
if(0 == change)
{
printf("第%d轮没有比较发生",i);
return ;
}
}
}
为什么把这三中排序方法放在一起讲呢？因为我们注意到，这三种排序都是通过一个二重循环搞定的，它们的复杂度都为O(n^2)。下一小节将介绍一些更快的排序算法。