常用排序总结

#include <iostream.h>
void InsertSort(int seq[],int len){

    int tem; //辅助空间tem，o(1)

    for(int i=1;i<len;i++)      //从第二个开始找
        if(seq[i]<seq[i-1]){    //如果小于前一个      

            tem = seq[i];       //提取出来
            seq[i] = seq[i-1];  //先后移一格 

            for(int j=i-2;j>=0&&tem<seq[j];j--)//从前两个开始往前找，直到大于等于时停止
                seq[j+1] = seq[j];  //边找边后移
            seq[j+1] = tem;             //放入正确位置

        }
}

void main() {

    int len = 8;
    int seq_test[] = {5,9,8,10,30,1,45,34};

    InsertSort(seq_test,len);

    for(int i=0;i<len;i++)
    cout<<seq_test[i]<<endl;
}

//shell就是用的直接插入思路，只是多加一个增量dk，dk=1时就是直接插入排序（基本有序思想）
void ShellSort(int seq[],int len,int dk){
    int tem;

    for(int i=dk;i<len;i++)
        if(seq[i]<seq[i-dk]){

            tem = seq[i];
            seq[i] = seq[i-dk];
            for(int j=i-2*dk;j>=0&&tem<seq[j];j-=dk)
                seq[j+dk] = seq[j];
            seq[j+dk] = tem;
        }
}

void SelectSort(int seq[],int len){
    int tem,k;      //K为最小值的下标
    for(int i=0;i<len-1;i++){   //总共进行len-1次排序
        k = i;
        for(int j=i+1;j<len;j++)
            if(seq[j]<seq[k])
                k = j;
        if(k!=i){
            tem = seq[i];
            seq[i] = seq[k];
            seq[k] = tem;
        }
    }
}

void HeapAdjust(int seq[],int left,int right){   //左边界，右边界
    int head;       
    head = seq[left];            //要排序的头结点 
    for(int i=left*2;i<=right;i*=2){      //i当作上指针，left当作下指针
        if(i<right&&seq[i]<seq[i+1]) i++;
        if(head>=seq[i]) break;
        seq[left] = seq[i];
        left = i;
    }

    seq[left] = head;
}

void HeapSort(int seq[],int len){
    int tem,i;
    for(i=len/2;i>0;i--)      //将无序二叉树调整为大顶堆
        HeapAdjust(seq,i,len);    
    for(i=len;i>1;i--){       //边排列边调整
        tem = seq[1];
        seq[1] = seq[i];
        seq[i] = tem;

        HeapAdjust(seq,1,i-1);    
    }
}

void BubbleSort(int seq[],int len){

    int tem;

    for(int i=0;i<len-1;i++)  //排序要走的趟次，满足len-1趟即可
        for(int j=0;j<len-1-i;j++)//排序范围，起始0~len-1，且每次减1
            if(seq[j]>seq[j+1]){
                tem = seq[j];
                seq[j] = seq[j+1];
                seq[j+1] = tem;
            }
}

也计你会问：为什么冒泡排序最好情况下时间复杂度为o(n)?因为还可以这样来改进：

void BubbleSort2(int seq[],int len){

    int tem;
    int FLAG;           //增加一位标志

    for(int i=0;i<len-1;i++){
        FLAG = 0;       //每趟初始为0
        for(int j=0;j<len-1-i;j++)
            if(seq[j]>seq[j+1]){
                tem = seq[j];
                seq[j] = seq[j+1];
                seq[j+1] = tem;
                FLAG = 1;  //交换过说明序列无序，置为1
            }
        if(!FLAG)          //为0说明已经排序完成，直接返回
            return;
    }
}

int Partition(int seq[],int low,int high){      //一次划分排序

    int pivotkey = seq[low];     //取最低位为轴点

    while(low<high){             //循环直到low high相遇
        while(low<high&&seq[high]>=pivotkey) high--;     //首先从最高点开始找
        seq[low] = seq[high];
        while(low<high&&seq[low]<=pivotkey) low++;
        seq[high] = seq[low];
    }
    seq[low] = pivotkey;     //最终位置,此时low=high
    return low;              //返回划分界点
}

void QuickSort(int seq[],int low,int high){     //递归直到low=high时结束排序

    int pivotloc;    //划分界点位置

    if(low<high){
        pivotloc = Partition(seq,low,high);
        QuickSort(seq,low,pivotloc-1);
        QuickSort(seq,pivotloc+1,high);
    }
}