算法-排序

2017-06-28

线性表的排序

各种排序算法性能比较

希尔排序需要根据步伐大小决定,基数排序需要r个队列,d趟分配和收集

算法种类	最好情况	平均情况	最坏情况	空间复杂度	是否稳定
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	是
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	是
简单选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	否
希尔排序				O(1)	否
快速排序	O(nlog2(n))	O(nlog2(n))	O(n^2)	O(nlog2(n))	否
堆排序	O(nlog2(n))	O(nlog2(n))	O(nlog2(n))	O(1)	否
2-路归并排序	O(nlog2(n))	O(nlog2(n))	O(nlog2(n))	O(n)	是
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	是

插入排序

直接插入排序

//时间复杂度为o(n^2),count为待排序数组大小,假设从小到大排序
void InsertSortDir(ElemType number[],int count){
    int current;    //从第1个开始，扔到current前面进行排序
    int change=0;
    int changenumber;
    for(current=1;current<count;current++){
        if(number[current]>number[current-1]){ //如果比前面大，则这次已经在正确位置上，不必插入，跳过
            while(change<current&&number[change]<number[current]){
                change++;   //找到待插入元素
            }
            changenumber = number[current];
            for(int j=change+1;j<=current;j++){  //交换后面的位置
                number[j]=number[j-1];
            }
            number[change] = changenumber;  //插入待插入元素
            change = 0;
        }
    }
}

折半插入排序

//时间复杂度为o(n^2),count为待排序数组大小,假设从小到大排序
void InsertSortRed(ElemType number[],int count){
    int current;    //从第1个开始，扔到current前面进行排序
    int change=0;
    int changenumber;
    for(current=1;current<count;current++){
        if(number[current]>number[current-1]){ //如果比前面大，则这次已经在正确位置上，不必插入，跳过
            int low = 0,high = current-1;
            int mid = 0;
            while(low<=high){//查找方式变为折半
                mid = (low+high)/2;
                if(number[mid]>number[current]){
                    high = mid-1;
                }else{
                    low = mid+1;
                }
            }
            change = mid;   //待插入元素位置
            changenumber = number[current];
            for(int j=change+1;j<=current;j++){  //交换后面的位置
                number[j]=number[j-1];
            }
            number[change] = changenumber;  //插入待插入元素
            change = 0;
        }
    }
}

希尔插入排序

//对于希尔排序，前后记录增量为dk,不为1,len为步长
void ShellSort(ElemType number[],int count,int len){
    int change = 0;
    int changenumber = 0;
    for(int dk=len/2;dk>=1;dk=dk/2){
        for(int i = dk;i<2*dk;i++){
            if(number[i]<number[i-dk]){ //相等，则在正确的位置上
                while(change<i&&number[change]<number[i]){
                    change+=dk;   //找到待插入元素
                }
                changenumber = number[i];
                for(int j=change+dk;j<=i;j+=dk){  //交换后面的位置
                    number[j]=number[j-dk];
                }
                number[change] = changenumber;  //插入待插入元素
                change = i-dk;
            }
        }
    }
}

交换排序

冒泡排序

//时间复杂度为o(n^2)，举例从后往前升序冒泡
void BubbleSort(ElemType number[],int count){
    int i=0;
    int temp=0;
    bool changed=true;
    while(i<count&&changed){
        changed=false;  //本趟排序默认没发生交换
        for(int j=count-1;j>i;j--){ //从前往后则j=0;j<count-i-1;j++，然后比较j与j+1
            if(number[j]<number[j-1]){
                changed = true;
                temp = number[j];   //交换元素
                number[j]=number[j-1];
                number[j-1]=temp;
            }
        }
        i++;
    }
}

快速排序

//时间复杂度为o(log2(n))
int Pratition(ElemType number[],int low,int high){
    ElemType pivot = number[low];   //将第一个元素作为轴,这个可以任意,不同情况下取轴可不同
    while(low<high){
        while(low<high&&number[high]>=pivot){
            high--; //将比pivot小的元素放在右侧
        }
        //跳出，说明number[high]<pivot，需要把其放在左侧
        number[low]=number[high];   //第一次的low被记录在pivot里，后续的low记录在前一次的high中
        while(low<high&&number[low]<=pivot){
            low++;
        }
        //跳出,说明number[low]>pivot,需要放在右侧
        number[high]=number[low];   //上一次的high已经存入low，可以直接替换
    }
    number[low]=pivot;  //放回其正确位置
    return low;
}
void QuickSort(ElemType number[],int low,int high){
    if(low<high){
        int pivotpos=Pratition(number,low,high);    //划分，其中pivotpos左侧小于其值，右侧大于，pivotpos为正确的位置
        QuickSort(number, low, pivotpos-1);
        QuickSort(number, pivotpos+1, high);
        
    }
}

选择排序

简单选择排序

//时间复杂度为o(n^2),依次找出最小或最大的
void SelectSort(ElemType number[],int count){
    int minindex = 0;
    int temp = 0;
    for(int i=0;i<count;i++){
        minindex = i;
        for(int j=i+1;j<count;j++){
            if(number[j]<number[minindex]){ //找到最小的那个
                minindex = j;
            }
        }
        temp = number[i];
        number[i]=number[minindex];
        number[minindex] = temp;
    }
}

堆排序

//向下调堆,用于大顶堆
void AdjustDown(ElemType number[],int i,int count){
    int temp = number[i];
    for(int j=2*i+1;j<count;j=2*j+1){   //沿着交大打子节点向下筛选
        if(j+1<count&&number[j]<number[j+1]){   //取左右子节点交大的一个
            j++;
        }
        if(temp>number[j]){ //父节点大于所有子节点，不需要改变
            break;
        }else{  //否则交换位置
            number[i]=number[j];    //大的一个子节点，放在父节点位置，小的父节点下移
            i=j;    //即现在判断的新父节点，为刚刚降下来的那个子节点位置，向下寻找新的次大值
        }
    }
    number[i]=temp;  //最终位置放入开始判断的那个值
}
//在堆栈中删除元素，即将删除的元素与堆底对换，然后向下调整一次替换元素位置
//向上调堆,用于向堆栈中插入元素
void AdjustUp(ElemType number[],int i,int count){
    int temp = number[i];
    int j = (i+1)/2;    //j为i的父亲节点
    while(j>=0&&number[j]<temp){    //父节点比子节点小，父节点下移
        number[i]=number[j];    //子节点被父节点替代
        i=j;
        j = (i+1)/2;    //继续往上调
    }
    number[j]=temp; //找到正确位置
}
//建立大顶堆
void BuildMaxHeap(ElemType number[],int count){
    for(int i=count/2;i>=0;i--){ //从i=[n/2]~1反复调整堆，此为父节点数量
        AdjustDown(number,i,count);
    }
}
//时间复杂度为o(nlog2(n)),堆用数组记录,从number[0]开始记录,每次排序获得最大值
void HeapSort(ElemType number[],int count){
    BuildMaxHeap(number, count);
    int temp = 0;
    //每次number[0]都是当前排序最大的值，放入倒数便可
    for(int i=1;i<count-1;i++){
        temp = number[0];
        number[0] = number[count-i];
        number[count-i] = temp;
        //新堆只有堆顶元素混乱，其他有序，只要向下排一次便可
        AdjustDown(number, 0, count-i);
    }
}

归并排序

2-路归并排序的递归实现

int count;  //数组大小
ElemType *numbertemp = (ElemType *)malloc((count+1)*sizeof(ElemType));  //辅助数组，用于存结果
void Merge(ElemType number[],int low,int mid,int high){
    //number[low~mid]与number[mid~high]各自有序，现在进行归并
    for(int i=low;i<high;i++){
        numbertemp[i] = number[i];
    }
    int i=low,j=mid+1;
    int k=low;
    while(i<mid&&j<=high){
        if(numbertemp[i]<numbertemp[j]){
            number[k] = numbertemp[i];
            i++;
            k++;
        }else{
            number[k] = numbertemp[j];
            j++;
            k++;
        }
    }
    while (i<=mid) {    //左侧没有复制完
        number[k]=numbertemp[i];
        k++;
        i++;
    }
    while (j<=high) {    //右侧没有复制完
        number[k]=numbertemp[j];
        k++;
        j++;
    }
}
//时间复杂度为o(nlog2(n)),此处的hign为最后一个元素下标
void MergeSort(ElemType number[],int low,int high){
    if(low<high){
        int mid = (low+high)/2; //从中间划分成2个子序列
        MergeSort(number, low, mid);    //递归左侧
        MergeSort(number, mid+1, high); //递归右侧
        Merge(number,low,mid,high); //进行归并
    }
}