排序

冒泡排序

基本方法：首先第一趟，把从最后一个元素到第一个元素，相邻两个元素间进行两两比较，把较小的放到前面，这样第一趟结束后就把最小的放到了数组的第一个位置；然后第二趟出去第一个位置的元素（最小的元素），总最后一个到第二个，重复上面操作；然后进行n-1趟，至此就把所有数据都完成了排序。

基本的冒泡排序算法

void BubbleSort(int V[], int n){
    //对数组V中的n个元素进行排序，执行n-1趟，第i趟对V[n-1]~V[i]起泡
    for(int i = 1; i < n; i++){    //对1~n-1，逐步缩小待排序列
        for(int j = n-1; j>=i; j--){    //反向检测，检查是否逆序
            if(V[j-1>V[j]){                //发生逆序，交换元素的值
                int temp = V[j-1];
                V[j-1] = V[j];
                V[j] = temp;
            }
        }
    }
}

改进的冒泡排序算法

上面的排序若中间某一趟已经排好序了，但是还是要继续循环检测，现在加一个flag标志来标识某一趟是否发生数据交换，若没发生交换说明已经排好，结束排序。

void BubbleSort(int V[], int n){
    bool flag;
    //对数组V中的n个元素进行排序，执行n-1趟，第i趟对V[n-1]~V[i]起泡
    for(int i = 1; i < n; i++){    //对1~n-1，逐步缩小待排序列
        flag = false;
        for(int j = n-1; j>=i; j--){    //反向检测，检查是否逆序
            if(V[j-1>V[j]){                //发生逆序，交换元素的值
                int temp = V[j-1];
                V[j-1] = V[j];
                V[j] = temp;
                flag = true;            //标志这一趟发生了交换数据
            }
        }
        if(flag == false) return;        //说明上一次反向检测没有发生交换，说明已经排序完成
    }
}

插入排序

基本思想：每一步将待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上去，直到所有元素全部插入为止。

void InsertSort(int L[], int left, int right){
    int temp,i,j;
    for(i = left+1; i <= right; i++){
        if(L[i] < L[i-1]){        //若某一次比较出现后面的元素比前面的小，则依次往前比较寻找停在第一个比它小的元素前面，或直到最左边
            temp = L[i];
            j = i-1;
            do{
                L[j+1] = L[i];
                j--;
            }while(j>=left && temp<L[j]);
            L[j+1] = temp;
        }
    }
}

折半插入排序

基本思想：设在数据表中有一个元素序列V[0],V[1],...V[n-1]。其中V[0],V[1]...V[n-1]是已经排好序的元素。在插入V[i]时利用折半搜索法寻找插入的位置

void BinaryInsertSort(int L[], int left, int right){
    //利用折半搜索，按L[i]在L[left]到L[i-1]中查找L[i]应插入的位置，再空出这个位置进行插入
    int temp;
    int i,low,high,middle,k;
    for(i = left+1; i<=right;i++){
        temp = L[i];
        low = left;
        high = i-1;
        while(low<=high){        //利用折半搜索插入位置
            middle = (low+high)/2;    //取中点
            if(temp<L[middle])  high = middle-1;    //向左缩小空间
            else  low = middle+1;            //否则向右缩小空间
        }
        for(k=i-1; k>=low;k--)        //成块移动，空出插入的位置
            L[k+1] = L[k];
        L[low] = temp;                //插入
    }
}

希尔排序

基本思想：设待排序元素序列有n个元素，首先取一个整数gap<n作为间隔，将全部的元素分为gap个子序列，所有距离为gap的元素放在放在同一个子序列中，在每一个子序列中分别施行直接插入排序。然后缩小间隔gap，重复上述的子序列划分和排序工作，直到最后gap==1，将所有的元素放在一个序列中排序为止。

void Shellsort(int L[], int left, int right){
    int i,j,gap = right-left+1;
    int temp;
    do{
        gap = gap/3+1;        //求下一增量
        for(i = left+gap; i<=right; i++){    //各自序列交替处理（各序列进行直接插入排序）
            if(L[i]<L[i-gap]){                //逆序
                temp = L[i];
                j = i-gap;
                do{
                    L[j+gap] = L[j];
                    j = j-gap;
                }while(j>=left && temp<L[j]);
                L[j+gap] = temp;
            }
        }
    }while(gap>1);
}

排序