交换排序

刺骨的言语ヽ痛彻心扉 2022-06-13 08:13 157阅读 0赞

冒泡排序就是交换排序的一种，一趟趟将最大数或者最小数冒在最后面。  
![这里写图片描述][SouthEast]

void BubbleSort(int *arr,int n)
    {
        int end = n - 1;
        while (end > 0)
        {
            bool flag = false;
            for (int i = 0; i < end; ++i)
            {
                if (arr[i]>arr[i + 1])
                {
                    swap(arr[i], arr[i + 1]);
                    flag = true;
                }
            }
            if (!flag)
            {
                break;
            }
            --end;
        }
    }

加一个标志位进行一次优化  
快速排序  
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。  
递归转换成子问题的一个过程  
![这里写图片描述][SouthEast 1]  
方法一  
左右指针法：一个从头开始，一个从尾开始，选取尾的数作为key值，然后两个指针开始走，头指针遇到比key值大的就停下来，为指针遇到比key值小的就停下来，然后头指针停下来的数和尾指针停下来的数进行交换，交换完成之后头指针和尾指针继续一个找比key大的数，一个找比key小的数，头指针大于等于尾指针的时候本次循环结束，此时头指针指向的数一定是比key值大的数，然后再将头指针指向的数和key所在的位置值进行交换，此时key左边的数一定是小于或等于key的，key右边的数一定是大于或等于key的。在进行比较的时候一定要至少一个加上等号否则如果相等头指针和尾指针都不走了，就会陷入死循环。  
![这里写图片描述][SouthEast 2]

int PartSort(int*arr,int left,int right)
    {
        int begin = left;
        int end = right;
        int tmp = arr[end];
        while (begin < end) { while (begin<end&&arr[begin] <= tmp) { ++begin;
            }
            while (begin<end && arr[end]>=tmp) { --end;
            }
            swap(arr[begin], arr[end]);
        }
        swap(arr[begin], arr[right]);
        return begin;
    }

方法二  
挖坑法的思想其实和左右指针法一样，不过他不想左右指针法直接是先让头指针找到比key大的再继续让尾指针找到比它小的，之后再直接将两个进行交换。而挖坑法是先确定最左或者最右作为1个坑，然后让头指针开始找到一个比key大的就放入坑中，此时头指针指向的位置又可以作为一个新坑。让后让尾指针找到一个比key小的停下来，然后放到头之前头指针停下来的创造的坑中，最后头指针和尾指针相遇的时候那么他们此时指向同一个坑，跳出循环，将之前最右面或者最左面的那个数取出来入坑，即一趟循环已经结束。  
![这里写图片描述][SouthEast 3]

int PartSort1(int*arr,int left,int right)
    {
        int begin = left;
        int end = right;
        int tmp = arr[end];
        while (begin < end) { while (begin < end&&arr[begin] <= tmp) { ++begin;
            }
            arr[end] = arr[begin];
            while (begin < end&&arr[end] >= tmp) { --end;
            }
            arr[begin] = arr[end];
        }
        arr[begin] = tmp;
        return begin;
    }

方法三  
前后指针法：一个prev指针和一个cur指针如果arr\[cur\]比key值小就停下来然后++prev再判断prev==cur?如果不等于就交换，交换之后cur就继续走。如果大于key就直接++cur.  
![这里写图片描述][SouthEast 4]  
![这里写图片描述][SouthEast 5]  
![这里写图片描述][SouthEast 6]

int PartSort2(int *arr, int begin, int end)
    {
        int cur = begin;
        int prev = cur - 1;
        int key = arr[end];
        while (cur < end)
        {
            if (arr[cur] < key)
            {
                ++prev;
                if (prev != cur)
                {
                    swap(arr[prev], arr[cur]);
                }
            }
                ++cur;
        }
        swap(arr[++prev], arr[end]);
        return prev;
    }

快速排序退化它的时间复杂度为O（N2）  
但是快速排序在这里的时间复杂度并不是根据最坏的来统计，因为为了避免快速排序出现最坏的情况加了许多情况对其进行优化因此快速排序我们认为它取最好的时间复杂度O(N\*lgN)  
比如小区间优化法，三数取中法  
小区间优化法的思想：假如划分的区间小于13，那么我们认为不需要用快排序来实现，因为递归也是需要付出代价的，这样反而效率低，因此我们选择直接插入排序来解决。

三数取中法：  
由于快速排序可能在划分的时候它的end-begin可能是最大值或者最小值也可能是接近于最大值或最小值，而在这种情况下快速排序它的时间复杂度就可能接近于O(N2)为了避免这种情因此我们都选择三个数里面区最终中间的那个数。

int GetMiddle(int*arr, int left,int right)
    {
        int middle = left + ((right - left) >> 1);
        if (arr[middle] < arr[right])
        {
            if (arr[middle]>arr[left])
            {
                return middle;
            }
            else
            {
                if (arr[left] > arr[right])
                {
                    return right;
                }
                else
                {
                    return left;
                }
            }
        }
        else
        {
                if (arr[middle] < arr[left])
                {
                    return middle;
                }
                else
                {
                    if (arr[left]>arr[right])
                    {
                        return left;
                    }
                    else
                    {
                        return right;
                    }
                }
            }
    }

void QuickSort(int *arr, int begin,int end) { if (begin >= end) { return;
        }
        else
        {
                int div = PartSort(arr, begin, end);
                QuickSort(arr, begin, div - 1);
                QuickSort(arr, div + 1, end);
        }
    }

将快速排序转换成非递归的（借助栈来完成）

void QuickSortNR(int*arr, int begin, int end)
    {
        int left = begin;
        int right = end;
        stack<int>sk;
        sk.push(right);
        sk.push(left);
        int div = 0.;
        while (!sk.empty())
        {
            left = sk.top();
            sk.pop();
            right = sk.top();
            sk.pop();
            if (left >= end)
            {
                break;
            }
            div=PartSort(arr, left, right);
            if (div + 1 < right)//只有当子区间的个数大于1的时候才需要划分
            {
                sk.push(right);
                sk.push(div + 1);
            }
            if (left < div - 1)
            {
                sk.push(div - 1);
                sk.push(left);
            }
        }
    }

[SouthEast]: /images/20220613/f817565c8c454f808f1e813239aee827.png
[SouthEast 1]: /images/20220613/c6776b8a59bb40648be34f424a5c1378.png
[SouthEast 2]: /images/20220613/a68589e7cd9841ab8d337514c02d212c.png
[SouthEast 3]: /images/20220613/632ce5502bd94145a5b4f424ff637c85.png
[SouthEast 4]: /images/20220613/50c1910c77fa47e4a92cbab1306278e0.png
[SouthEast 5]: /images/20220613/7760c14c50d844868d55ac0b90ce453f.png
[SouthEast 6]: /images/20220613/7e0b16ee495a42368105cb2ef882f6be.png