1.按存储分类:内部排序和外部排序
内部排序:是数据记录在内存中进行排序;外部排序:是因排序的数据很大,一般一次不能容纳全部的排序记录,在排序过程中需要访问外存。内部排序高速、有效,是我们比较常用的排序方法。外部排序速度慢,效率低,一般不建议使用外部排序,比较实用的排序还是只有内部排序。
2.内部排序分类:插入排序、选择排序、交换排序、归并排序、基数排序。
在内部排序中,最常见、有效且实用的排序算是交换排序,本文将在下面章节重点讲述交换排序中的冒泡排序和快速排序。
二、交换排序
1.冒泡排序
冒牌排序是我们读书时最先接触的一种排序算法,也是比较经典的排序算法。
原始的冒泡排序函数:
void bubbleSort(int a[], int n)
{
for(int i =0 ; i< n-1; ++i)
{
for(int j = 0; j < n-i-1; ++j)
{
if(a[j] > a[j+1])
{
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
对冒泡排序常见的改进方法是加入标志性变量,用于标志某一趟排序过程中是否有数据交换。
第1种改进法:设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
void Bubble_1( int r[], int n)
{
int pos = 0;
int i;
int j;
int tmp;
i = n - 1;
while(i > 0)
{
pos = 0;
for(j=0; j<i; j++)
{
if(r[j] > r[j+1])
{
pos = j; //记录交换的位置
tmp = r[j];
r[j] = r[j+1];
r[j+1] = tmp;
}
}
i= pos;
}
}
排序趟数几乎减少了一半。
void Bubble_2(int r[], int n)
{
int low = 0;
int high= n -1;
int tmp,j;
while(low < high)
{
for(j=low; j<high; ++j) //正向冒泡,找到最大者
{
if(r[j]> r[j+1])
{
tmp = r[j];
r[j]=r[j+1];
r[j+1]=tmp;
}
--high;
for(j=high; j>low; --j) //反向冒泡,找到最小者
{
if(r[j]<r[j-1])
{
tmp = r[j];
r[j]=r[j-1];
r[j-1]=tmp;
}
++low;
}
}
}
}
大致步骤如下:
1)选择一个基准元素,通常选择第一个元素或者最后一个元素。
2)通过一趟排序将待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。
3)此时基准元素在其排好序后的正确位置。
4)然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。举例:
对无序数组[6 2 4 1 5 9]排序:
a),先把第一项[6]取出来,
用[6]依次与其余项进行比较:
如果比[6]小就放[6]前边,2 4 1 5都比[6]小,所以全部放到[6]前边;
如果比[6]大就放[6]后边,9比[6]大,放到[6]后边;一趟排完后变成下边这样:
排序前 6 2 4 1 5 9
排序后 2 4 1 5 6 9b),对前半边[2 4 1 5]继续进行快速排序
重复步骤a)后变成下边这样:
排序前 2 4 1 5
排序后 1 2 4 5前半边排序完成,总的排序也完成:
排序前:[6 2 4 1 5 9]
排序后:[1 2 4 5 6 9]
排序结束
代码
将前后分开函数:
int partition(int unsorted[], int low, int high)
{
int pivot = unsorted[low];
while(low < high)
{
while((low < high) && (unsorted[high] >= pivot))
--high;
unsorted[low] = unsorted[high];
while((low < high) && (unsorted[low] <= pivot))
++low;
unsorted[high] = unsorted[low];
}
unsorted[low] = pivot;
return low;
}
快速排序函数:
void quickSort(int unsorted[], int low, int high)
{
int loc = 0;
if(low < high)
{
loc = partition(unsorted, low, high);
quickSort(unsorted, low, loc -1);
quickSort(unsorted, loc + 1, high);
}
}
举例测试:
void Main(void)
{
int i;
int a[6] = {6, 2, 4, 1, 5, 9};
quickSort(a, 0, 5);
for(i=0; i<6; i++)
printf("a[%d] = a[%d]\n", i, a);
}