欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

快速排序 实现思路及C++实现

程序员文章站 2022-03-15 10:24:52
快速排序实现快速排序思想确定分界点调整区间,将比分界点小的放到分界点左边,比分界点大的放到分界点右边递归处理左右两个区间实现快速排序代码麻瓜思路另开两个数组存放比分界点小的和比分界点大的常规思路:#include #include using namespace std;void quickSort(vector& vec, int l, int r){ if (l >=...

快速排序

实现快速排序思想

  1. 确定分界点
  2. 调整区间,将比分界点小的放到分界点左边,比分界点大的放到分界点右边
  3. 递归处理左右两个区间

实现快速排序代码

麻瓜思路
另开两个数组存放比分界点小的和比分界点大的

常规思路:

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>& vec, int l, int r)
{
    if (l >= r) {
        return;
    }
    
    int x = vec[l];
    int i = l - 1;
    int j = r + 1;
    
    while (i < j) {
        do {
            i++;
        } while (vec[i] < x);
        
        do {
            j--;
        } while (vec[j] > x);
        
        if (i < j) {
            swap(vec[i], vec[j]);
        }
    }
    
    quickSort(vec, l, j);
    quickSort(vec, j + 1, r);
}


int main()
{
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    vector<int> vec(n, 0);
    
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    
    quickSort(vec, 0, n - 1);
    
    for (int i = 0; i < n; i++) {
        cout << vec[i] << " ";
    }
    
    return 0;
}

本文地址:https://blog.csdn.net/weixin_42425796/article/details/108857914