网站 › 『编程语言区』 › 快速排序——新手笔记

rain-xuan 发表于 2021-4-27 22:28

快速排序——新手笔记

本帖最后由 rain-xuan 于 2021-4-28 15:05 编辑

## 快速排序算法初探

### 看图说话

#### 图


#### 说话

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,i = left+1,j=right;
    while(true)
    {
      while(i<=j&&a<=pivot)
      {
            i++;
      }
      while(i<=j&&a>=pivot)
      {
            j--;
      }
      if(i>=j)
      {
            break;
      }
      int temp = a;
      a = a;
      a = temp;
    }
    a = a;
    a = 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);
    for(int i=0;i<right;i++)
    {
      cout << a << "\t";
    }
    cout << endl;
    QuickSort(a,left,right-1);
    for(int i=0;i<right;i++)
    {
      cout << a << "\t";
    }
    cout << endl;
    return 0;
}
```

### 运行结果


### 补充字符串排序

```
#include <iostream>
#include <string>
using namespace std;
int partition(string a[],int left,int right)
{
    string pivot = a;
    int i = left + 1,j = right;
    while(true)
    {
      while(i<=j&&a<=pivot)
      {
            i++;
      }
      while(i<=j&&a>=pivot)
      {
            j--;
      }
      if(i>=j)
      {
            break;
      }
      string temp = a;
      a = a;
      a = temp;
    }
    a = a;
    a = 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);
    int left = 0;
    for(int i=0;i<right;i++)
    {
      cout << str << "\t";
    }
    cout << endl;
    QuickSort(str,left,right-1);
    for(int i=0;i<right;i++)
    {
      cout << str << "\t";
    }
    cout << endl;
    return 0;
}
```

### 运行结果


drophair 发表于 2021-4-27 22:47

代码格式化一下吧，看的有点头晕{:1_901:}

sjt5396 发表于 2021-4-28 06:34

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

rain-xuan 发表于 2021-4-28 13:42

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

查看完整版本: 快速排序——新手笔记