排序算法

插入排序(Insertion Sort)

对于nums[n]数组

因为a[0]已自动排序，我们遍历1~ n-1，对i $\in$ [1,n-1]的a[i]进行遍历依次做插入排序。记a[i]=temp。对每一个a[i]，我们对j=i ~ 1进行遍历，若a[j-1]>temp则位置顺延(a[j]=a[j-1]).

*算法分析

时间：O( ${n^2}$ )

空间：O(1)

性质：stable

*code

void insertionsort(int nums[],int len)
{
    for(int i=1;i<len;i++){
        int temp=nums[i];
        int j;
        for(j=i;j>0&&nums[j-1]>temp;j--){
            nums[j]=nums[j-1];
        }
        nums[j]=temp;
    }
}

希尔排序(Shell Sort)

划分数组成为若干子数组，对若干子数组进行插入排序

*算法分析

时间：O( ${n^2}$ )，好的增量可做到O( ${n^{3\over2}}$ ).

空间：O(1)

性质：unstable

*code

void shellsort(int nums[],int len)
{
    int increment;
    for(increment=len/2;increment>0;increment/=2){
        for(int i=increment;i<len;i++){
            int temp=nums[i],j;
            for(j=i;j>=increment;j-=increment){
                if(temp<nums[j-increment]){
                    nums[j]=nums[j-increment];
                }else{
                    break;
                }
            }
            nums[j]=temp;
        }
    }
}

冒泡排序(bubble sort)

通过交换，使较小的数浮到前位

*算法分析

时间：O( ${n^2}$ )

空间：O(1)

性质：stable

*code

void bubblesort(int nums[],int len)
{
    int flag=1;
    for(int i=1;i<len&&flag==1;i++){
        flag=0;
        for(int j=0;j<len-i;j++){
            if(nums[j]>nums[j+1]){
                flag=1;
                swap(nums[j],nums[j+1]);
            }
        }
    }
}

快速排序(quick sort)

选取枢纽元，小于枢纽元和大于枢纽元的部分进行分治排序。

1.枢纽元的选取

选首位元素：对于预排序和反序的序列有高的复杂度O( ${n^2}$ )

*三数中值分割：

选左、中、右三位的中位数作主元

int median3(int nums[],int left,int right)
{
    int center=(left+right)/2;
    if(nums[left]>nums[center]){//三位排序
        swap(nums[left],nums[center]);
    }
    if(nums[left]>nums[right]){
        swap(nums[left],nums[right]);
    }
    if(nums[center]>nums[right]){
        swap(nums[center],nums[right]);
    }
    swap(nums[center],nums[right-1]);//隐藏主元，右二位的数并不会参与swap
    return nums[right-1];
}

2.利用循环完成对序列的分割，即小于主元和大于主元两部分

3.递归分治

void Qsort(int nums[],int left,int right)
{
    int i,j,pivot;

    pivot=median3(nums,left,right);
    i=left+1;//从未排序的部分开始
    j=right-2;
    if(i>j){//递归返回条件
        return;
    }

    while(1){
        while(nums[i]<pivot){
            i++;
        }
        while(nums[j]>pivot){
            j--;
        }
        if(i<j){
            swap(nums[i],nums[j]);
        }else{
            break;
        }
    }

    swap(nums[i],nums[right-1]);//恢复主元位置
    Qsort(nums,left,i-1);
    Qsort(nums,i+1,right);
}

*算法分析

时间：平均O(nlogn)

空间：O(logn)

性质：unstable

选择排序(select sort)

选定一个元素作为基点，遍历后方元素，寻找最小的与基点交换位置

*算法分析

时间：O( ${n^2}$ )

空间：O(1)

性质：unstable

*code:

void selectsort(int nums[],int len)
{
    for(int i=0;i<len;i++){
        int j=i;
        for(int k=i+1;k<len;k++){
            if(nums[k]<nums[j]){
                j=k;
            }
        }
        swap(nums[i],nums[j]);
    }
}

堆排序(heap sort)

利用堆性质的排序。

1.堆的操作，向下调整：

void downadjust(int nums[],int start,int end)
{
    int record=nums[start],j;
    /*按层遍历*/
    for(j=2*start+1;j<=end;j=j*2+1){//由于我们数组是从0开始，那么每一元素元素的子节点是2*x+1
        if(j<end&&nums[j]<=nums[j+1]){//找最大值
            j++;
        }
        if(nums[j]<=record){
            break;
        }
        nums[start]=nums[j];//父节点为该层最大值
        start=j;
    }
    nums[start]=record;
}

2.排序步骤

对于升序，我们选择大根堆。大根堆父节点元素值一定大于等于子节点元素值，根节点是堆的最大值。

首先对序列建堆，我们使用向下调整。从最后一个元素的父节点开始。

建堆完成后，我们要做deletemax并取根节点交换到末位置，通过向下调整以完成deletemax.

void heapsort(int nums[],int len)
{
    for(int i=(len-1)/2;i>=0;i--){
        downadjust(nums,i,len-1);//向下调整建大根堆
    }
    for(int i=len-1;i>0;i--){//每次做deletemax并将max置于队尾
        swap(nums[0],nums[i]);
        downadjust(nums,0,i-1);
    }   
}