【C++快速排序学习总结】

算法图解：

情况1：当前值小于所指向值

情况2：当前值大于所指向值

情况3：当前值等于所指向值

---

代码

遇到的问题：partition返回中间段的左右边界数据，选用结构体进行返回
参考左神代码编写

#include 
#include 
using namespace std;

struct mydata
{
    int position1 = 0;  //The left border of the middle area
    int position2 = 0;  //The right border of the middle area
};

void swap(int arr[], int i, int j)
{
    int temp = 0;
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

mydata partition(int arr[], int L, int R)
{
    int less = L - 1;
    int more = R;

    while (L < more)
    {
        if (arr[L] < arr[R])
        {
            swap(arr, ++less, L++);
        }
        else if (arr[L] > arr[R])
        {
            swap(arr, --more, L);
        }
        else
        {
            L++;
        }
    }
    swap(arr, more, R);
    mydata p;
    p.position1 = less + 1;
    p.position2 = more;
    // p[1] is the right boundary of the left interval
    // p[2] is the right boundary of the left interval
    return p;
}

void quicksort(int arr[], int L, int R)
{
    if (L < R)
    {
        srand((int)time(NULL));               // random number seeds
        int ran = L + (rand() % (R - L + 1)); // Generate a random number between L and R
        swap(arr, ran, R); // Choose ran and compare it with other numbers
        mydata m;
        m = partition(arr, L, R);
        quicksort(arr, L, m.position1 - 1);
        quicksort(arr, m.position2 + 1, R);
    }
}

void print(int a[], int len)
{
    cout << "The sort is:" << endl;
    for (int i = 0; i < len; i++)
    {
        cout << a[i] << " ";
    }
}

void kuaipai()
{
    int arr[] = {2, 5, 6, 7, 8, 9, 4, 1};
    int len = sizeof(arr) / sizeof(arr[0]);
    quicksort(arr, 0, len - 1);
    print(arr, len);
}

int main()
{
    kuaipai();
    return 0;
}

---

TIPS：

srand((int)time(NULL)); 产生随机数种子要用包含头文件.
L + (rand() % (R - L + 1)); // 产生[L,R]中的随机数。

---

算法思路：

递归方式，用荷兰国旗方法把原数据分成三段，左端小于标杆值，中间等于标杆值，右端大于标杆值。

利用指针从左到右比较当前值与标杆值的大小，小的放左端，大的放右端，直到所有值都比较完。

中间与标杆值相等的数就正确排序了。

然后将得到的数据左端和右端分别进行递归，则可将全部数据进行正确排序。

随机选取标杆值用来优化算法的时间复杂度，时间复杂度：O(N*logN)