数据结构深入剖析（6）

一、排序的概念及分类
1、排序的一般定义
    排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。
2、排序的数学定义
    假设含n个数据元素的序列为{ R1, R2, …, Rn }，其相应的关键字序列为{ K1, K2, …, Kn }，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：
    Kp1≤Kp2≤…≤Kpn
    按此固有关系将上式记录序列重新排列为
    { Rp1, Rp2, …，Rpn }的操作称作排序。
3、排序的稳定性
    如果在序列中有两个数据元素r[i]和r[j]，它们的关键字k[i] == k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。
4、多关键字排序
    排序时需要比较的关键字多余一个：
        排序结果首先按关键字1进行排序，当关键字1相同时按关键字2进行排序，....，当关键字n-1相同时按关键字n进行排序。
5、排序中的关键操作
    比较：任意两个数据元素通过比较操作确定先后次序
    交换：数据元素之间需要交换才能得到预期结果
6、内排序和外排序
    内排序：整个排序过程不需要访问外存便能完成。
    外排序：待排序的数据元素数量很大，整个序列的排序过程不可能在内存中完成。
7、排序的审判
    时间性能：关键性能差异体现在比较和交换的数量。
    辅助存储空间：为完成排序需要的额外的存储空间，必要时可以“空间换时间”。
    算法的实现复杂性：过于复杂的排序算法会影响代码的可读性和可维护性，也可能影响排序的性能。
二、基本排序算法
1、选择排序：每一趟（例如第i趟，i = 0,1,...,n-2）在后面n-i个待排序的数据元素中选出关键字最小的元素，作为有序元素序列的第i个元素。
算法实现：
#include  
void printarray(int array[],int len)
{
    int i = 0;
    for(i = 0; i < len;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}
void swap(int array[],int i,int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
void SelectionSort(int array[],int len)
{
    int i = 0;
    int j = 0;
    int k = 0;
    for(i = 0;i < len;i++){
        k = i;
        for(j = i+1;j < len;j++){
            if(array[k] > array[j]){
                k = j;
            }
        }
    swap(array,i,k);
    }
}
int main()
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    printarray(array,len);
    SelectionSort(array,len);
    printarray(array,len);
    return 0;
}
2、插入排序：当插入第i（i >= 1）个数据元素时，前面的v[0],v[1],...,v[i-1]已经排序好。这时，用v[i]的关键字与v[i-1],v[i-2],....的关键字进行比较，找到插入位置即将v[i]插入，原来位置上的对象向后移动。
算法实现：
#include  
void printarray(int array[],int len)
{
    int i = 0;
    for(i = 0; i < len;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}
void InsertionSort(int array[],int len)
{
    int i = 0;
    int j = 0;
    int k = -1;
    int temp = -1;

    for(i = 1;i < len;i++){
        k = i;
        temp = array[k];

        for(j = i-1;(j >= 0)&& (array[j] > temp);j--){
            array[j+1] = array[j];
            k = j;
        }
    array[k] = temp;
    }
}

int main()
{
    int array[] = {21,25,49,25,16,8};
    int len = sizeof(array) / sizeof(*array);
    printarray(array,len);
    SelectionSort(array,len);
    printarray(array,len);
    return 0;
}
3、冒泡排序：设待排数据元素序列中的元素个数为n。最多作n-1趟，i=1,2，...,n-1。在第i趟排序后向前，j= n-1, n-2,...,i,两两比较v[j-1]和v[j]的关键字。如果发生逆序，则交换v[j-1]和v[j]。
算法实现：
#include  
void printarray(int array[],int len)
{
    int i = 0;
    for(i = 0; i < len;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}
void swap(int array[],int i,int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}
void BubbleSort(int array[],int len)
{
    int i = 0;    
    int j = 0;
    int exchange  = 1;

    for(i = 0;(i < len) && exchange;i++){
        exchange = 0;
        for(j = len - 1;j > i;j--){
            if(array[j] < array[j-1]){
                swap(array,j,j-1);
                exchange = 1;
            }
        }
    }
    printf("i = %d\n",i);
}
int main()
{
    int array[] = {1,2,3,4,5,6};
    int len = sizeof(array) / sizeof(*array);    
    printarray(array,len);
    BubbleSort(array,len);
    printarray(array,len);
    return 0;
}