快速排序(Quicksort)是对冒泡排序的一种改进。由C.
A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
c++代码实现
int partition(int* array, int left, int right)
{
int index = left;
int pivot = array[index];
swap(array[index], array[right]);
for (int i=left; i<right; ++i)
{
// ascending sort
if (array[i] < pivot)
{
swap(array[index++], array[i]);
}
}
swap(array[right], array[index]);
// index is pivot's position in array
return index;
}
void qsort(int* array, int left, int right)
{
if (left >= right)
{
return;
}
int index = partition(array, left, right);
qsort(array, left, index - 1);
qsort(array, index + 1, right);
}
int main(int argc, char* argv[])
{
int arr[] = { 23, 24, 1, 3, 32 };
qsort(arr, 0, 4);
for (int i=0; i<5; ++i)
cout << arr[i] << " ";
cout << endl;
system("pause");
return 0;
}
改进的partition函数,每次分治逻辑中减少一次交换操作
int partition(int* array, int left, int right)
{
int index = left + 1;
int pivot = array[left];
for (int i=left + 1; i<=right; ++i)
{
// ascending sort
if (array[i] < pivot)
{
swap(array[index++], array[i]);
}
}
swap(array[left], array[index - 1]);
// index is pivot's position in array
return index - 1;
}
分享到:
相关推荐
排序法 - 改良的选择排序 87 37.Algorithm Gossip: 快速排序法(一) 92 38.Algorithm Gossip: 快速排序法(二) 94 39.Algorithm Gossip: 快速排序法(三) 96 40.Algorithm Gossip: 合并排序法 99 ...
karatusuba's algorithm 计算乘积 从键盘任意输入N个整数 排序后 二叉搜索查询 从键盘输入的某个任意整数的序号...键盘输入N个数 快速排序 将数组的某一段元素进行划分,小的在左边,大的在右边 键盘输入N个数 归并排序
算法导论排序算法C++实现。被算法导论优美的叙述折服,用C++实现一下加深理解
排序算法可视化工具 :fire: ... :check_mark_button: 气泡排序 :check_mark_button: 插入排序 :check_mark_button: 选择排序 :check_mark_button: 快速排序 :check_mark_button: 合并排序 :check_mark_button: 堆排序
各种排序算法java实现:插入排序、冒泡排序、选择排序、Shell排序、快速排序、改进后的快速排序、归并排序、改进后的归并排序、堆排序!
输入若干组长度各异的待排序列,分别用快速排序算法和改进的枢轴元素三者取中算法对待排序列进行排序, 当待排子序列长度已小于 20时,改用直接插入排序,利用时间函数验证三者取中算法在效率上的提高。 (提示: 待...
快速排序 归并排序 壳排序 堆排序 基数排序 用法 var SortAlgorithm = require ( 'sortAlgorithm' ) ; var sort = new SortAlgorithm ( ) ; sort . bubbleSort ( [ 3 , 1 , 2 , 5 , 4 ] ) ; // return [1,2,3,4,5] ...
java笔试题算法 AlgorithmCode ...使用三向切分快速排序,实际应用中可能出现的某些分布的输入能够达到线性级别,而其它排序算法仍然需要线性对数时间。 LeetCode 1-100 101-200 201-300 301-400 4
常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: 关于时间复杂度: 平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。...
使用c++实现常见的排序算法,包括冒泡排序,快速排序,直接插入排序,带有完整注释
排序算法这是尝试构建包含所有针对Ruby的排序算法的gem。已实施排序: 气泡插入快的选拔壳去做波哥鸡尾酒梳子堆合并快速到位侏儒
下一个快速排序快速排序下一个。安装npm install -S @jswork/next-quick-sort用法import '@jswork/next-quick-sort' ;const array = [ 3 , 44 , 38 , 5 , 47 , 15 , 36 , 26 , 27 , 2 , 46 , 4 , 19 , 50 , 48 ] ;nx...
Sorting-algorithm排序算法整合包含冒泡、选择、归并、快速排序使用java实现
快速排序 选择排序 Java文档 git clone https://github.com/Hopson97/Sort-Algorithm-Visualiser.git cd Sort-Algorithm-Visualiser gradle javadoc 然后打开build / docs / javadoc / index.html文件。 特别感谢 ...
leetcode切割分组 java_algorithm this is a sorting algorithm demo. created by InterlliJ. that ...快速排序 平均时间复杂度 O(n + k) 空间复杂度 O(k) CountingSort | 计数排序 | 用一个计算器
数据结构算法 (最新工作比较忙,可能不会及时更新,可以将现有的算法重复复习,也可以自己去网上...快速排序 归并排序 堆排序 有序摘要的合并 取数字指定数字的字 求整数最大数的数值 找到字符串中第一个不重复的字符
用Java语言实现的各种排序,包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。 插入排序: package org.rut.util.algorithm.support; import org.rut.util.algorithm....
三路快速排序 堆排序 索引堆排序(堆排序拓展) 说明:从多角度进行测试及包括数据重复率,数据有序性等对单一角度或者多角度提出算法的优化策略 搜索算法 二分搜索树 二分搜索法及其变体 并查集基础算法 算法设计...
程序员考试刷题 欢迎来到 Swift 算法俱乐部! 在这里,您将找到使用大家最喜欢的新语言 Swift 实现的流行算法和数据结构,并详细解释了它们的工作原理。 如果您是一名计算机科学专业的...快速查找排序数组中的元素。