C++快速排序

内容简介：快速排序是基于分治思想的排序算法，通过这种策略把列表分为两个子列，重复该过程。是由东尼·霍尔提出，在平均状况下，排序N个数据要O(nlogn)次比较，在最坏情况下则需要O(n^2)，但退化成冒泡的情况比较少见，快速排序比其他排序算法通常情况是最佳的，因为内部使用的循环在很多平台都有优化。快速排序的步骤很简单：在维基百科上的这张图可以很直观的展示快速排序的过程

int Division(int a[], int left, int right) {
    int base = a[left]; // 取第一个数为基准
    while (left < right) {
        while (left < right && a[left] > base) {
            // 从右向左找第一个比基准小的元素
            --right;
        }
        a[left] = a[right]; // 交换位置，把小元素放在左侧

        while (left < right && a[left] < base) {
            // 从左向右找第一个比基准大的元素
            ++left;
        }
        a[right] = a[left]; // 交换位置，把大元素放在右侧
    }
    a[left] = base;
    return left;
}

void quick_sort(int a[], int left, int right) {
    if (left < right) {
        int index = Division(a, left, right); //对列表进行分割
        quick_sort(a, left, i -1); //对左侧进行排序
        quick_sort(a, i + 1, right); //对右侧进行排序
    }
}

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

关注我们，获取更多IT资讯^_^

查看所有标签

• 图形化排序算法比较：快速排序、插入排序、选择排序、冒泡排序
• 排序算法下——桶排序、计数排序和基数排序
• 算法之常见排序算法-冒泡排序、归并排序、快速排序
• 【JS面试向】选择排序、桶排序、冒泡排序和快速排序简介
• 计数排序vs基数排序vs桶排序
• 排序算法--冒泡排序

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。