• 周日. 7月 3rd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

C++快速排序

admin

11月 28, 2021

  快速排序作为排序家族里面最为快捷的方式,值得思考。我们将一个数组中的某一个数定为基点,然后通过快速排序按照需求(假设升序),将比基点小的数丢在基点左边,把比基点大的数丢在基点右边这样来将基点数的正确位置找到。接着,我们再对基点两边的数组分别进行快排以达到有序的目的。

  举例实际分析如下:

  int data[6] = {6,2,7,3,8,9};

  int i = left,j = right,key = data[left];

  初始数组为6 2 3 7 8 9,我们将基点数定位6进行第一次比较。

  此时right = 5,left = 0。先从右往左找寻比key小的数,right = 3时找到。将data[ left]赋值为data[right] -> 3 2 7 3 8 9。

  然后从左往右找比key大的数,i = 2时找到。我们将data[right]赋值为data[left] -> 3 2 7 7 8 9。

  左右找寻数的任务已经完成,此时应该将key值放在正确位置去了,但是这个位置是哪里?现在还不知道,因为左右标志位还不等,但是下一次循环开始后,发现left 和 right 在2的地方相等了。所以这个位置应该是2 -> 3 2 6 7 8 9。这样,一次排序完成了。

  现在i 和 j 已经都变成了2而且6的正确位置已经找到了。但是按照算法的思路将这个数组分为左右两部分该怎么办,我们的left和right派上了大用场。从left 到 i – 1为左边部分,从j + 1 到 right则为右半部分,对这两部分进行递归快排最终可得到结果。

//
//  main.cpp
//  test
//
//  Created by MadMarical on 15/11/20.
//  Copyright (c) 2015年 com. All rights reserved.
//

#include <iostream>

using namespace std;

int pData[] = {6,2,7,3,8,9};

void quickSort(int *p,int s,int t)
{
    int left,right;
    int key;
    left = s,right = t;
    key = p[left];
    if (s >= t)
    {
        return;
    }
    while (left != right) //左右标志不等,在数组内寻找
    {
        while (left != right && p[right] >= key) //因为是升序,在数组里从右往左找寻一个比key小的数。
        {
            right--;
        }
        p[left] = p[right];
        while (left != right && p[left] <= key)
        {
            left++;
        }
        p[right] = p[left];
    }
    p[left] = key;
    quickSort(p, s, left - 1);
    quickSort(p, right + 1, t);
}

int main(int argc, const char * argv[])
{
    quickSort(pData, 0, 5);
    
    cout<<pData[0]<<" "<<pData[1]<<" "<<pData[2]<<" "<<pData[3]<<" "<<pData[4]<<" "<<pData[5]<<endl;
    
    return 0;
}

反思:

1.如果使用swap进行交换,在代码理解上会减轻不少。

2.快速排序中的判断方法和递归调用值得深思,网上的许多答案也是模棱两可,还是要自己理解比较靠谱。

  

  

发表评论

您的电子邮箱地址不会被公开。