C++实现快速排序

小鱼儿 2022-12-29 09:15 77阅读 0赞

# 思想 #

1.在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素
    中随机选取一个作为基准)，称为基准元素；
    
     2.对待排序的元素进行分区，将比基准元素大的元素放在它的右边，比其小的放在它的左边；
    
     3.对左右两个分区重复以上步骤直到所有元素都是有序的。

# 排序过程 #

1、设置两个指针left和right，一个指向待排数组最左边，一个指向最右边
    2、把left指向的第一个元素取出来，作为基准元素，赋值给一个临时变量tmp，这样left所指向的位置就空出来了；
    3、将right指针向左移动，遇到比tmp小的就停下来，将这个right指针指向的小元素赋值给left所指向的位置，这样right指针所指向的位置就空出来了；
    4、将left指针向右移动，遇到比tmp大的就停下来，将这个left指针指向的大元素赋值给right所指向的位置，这样left指针所指向的位置就空出来了；
    5、重复第3、4步，直到left和right相等
    6、将基准元素tmp赋值给left指向的位置，基准元素归位；
    7、将基准元素左边的子序列和右边的子序列分别进行上述快排过程。

所以，快排有点像“拆东墙补西墙，再拆西墙补东墙”的过程。

# C++实现 #

#include<iostream>
    using namespace std;
    //快排
    void quickSort(int arr[], int _left, int _right) {
        int left = _left;
        int right = _right;
        int temp = 0;
        if (left < right) {   //待排序的元素至少有两个的情况
            temp = arr[left];  //待排序的第一个元素作为基准元素
            while (left != right) {   //从左右两边交替扫描，直到left = right
    
                while (right > left&& arr[right] >= temp)
                    right--;        //从右往左扫描，找到第一个比基准元素小的元素
                arr[left] = arr[right];  //找到这种元素arr[right]后与arr[left]交换
    
                while (left < right && arr[left] <= temp)
                    left++;         //从左往右扫描，找到第一个比基准元素大的元素
                arr[right] = arr[left];  //找到这种元素arr[left]后，与arr[right]交换
    
            }
            arr[right] = temp;    //基准元素归位
            quickSort(arr, _left, left - 1);  //对基准元素左边的元素进行递归排序
            quickSort(arr, right + 1, _right);  //对基准元素右边的进行递归排序
        }
    }
    //主函数
    void main() {
        int arr[] = { 10,5,3,1,7,2,8 };
        
        int length = 0;
        length = sizeof(arr) / sizeof(int);
        cout << "数组长度：" << length << endl;
    
        cout << "排序之前：" << endl;
        for (int i = 0; i < length; i++) {
            cout << arr[i] << endl;
        }
        quickSort(arr, 0, length - 1);
    
        cout << "\n排序之后：" << endl;
        for (int i = 0; i < length; i++) {
            cout << arr[i] << endl;
        }
    
    }

参考：[图解快速排序][Link 1]

[Link 1]: https://www.cnblogs.com/MOBIN/p/4681369.html