排序：快速排序和归并排序

超、凢脫俗 2022-07-27 15:56 219阅读 0赞

#### 快速排序 ####

#### 快速排序递归实现 ####

//快速排序递归实现
    void qsort_once(int *arr, int low, int high)
    {
        if(low >= high)
            return;
        int pivot = arr[low];
        int lowtmp = low, hightmp = high;
        while(lowtmp < hightmp)
        {
            while(lowtmp < hightmp && arr[hightmp] >= pivot)
                hightmp--;
            arr[lowtmp] = arr[hightmp];
            while(lowtmp < hightmp && arr[lowtmp] <= pivot)
                lowtmp++;
            arr[hightmp] = arr[lowtmp];
        }
        arr[lowtmp] = pivot;
        qsort_once(arr, low, lowtmp - 1);
        qsort_once(arr, lowtmp + 1, high);
    }

#### 快速排序一次划分Partition（基于两边指针向中间方法） ####

//一次划分函数Partition ——基于两边向中间方法
    int Partition(int * arr, int low, int high)
    {
        int pivot = arr[low];
    
        while(low < high)
        {
            while(low < high && arr[high] >= pivot) high--;
            arr[low] = arr[high];
    
            while(low < high && arr[low] <= pivot) low++;
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }

#### 快速排序一次划分Partition（基于同向指针向一边方法） ####

//一次划分函数Partition2 ——基于同向前后指针方法
    //原理是两个指针一个用于遍历一个用户记录左边或者右边元素的位置
    //这种方法能够保证在最后找到主元素位置后某一边元素的相对位置不变
    //注意是哪一边元素要求相对位置保持不变，可以通过改变指针方向实现
    int Partition2(int * arr, int low, int high)
    {
        int i = low - 1;        //指向已经放置好的元素,初始为已有元素的前一个元素
        int pivot = arr[high];  //主元素是最后一个元素
        int tmp;
        for(int j = low; j < high; j++)
        {
            if(arr[j] <= pivot)
            {
                i++;
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        tmp = arr[i+1];
        arr[i+1] = pivot;
        arr[high] = tmp;
    
        return i+1;
    }

#### 快速排序非递归实现 ####

//借助Partition函数和栈实现非递归的快速排序
    void Quick_sort(int * arr, int low, int high)
    {
        stack<int> st;
        int index;
        do
        {
            while(low < high)
            {
                index = Partition(arr,low,high);
                if((index - low) <(high - index))
                {
                    st.push(index+1);
                    st.push(high);
                    high = index - 1;
                }
                else
                {
                    st.push(low);
                    st.push(index - 1);
                    low = index + 1;
                }
            }
            if(st.empty()) return;
            high = st.top(); st.pop();
            low = st.top(); st.pop();
        }while(1);
    }

#### Partition的应用（最小的k个数，第k大的数） ####

//利用Patition实现寻找第k大的数
    void getkth(int * arr, int n, int k)
    {
        if(arr == NULL || n < 0 || k < 0 || k > n)
            return;
        int _start = 0, _end = n - 1;
        int index = Partition2(arr,_start,_end);
        while(index != k -1)
        {
            if(k-1 < index)
                _end = index - 1;
            else
                _start = index + 1;
            index = Partition(arr, _start, _end);
        }
        printf("%d\n", arr[index]);
    }

//求较小的k个数 和上面的是一致的，因为第k大的数的左边的数都是比它小的数，也就是要求的数

#### Partition的应用（不同特征数据的一次分类） ####

//区分数列中的两类字符，基于不同的特征
    //实际上就是利用两个指针首尾向中方法进行遍历，分别找到应该交换的位置进行交换
    int PartitionWord(char * arr, int low, int high)
    {
        while(low < high)
        {
            while(low < high && arr[high] <= 'Z' && arr[high] >= 'A') high--;
            while(low < high && arr[low] >= 'a' && arr[low] <= 'z') low++;
    
            int tmp = arr[low];
            arr[low] = arr[high];
            arr[high] = tmp;
        }
    }

//非0元素提前，相对位置不变 逆序方式以保证后面的数字相对位置不变
    void PartitionZero(int * arr, int low, int high)
    {
        int i = high + 1;                //指向已经放置好的元素,初始为已有元素的前一个元素
        int tmp;
        for(int j = high; j >= 0; j--)
        {
            if(arr[j] != 0)
            {
                i--;
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }

#### Partition的应用（荷兰国旗问题） ####

//荷兰国旗问题
    //使用三个指针，两边的两个逐步向中间靠拢，中间那个用于判断元素，
    //注意cur（中间指针只增不减）
    void Helanguoqi(int *arr, int low, int high)
    {
        if(arr == NULL || low < 0 || low > high)
            return;
        int beg = low, cur = low, ed = high;
        int tmp;
        while(arr[beg] == 0)beg++;
        while(arr[ed] == 2)ed--;
        cur = beg + 1;
        while(cur <= ed)
        {
            if(arr[cur] == 2)
            {
                tmp = arr[cur];
                arr[cur] = arr[ed];
                arr[ed] = tmp;
                ed--;     //此时cur不能++ 否则会造成有些置换后还是2但是不会再置换到的情况
            }
            else
            if(arr[cur] == 1)
            {
                cur++;
            }
            else
            {
                tmp = arr[cur];
                arr[cur] = arr[beg];
                arr[beg] = tmp;
                cur++;
                beg++;
            }
        }
    }

### 归并排序 ###

归并排序包括划分和合并，划分比较简单，利用递归的方法很容易实现，关键是合并的操作。合并操作在这里有两种：一种是比较简单的利用额外数组空间进行合并，另一种是在原地进行合并。

#### 利用额外数组空间的Merge函数 ####

//归并排序 Merge函数  递增顺序——借助一个额外的数组空间
    void Merge(int * arr, int low, int mid, int high)
    {
        int * tmp = (int *)malloc(sizeof(int) * (high+1));
        int i, j, k;
        for(k = low; k <= high; k++)
            tmp[k] = arr[k];
        for(i = low, j = mid+1, k = low; i <=mid && j <= high; k++)
        {
            if(tmp[i] < tmp[j])
                arr[k] = tmp[i++];
            else
                arr[k] = tmp[j++];
        }
        while(i <= mid ) arr[k++] = tmp[i++];
        while(j <= high ) arr[k++] = tmp[j++];
    
        free(tmp);
    }

//归并排序 MergeSort
    void MergeSort(int *arr, int low, int high)
    {
        if(low < high)
        {
            int mid = (low + high) / 2;
            MergeSort(arr, low, mid);
            MergeSort(arr, mid + 1, high);
            Merge(arr, low, mid, high);
        }
    }

#### 递归方式实现两个排序单链表的有序合并 ####

两个已经排序的单链表的合并问题，可以利用递归的方法来合并，比较容易理解，也可以不利用递归直接进行合并。

//链表节点
    struct ListNode
    {
        int value;
        ListNode * next;
    };
    
    //合并已经排序的两个链表——基于递归方法
    ListNode* MergeList(ListNode * list1, ListNode* list2)
    {
        if(list1 == NULL)
            return list2;
        if(list2 == NULL)
            return list1;
        ListNode * phead = NULL;
        if(list1->value < list2->value)
        {
            phead = list1;
            phead->next = MergeList(list1->next,list2);
        }
        else
        {
            phead = list2;
            phead->next = MergeList(list2->next, list1);
        }
        return phead;
    }

#### 非递归方式实现两个排序链表的有序合并 ####

//合并已经排序的两个链表——基于非递归的方法
    ListNode* MergeList2(ListNode* list1, ListNode* list2)
    {
        if(list1 == NULL) return list2;
        if(list2 == NULL) return list1;
        ListNode * phead = NULL, *p1,*p11,*p2;
        if(list1->value <= list2->value)
        {
            phead = list1;
            p1 = p11 = phead;
            p2 = list2;
        }
        else
        {
            phead = list2;
            p1 = p11 =phead;
            p2 = list1;
        }
    
        while(p1 != NULL && p2 != NULL)
        {
            while(p1 != NULL && p2 != NULL && p1->value <= p2->value)
            {
                p11 = p1;
                p1 = p1->next;
            }
            p11->next = p2;
            p2 = p2->next;
            p11->next->next = p1;
            p11 = p11->next;    //添加元素之后p11不再是p1的前一个元素了
        }
    
        if(p1 == NULL) p11->next = p2;
        if(p2 == NULL) ;
    
        return phead;
    }

#### 利用原地数组空间的Merge函数 ####

归并排序的原地排序的实现：  
主要思路是利用三个指针：low，mid和high，每次确定前面数组中比后面数组中小的那些数，它们的下一个数下标记为i，然后确定后面那个数组中比前面数组中i下标对应的数要小的数，其长度记为step，它们的下一个数下标为j，此时交换\[i,j-step-1\]和\[j-step,j-1\]两个区间中的数字就得到了有序数组区间\[0,i+step-1\]。然后i不断向后迭代就好了。

交换数组中的两个区间利用的方法是三次逆置，即首先逆置前面的小区间和逆置后面的小区间，最后逆置整个操作的大区间。

所以下面首先定义逆置函数，然后定义对整个操作区间进行操作的函数，最后通过不断确定i,j和step以完成对整个数组的排序。

##### 数组逆置 #####

//Merge函数的原地--同一数组中逆置
    void Reverse(int * arr, int beg, int ed)
    {
        if(arr == NULL || beg < 0 || ed < beg)
            return;
        int i = beg, j = ed, tmp;
        while(i < j)
        {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }

##### 基于数组逆置的数组不同部分交换 #####

//Merge函数的原地--将数组中的两个部分交换位置
    void ReverseTwoPartArray(int * arr, int beg, int mid, int ed)
    {
        Reverse(arr, beg, mid-1);
        Reverse(arr, mid, ed);
        Reverse(arr, beg, ed);
    }

//Merge函数的原地合并，不需要额外申请空间
    void Merge2(int *arr, int beg, int mid, int ed)
    {
        if(arr == NULL || beg < 0 || mid < beg || ed < mid)
            return;
        int i = beg, j = mid;
        int step = 0;
        while(i <= mid - 1 && j <= ed)
        {
            while(i <= mid - 1 && j <= ed && arr[i] <= arr[j] )
                i++;
            step = 0;
            while(i <= mid - 1 && j <= ed && arr[j] < arr[i])
                j++, step++;
            ReverseTwoPartArray(arr,i,j - step, j-1);
            i += step;
        }
    }

//基于Merge函数原地合并的归并排序
    void Mergesort2(int *arr, int low, int high)
    {
        if(low < high)
        {
            int mid = (low+high) / 2;
            Mergesort2(arr,1,mid);
            Mergesort2(arr,mid+1,high);
            Merge2(arr,low,mid+1,high);
        }
    }