C++模板快速排序和Stooge排序

柔光的暖阳◎ 2022-07-28 01:45 181阅读 0赞

# 快速排序和Stooge排序 #

## 快速排序 ##

### 简介 ###

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。  
步骤为：

> 1.  从数列中挑出一个元素，称为”基准”（pivot），
> 2.  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
> 3.  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

经典算法书上快排采用原地(in-place)排序的方法，其实也有非原地的方法，简单的伪代码如下：

function quicksort(q)
         var list less, pivotList, greater
         if length(q) ≤ 1 {
             return q
         } else {
             select a pivot value pivot from q
             for each x in q except the pivot element
                 if x < pivot then add x to less
                 if x ≥ pivot then add x to greater
             add pivot to pivotList
             return concatenate(quicksort(less), pivotList, quicksort(greater))
         }

--------------------

### 复杂度 ###

最差时间复杂度 Θ(n2)  
最优时间复杂度 Θ(nlogn)  
平均时间复杂度 Θ(nlogn)  
最差空间复杂度 根据实现的方式不同而不同

以上内容整理自**维基百科**

--------------------

### 基于模板的实现 ###

#### **代码** ####

#ifndef MYSORT_H_
    #define MYSORT_H_
    #include <iostream>
    #include <limits>
    namespace MySort{
        ///快速排序
        template <typename T>
        int Partition(T*arr, int p, int r)
        {
            T x = *(arr + r);
            int i = p - 1;
            for (int j = p; j < r; j++)
            {
                if (*(arr + j) <= x)
                {
                    i = i + 1;
                    swap(*(arr + i), *(arr + j));
                }
            }
            swap(*(arr + i+1), *(arr + r));
            return i + 1;
        }
        template <typename T>
        void QuickSort(T*arr, int p, int r)
        {
            if (p < r)
            {
                int q = Partition(arr, p, r);
                QuickSort(arr, p, q - 1);
                QuickSort(arr, q + 1, r);
            }
        }
    }//namespace MySort
    #endif

测试代码

#include <iostream>
    #include "MySort.h"
    using namespace std;
    int main()
    {
    
        int a[] = { 3,2,1,4,5,9,8,7,6 };
        MySort::QuickSort(a, 0, sizeof(a) / sizeof(int)-1 );//由编译器推断型别
        //MySort::QuickSort<int>(a, 0, sizeof(a) / sizeof(int)-1 );//完整写法
    
        for (int i = 0; i < sizeof(a) / sizeof(int); i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
        system("PAUSE");
        return 0;
    }

--------------------

## Stooge（臭皮匠）排序 ##

### 简介 ###

臭皮匠排序（英语：Stooge Sort）是一种低效的递归排序算法，甚至慢于冒泡排序。由于实现形式上与快排类似，也顺带学习了一番。

--------------------

### 实现 ###

*  如果最后一个值小于第一个值，则交换这两个数
 *  如果当前集合元素数量大于等于3：  
    1.使用臭皮匠排序前2/3的元素  
    2.使用臭皮匠排序后2/3的元素  
    3.再次使用臭皮匠排序前2/3的元素

--------------------

### 复杂度 ###

最差时间复杂度 O(nlog3/log1.5)  
最差空间复杂度 O(n)

伪代码如下：

algorithm stoogesort(array L, i = 0, j = length(L)-1)
         if L[j] < L[i] then
             L[i] ↔ L[j]
         if (j - i + 1) >= 3 then
             t = (j - i + 1) / 3
             stoogesort(L, i  , j-t)
             stoogesort(L, i+t, j  )
             stoogesort(L, i  , j-t)
         return L

以上内容整理自**维基百科**

--------------------

### 基于模板的实现 ###

#### **代码** ####

#ifndef MYSORT_H_
    #define MYSORT_H_
    #include <iostream>
    #include <limits>
    namespace MySort{
        ///Stooge排序 （臭皮匠排序）
        template <typename T>
        void StoogeSort(T* arr, int i, int j)
        {
            if (*(arr + i) > *(arr + j))
                swap(*(arr + i), *(arr + j));
            if (i + 1 >= j)   //   j - i  +  1 >=3
                return;
            int k = (j - i + 1) / 3;
    
            StoogeSort(arr, i, j - k);
            StoogeSort(arr, i + k, j);
            StoogeSort(arr, i, j - k);
        }
    }//namespace MySort
    #endif

测试代码

#include <iostream>
    #include "MySort.h"
    using namespace std;
    int main()
    {
    
        int a[] = { 3,2,1,4,5,9,8,7,6 };
    
        MySort::StoogeSort(a, 0, sizeof(a) / sizeof(int) - 1);
        for (int i = 0; i < sizeof(a) / sizeof(int); i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
        system("PAUSE");
        return 0;
    }