排序算法(二)——希尔、快速、归并

希尔排序(插入排序的改良版)

在希尔排序出现之前，计算机界普遍存在“排序算法不可能突破O(n2)”的观点。希尔排序是第一个突破O(n2)的排序算法，它是简单插入排序的改进版。希尔排序的提出，主要基于以下两点：

1. 插入排序算法在数组基本有序的情况下，可以近似达到O(n)复杂度，效率极高。
2. 但插入排序每次只能将数据移动一位，在数组较大且基本无序的情况下性能会迅速恶化。

算法描述

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行 k 趟排序
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度
   

动图演示

算法实现

在希尔排序的理解时，我们倾向于对于每一个分组，逐组进行处理，但在代码实现中，我们可以不用这么按部就班地处理完一组再调转回来处理下一组,实现时不用循环按组处理，我们可以从第gap个元素开始，逐个跨组处理。

//Donald Shell增量 每次分组减半
void shellSort(int arr[], int len){
    //增量delta，并逐步缩小增量
    for(int delta = len / 2; delta >0; delta /= 2){
        //从第delta个元素开始，逐个对其所在组进行直接插入排序操作
        for(int i = delta; i<len;i++){
            //寻找可以插入的位置
            int pos = i;
            int curVal = arr[i];
            while(pos >= delta && arr[pos-delta] > curVal){
                arr[pos] = arr[pos-delta];
                pos-=delta;
            }
            arr[pos] = curVal;
        }
    }
}

算法特点

1. 希尔排序的增量数列可以任取，需要的唯一条件是最后一个一定为1（因为要保证按1有序）
2. Donald Shell提出的增量，即折半降低直到1,其时间复杂度还是O(n2)。Hibbard经过复杂证明可使得最坏时间复杂度为O(n3/2)
3. Shell排序不是一个稳定的算法

快速排序

快速排序算法知名度较高，对于大数据具有优秀的排序性能和相对简单的算法实现。快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法描述

1. 从序列中挑出一个元素作为基准(pivot)
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区(partition)操作。
3. 递归的把左右两边的字序列进行排序
4. 直到子数组长度为1

动图演示

算法实现

void quickSort(int arr[],int left,int right){
    //left 数组起始下标
    //right 数组结束下标

    //递归终止条件 数组长度为1
    if(left >= right)
        return;
    //执行partition操作，将数组分为两个子数组
    int pivotIndex = partition(arr,left,right);
    //递归调用
    quickSort(arr,left,pivotIndex-1);
    quickSort(arr,pivotIndex,right);
}

int partition(int arr[],int left,int right){
    //选定第一个元素作为基准(可随意)
    int pivot = arr[left];
    //所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面
    while(left <right){
        //采取双指针的方式,移动left和right

        while(left <right && arr[right] >=pivot)
            --right;
        arr[left] = arr[right]; //交换比基准值小的至左边
        while(left <right && arr[left] <=pivot)
            ++left;
        arr[right] = arr[left]; //交换比基准值大的至右边

        //扫描完成，基准到位
        arr[left] = pivot;
        return left;
    }
}

//划分第二方法
int partition(int arr[],int left,int right){
    //随机选中一个元素作为基准arr[p],并放置末尾
    //swap(arr[p],arr[right]);
    //这里直接选择arr[right]作为基准
    int pivot = arr[right];
    //双指针
    //[left,i）均小于等于pivot
    //[i,j)均大于等于pivot
    //[j,right）表示未扫描区间
    int i = left; 
    //扫描除基准外的元素
    for(int j = left;j < right;j++){
        if(arr[j] <= pivot){
            swap(arr[i],arr[j]);
            i++;
        }
    }
    //将基准放置正确位置
    swap(arr[i],arr[right]);
    return i;
}

算法特点

1. 快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放
2. 在最坏状况下时间复杂度(顺序数列)则需要 Ο(n2),平均Ο(nlogn)

归并排序

算法描述

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

动图演示

算法实现

数组排序

void mergeSort(int arr[],int left,int right){
    if(left >= right)
        return;
    int mid = left + (right-left) /2;
    //左数组 [left,mid] 右子数组[mid+1,right]
    mergeSort(arr,left,mid);
    mergeSort(arr,mid+1,right);

    //合并
    merge(arr,left,mid,right);
}
//合并两个有序数组
//左数组 [left,mid] 右子数组[mid+1,right]
void merge(int arr[],int left,int mid,int right){
    //申请空间
    int *p = new int[right-left+1];
    //合并两个子数组
    int i = left,j = mid+1;
    int k = 0;
    while(i<=mid && j<=right){
        p[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <=mid){
        p[k++] = arr[i++];
    }
    while ( j<=right){
        p[k++] = arr[j++];
    }
    //把数据复制回原数组
    for(int i = left;i<=right;i++){
        arr[i] = p[i-left];
    }
    delete []p;
}

链表归并排序

//链表的归并排序
ListNode* sortList(ListNode* head) {
    return mergeSort(head,nullptr);
}
//从头到尾进行排序，返回排序好的头指针
ListNode* mergeSort(ListNode* head,ListNode* tail){
    if(!head)
        return head;

    //只剩最后一个节点,tail不进行排序
    if(head->next == tail){
        head->next = nullptr;
        return head;
    }
    //快慢指针寻找中间
    ListNode* slow = head,*fast =head,*mid = head;
    while(fast != tail){
        slow = slow->next;
        fast = fast->next;
        if(fast != tail)
            fast = fast->next;
    }
    mid = slow;
    return merge(mergeSort(head,mid),mergeSort(mid,tail));
        
}
ListNode* merge(ListNode* list1,ListNode* list2){
    ListNode* dummyHead = new ListNode(0);
    ListNode* pre = dummyHead;
    while(list1 && list2){
        if(list1->val < list2->val){
            pre->next = list1;
            list1 = list1->next;
        }else{
            pre->next = list2;
            list2 = list2->next;
        }
        pre = pre->next;
    }
    if(list1){
        pre->next = list1;
    }else{
        pre->next = list2;
    }
    return dummyHead->next;
}

算法特点

1. 时间复杂度平均Ο(nlogn),对于数组需要O(n)的空间复杂度，对于链表只需要O(1)
2. 常用于给链表排序
3. 因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。