快速排序——新手笔记

rain-xuan

快速排序算法初探

看图说话

图

说话

1. 思想

   • 快速排序以我的理解就是先随意选择一个初始值，为了方便，一般是选择最左边的值，也就是图中的target.然后通过分割实现target的左边值都小于等于target，右边值都大于等于target.

2. 具体实现步骤

   2.1 分割的实现

   • 确定了target之后，我们可以创建两个指针，left指针初始指向target+1的位置，right指针指向数组尾部
   • 以i<=j为前提。当以i为下标的数组元素大于target,并且以j为下标的数组元素小于target时，交换i,j指向的数组元素值
   • 如果上面后一句条件不成立，i++，j--
   • 如果i>=j时，交换target与j指向的数组元素。然后返回小标j

3. 递归

   • 有了分割的思想，思考发现，可以用递归不断重复，直到数组有序。

代码

#include <iostream>
using namespace std;
int partition(int a[],int left,int right)
{
    int pivot = a[left],i = left+1,j=right;
    while(true)
    {
        while(i<=j&&a[i]<=pivot)
        {
            i++;
        }
        while(i<=j&&a[j]>=pivot)
        {
            j--;
        }
        if(i>=j)
        {
            break;
        }
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    a[left] = a[j];
    a[j] = pivot;
    return j;
}

void QuickSort(int a[],int left,int right)
{
    if(left < right)
    {
        int target = partition(a,left,right);
        QuickSort(a,left,target-1);
        QuickSort(a,target+1,right);
    }
}

int main()
{
    int a[]={2,7,1,0,3,9};
    int left = 0;
    int right = sizeof(a)/sizeof(a[0]);
    for(int i=0;i<right;i++)
    {
        cout << a[i] << "\t";
    }
    cout << endl;
    QuickSort(a,left,right-1);
    for(int i=0;i<right;i++)
    {
        cout << a[i] << "\t";
    }
    cout << endl;
    return 0;
}

运行结果

补充字符串排序

#include <iostream>
#include <string>
using namespace std;
int partition(string a[],int left,int right)
{
    string pivot = a[left];
    int i = left + 1,j = right;
    while(true)
    {
        while(i<=j&&a[i]<=pivot)
        {
            i++;
        }
        while(i<=j&&a[j]>=pivot)
        {
            j--;
        }
        if(i>=j)
        {
            break;
        }
        string temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    a[left] = a[j];
    a[j] = pivot;
    return j;
}
void QuickSort(string a[],int left,int right)
{
    if(left < right)
    {
        int center = partition(a,left,right);
        QuickSort(a,left,center-1);
        QuickSort(a,center+1,right);
    }
}
int main()
{
    string str[] = {"3.txt","6.txt","a.md","1.pptx","7.docx"};
    int right = sizeof(str)/sizeof(str[0]);
    int left = 0;
    for(int i=0;i<right;i++)
    {
        cout << str[i] << "\t";
    }
    cout << endl;
    QuickSort(str,left,right-1);
    for(int i=0;i<right;i++)
    {
        cout << str[i] << "\t";
    }
    cout << endl;
    return 0;
}

运行结果

drophair

代码格式化一下吧，看的有点头晕

sjt5396

这个能进行彩票号码的排序吗

rain-xuan

drophair 发表于 2021-4-27 22:47
代码格式化一下吧，看的有点头晕

好的，已经优化