算法：常见的几种排序

资料摘自<数据结构C++语言描述>

选择排序

选择排序所遵循的过程来自于我们的经验。幼儿园老师通常用选择法将孩子们按身高排队。对以随机顺序排列的一组学生，老师反复从组中挑选出最矮的学生并将他或她移到正在形成的按高矮个排列的队列中。这一过程一直持续到所有学生都被移动到有序队列中，如下所示：

//用选择排序算法对类型为T的n元数组进行排序
template<class T>
void SelectionSort(T A[], int n){
    //每遍循环中最小元素的下标
    int smallIndex;
    int i, j;
    //对A[0]..A[n-2]进行排序后，A[n-1]也将有序
    for(i = 0; i < n-1; i++){
        //从下标i开始扫描，将smallIndex置为i
        smallIndex = i;
        for(j = i+1; j < n;  j++){
            //若打开更小元素，则修改smallIndex的值
            if(A[j] < A[smallIndex]){
                smallIndex = j;
            }
        }
        //结束后，将最小元素放入A[i]
        swap(A[i], A[smallIndex]);
    }
}

冒泡排序

1.    比较相邻的前后两个数据，如果前面数据大于后面的数据就将两个数据交换

2.    这样对数组的第0个数据到n-1个数据进行一次遍历后，最大的一个数据就沉到数组第n-1个位置

template<class T>
void BubbliSort(T A[], int n){
    int i, j;
    //最后一次交换时的下标值
    int lastExchangeIndex;
    //i为子表中最后一个元素的下标
    i = n - 1;
    while(i > 0){
        lastExchangeIndex = 0;
        for(j = 0; j < i; j++){
            if(A[j+1] < A[j]){
                swap(A[j], A[j + 1]);
                lastExchangeIndex = j;
            }
        }
        //置i值为最后一次交换发生的下标，继续对A[0]到A[i]排序
        i = lastExchangeIndex;
    }
}

插入排序

插入排序类似于我们所熟悉的要对一串名单进行排序的“洗牌”过程。管理注册者将每个人名写在一个3*5的卡片上，然后按字母顺序重新排列卡片，方法是将卡片往前移直到找到合适的位置。在操作进行过程中，卡片堆的前部是排好序的，而尾部有待处理。我们用含5个整数值的表描述这一过程：A = 50,20,40,75,35

template<class T>
void InsertionSort(T A[], int n){
    int i, j;
    T temp;
    //i标明的子表A[0]到A[i]
    for(i = 1; i < n; i++){
        //用下标j从A[i]往前扫描子表，为A[i]找到适当位置后，将A[i]赋给A[j]
        j = i;
        temp = A[i];
        //若temp<A[j-1]且还未到尽头，继续往前扫描
        while(j > 0 && temp < A[j-1){
            //右移表中元素
            A[j] = A[j-1];
            j--;
        }
        //找到位置，将temp插入
        A[j] = temp;
    }
}

快速排序

与多数排序算法一样，快速排序也是由我们所熟知的经验得来的。若我们要将一摞作业纸按姓名顺序堆放，我们可以用某个中心字符对表进行分割，将作业分为两堆。所有名字小于或等于K的放在一堆，其余的放在另一堆。然后我们再将第一堆又分作两部分。如此继续下去，我们可以将各堆分得越来越小。

template<class T>
void QuickSort(T A[], int low, int high){
    //存放中心索引及其值的局部变量及用于扫描的索引
    T pivot;
    int scanUp, scanDown;
    int mid;
    if(high - low <= 0){
        return;
    }else if(high - low == 1){
        if(A[high] < A[low]){
            swap(A[low], A[high]);
        }
        return;
    }
    //取中心索引并将其值赋给pivot
    mid = (low + high)/2;
    pivot = A[mid];
    //交换pivot及低端元素的值并初始化扫描索引scanUp和scanDown
    swap(A[mid], A[low]);
    scanUp = low + 1;
    scanDown = high;
    //定位错位元素，当scanDown < scanUp时结束
    do{
        //从低端子表往上扫描，当scanUp进入到高端子表或遇到大于pivot的元素时结束
        while(scanUp <= scanDown && A[scanUp] <= pivot){
            scanUp++;
        }
        //从高端子表往下扫描，当scanDown指向的元素小于或等于pivot时停止
        while(pivot < A[scanDown]){
            scanDown--;
        }
        //若两个索引还在各自的子表中，则表示两个元素错位，将两个元素换位
        if(scanUp < scanDown){
            swap(A[scanUp], A[scanDown]);
        }
    }while(scanUp < scanDown);
    //将pivot拷贝到scanDown位置，分开两个子表
    A[low] = A[scanDown];
    A[scanDown] = pivot;
    //若低端子表(low至scanDown-1)有2个或更多个元素，则进行递归调用
    if(low < scanDown - 1){
        QuickSort(A, low, scanDown - 1);
    }
    //若高端子表(scanDown+1至high)有2个或更多个元素，则进行递归调用
    if(scanDown + 1 < high){
        QuickSort(A, scanDown + 1, high);
    }
}

附：冒泡排序所表现的总体性能是最差的