排序

直接插入排序

void InsertSort(int a[],int n){
    for(int i=2;i<=n;i++){
        //a[0]为哨兵 
        a[0] = a[i];
        int j;
        for(j=i-1;a[0]<a[j];j--){
            a[j+1] = a[j];
        }
        a[j+1] = a[0];
    }
}

折半插入排序

void InsertSort(int a[],int n){
    for(int i=2;i<=n;i++){
        //a[0]为哨兵  
        a[0] = a[i];
        int low = 1,high = i-1;
        while(low<=high){
            int mid = (low+high)/2;
            if(a[mid]>a[0]) high = mid-1;
            else low = mid+1;
        }
        for(int j=i-1;j>=low;j--){
            a[j+1] = a[j];
        }
        a[low] = a[0];
    }
}

希尔排序

void ShellSort(int a[], int n) {
    for(int d=n/2;d>=1;d/=2){
        for(int i=0;i<d;i++){
            for(int j=i+d;j<=n;j+=d){
                a[0]=a[j];
                int k;
                for(k=j-d;k>=0&&a[0]<a[k];k-=d){
                    a[k+d]=a[k];
                }
                a[k+d]=a[0];
            }
        }
    }
}

选择排序

void SelectSort(int a[],int n){
    for(int i=1;i<=n;i++){
        int tmp=i;
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[tmp]){
                tmp=j;
            }
        }
        swap(a[tmp],a[i]);
    }

}

冒泡排序

void BubbleSort1(int a[], int n) {
    for(int i=1;i<n;i++) {
        bool flag = false;
        for(int j=n-1;j>=i;j--) {
            if(a[j-1]>a[j]) {
                int tmp=a[j-1];
                a[j-1]=a[j];
                a[j]=tmp;
                flag = true;
            }
        }
        if(!flag) return;
    }
}

快速排序

int Partition(int a[],int low,int high){
    int pivot = a[low];
    while(low<high){
        while(low<high&&a[high]>=pivot) high--;
        a[low] = a[high];
        while(low<high&&a[low]<=pivot) low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}
void QuickSort(int a[],int low,int high){
    if(low<high){
        int pivotpos = Partition(a,low,high);
        QuickSort(a,low,pivotpos-1);
        QuickSort(a,pivotpos+1,high);
    }
}

堆排序

void HeadAdjust(int a[],int k,int n){
    a[0] = a[k];
    for(int i=k*2;i<=n;i*=2){
        if(i<n&&a[i]<a[i+1]){
            i++;
        }
        if(a[0]>=a[i]) break;
        else{
            a[k]=a[i];
            k=i;
        }
    }
    a[k] = a[0];
}

//建立大根堆
void BuildMaxHeap(int a[],int n){
    for(int i=n/2;i>=1;i--){
        HeadAdjust(a,i,n);
    }
}

//堆排序
void HeapSort(int a[],int n){
    BuildMaxHeap(a,n);
    for(int i=n;i>1;i--){
        swap(a[i],a[1]);
        HeadAdjust(a,1,i-1);
    }
}

归并排序

void Merge(int a[],int low,int mid,int high){
    for(int i=low;i<=high;i++){
        b[i] = a[i];
    }
    int k=low,i=low,j=mid+1;
    while(i<=mid&&j<=high){
        if(b[i]<=b[j]){
            a[k++] = b[i++];
        }else{
            a[k++] = b[j++];
        }
    }
    while(i<=mid) a[k++] = b[i++];
    while(j<=high) a[k++] = b[j++];
}

void MergeSort(int a[],int low,int high){
    if(low<high){
        int mid = low+high>>1;
        MergeSort(a,low,mid);
        MergeSort(a,mid+1,high);
        Merge(a,low,mid,high);
    }
}