//思想:实现快速排序的关键是首先在数组中选择一个数字(这里随机选取)作为枢纽元,将枢纽元与数组中最后的元素交换使得枢纽元
//离开要被分割的数据段,将数组中比枢纽元小的元素都移动数组的左边,将数组中比枢纽元大的元素都移动数组的右边
#include<iostream>
using namespace std;
#include<time.h>
int RandomInRange(int start ,int end)
{
if(end>start)
{
srand(time(NULL));
return start+rand() %((end-start));//产生start~end之间的随机数
}
}
void swap_element(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
int Partition(int data[],int length,int start,int end)
{
if(data==NULL || length<=0||start<0 || end>=length)
{
cout<<"error1!"<<endl;
exit(0);
}
int index=RandomInRange(start,end);
swap_element(&data[index],&data[end]);
int small=start-1;
for(index=start;index<end;index++)
{
if(data[index]<data[end])
{
++small;
if(small != index)
{
swap_element(&data[index],&data[small]);
}
}
}
++small;
swap_element(&data[small],&data[end]);
return small;
}
void Quicksort(int data[],int length,int start,int end)
{
if(start==end)
{
return ;
}
int index=Partition(data,length,start,end);
if(index>start)
Quicksort(data,length,start,index-1);
if(index<end)
Quicksort(data,length,index+1,end);
}
int main(void)
{
int data[10]={1,4,7,0,6,10,3,8,2,9};
Quicksort(data,10,0,9);
for(int i=0;i<10;i++)
cout<<data[i]<<" ";
cout<<endl;
return 0;
}
参考《数据结构与算法分析》
快速排序的最差时间复杂度为O(n^2);
最优时间复杂度为O(nlogn)
平均时间复杂度为O(nlogn)
分享到:
相关推荐
剑指offer leetcode 探索 常见数据结构 《算法》常见排序算法 使用语言: python go(待办) javascript(待办) <<剑指offer>> Leetcode编程题 排序算法 选择排序 插入排序 希尔排序 归并排序 快速排序 快速...
中级编程题目的是通过字节跳动的笔试,内容主要是数据结构(链表和二叉树)、剑指offer、leetcode top100。 排序 堆排序、快速排序、冒泡排序、希尔排序、选择排序、直接插入排序 LeetCode Top 100 滑动窗口
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
lru缓存leetcode剑指报价题库列表 --> IO实践--> 力扣问题列表 二进制搜索 解决方案 问题编号 困难 笔记 简单的 简单的 排序数组中最近的 赖十七: 中等的 中等的 找到 K 个最近的元素 中等的 找到大于目标的...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
LeetCode&剑指Offer LeetCode 1-100.md 剑指 offer 汇总.md 二分 二分法小结.md 搜索旋转排序数组.md 搜索旋转排序数组 II (重复).md 剑指 Offer 11. 旋转数组的最小数字【二分】.md 剑指 Offer 53 - I. 在排序...
快速排序 —— —— 归并排序 —— —— 插入排序 —— —— 选择排序 —— # 标题 解决方案 困难 155 简单的 20 简单的 739 中等的 394 中等的 # 标题 解决方案 困难 617 简单的 226 简单的 94 中等的 101 简单的 ...
java笔试题算法 AlgorithmCode ...使用三向切分快速排序,实际应用中可能出现的某些分布的输入能够达到线性级别,而其它排序算法仍然需要线性对数时间。 LeetCode 1-100 101-200 201-300 301-400 4
冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序、希尔排序、计数排序、桶排序、计数排序 顺序查找、二分查找、插值查找、斐波那契查找、树表查找、分块查找、哈希查找 系统设计题 LeetCode 常见题目标签...
二叉排序树查找,Python3 数据结构与算法的介绍及应用。1. 数据结构:数组、链表、栈、队列、树、堆、图; 2. 典型排序算法:冒泡排序、选择排序、插入排序、希尔...4. LeetCode 和《剑指Offer》刷题、多种方法的题解
leetcode5 dp Awesome 算法秒撕 ----排序---- 快速排序 * 参考算法导论 partition,将数组in-...剑指offer63): 股票低点买入,高点售出 维护一个当前的最低值,和当前的最大利润;最后返回当前最大利润 int max_ = I
剑指Offer文件夹下为剑指Offer题解,序号即为题目号。 数据结构(Data Structures): 栈 队列 链表 集合 字典和散列表 树 二叉堆和堆排序 图 排序算法: 冒泡排序 选择排序 插入排序 归并排序 快速排序 计数排序 ...
剑指offer 练习题 算法与数据结构 SQL 算法 void max_heapifty(vector<int>& nums, int start, int end); // 调整堆 void heap_sort(vector<int>& nums); // 堆排序 void shell_sort(vector<int>& nums); // 希尔...
该仓库作为个人刷题的题目记录仓库,包含剑指Offer上的全部面试题和LeetCode上的部分题目。 所涵盖的内容有: 剑指offer 75 数组 10 二分查找 9 二叉树,二叉搜索树,红黑树RBTree 44 单链表,哈希表,LRU 33 排序,...
剑指原题,剪绳子。 5 排序数组,平方后,数组当中有多少不同的数字(相同算一个)。 6 一个数据先递增再递减,找出数组不重复的个数,比如 [1, 3, 9, 1],结果为3,不能使用额外空间,复杂度o(n) 7 高考成绩2000万...
leetcode叫数 ...src/牛客网/剑指offer/ 目录下是在 进行的一些练习,题目来源是剑指 Offer,其中一部分习题有 java 和 kotlin 两个版本,java 目录下大概有 40 来个题的代码,不过都无描述,只有代码,kotlin
算法练级计划以面试算法过渡为线索,总结归纳面试涉及的算法知识点,整理LeetCode以及“剑指要约”出现的面试转换,在大量的LeetCode过渡中梳理一个刷题脉络,让大家能够在有限的频率,通过面试算法回归的练习,提高...
2、剑指Offer 3、LeetCode代码练习 github传送门 github传送门 gitee传送门 啊哈 算法 剑指Offer LeetCode 一、链表 1、Java实现单链表,支持增删改查。 2、单向链表反转 3、单向链表是否有环 4、合并两个有序链表 5...
剑指offer刷题 反转链表 前k小的数 链表相关 镜像的二叉树 Z字型打印二叉树 回溯法 机器人的运动范围 矩阵中的路径 leetcode刷题 动态规划相关 不用加减乘除作加法 一些公司的题目 推荐阅读 刷题必备 《剑指offer》 ...